树旋转
在不改變中序的前提下,一種使二元樹平衡的操作 / 维基百科,自由的 encyclopedia
在数据结构中,树旋转(英语:Tree rotation)是对二叉树的一种操作,不影响元素的顺序,但会改变树的结构,将一个节点上移、一个节点下移。树旋转会改变树的形状,因此常被用来将较小的子树下移、较大的子树上移,从而降低树的高度、提升许多树操作的效率。
此条目没有列出任何参考或来源。 (2015年3月5日) |
此条目需要编修,以确保文法、用词、语气、格式、标点等使用恰当。 (2011年10月13日) |
树的旋转方向有很多不同的定义,有些定义彼此之间还存在冲突。有些人认为旋转方向应该反映节点的移动方向(左子树旋转到父节点的位置为右旋),有些人则认为旋转方向应该反映被旋转的子树是哪棵(左子树旋转到父节点的位置为左旋,与前一种说法相反)。这篇维基文章采用前者的定义:旋转方向为节点的移动方向。