对一棵查找树(search tree)进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。
旋转Rotate -- 不破坏左小右大特性的小手术
平衡树有很多种, 其中有几类树维持平衡的方法, 都是靠整形小手术:
图中 x 与 y 为 nodes; A, B, C 为一整串的 subtrees。 试想: 如果 x 原来是 y 的 left child; 现在想将 x 变成 parent, 则树的其它部分应如何变化? y 必须变成 right child, 这样才能维持 BST 的特性 -- 左小右大。 至于 x 与 y 以下的其它部分, 可以整串 subtree 一起处理: x 原来的 left subtree (A), 调整后还是 x 的 left subtree; y 原来的 right subtree (C), 调整后还是 y 的 right subtree; 而 x 原来的 right subtree (B), 调整后很自然只有一个地方可以放: 变成 y 的 left subtree。 这些规则都不需要记, 因为如果你希望调整后还维持 BST 左小右大的特性, 这是唯一的答案。 把 x,y 两个值及 A,B,C 三棵 subtrees 内的三串值画在数在线看更清楚:
--------- x --------- y ---------
A B C
这个动作, 称为 right rotation 向右旋转, 或称为顺时针旋转 (clockwise)。 原来的 parent (y) 叫做 pivot, 原来的 child (x) 叫做 rotator。
把上图反过来看, 如果原来的树长得像右图, 想将它改成左图, 则称为 left rotation 向左旋转, 或称为逆时针旋转 (counter-clockwise)。 原来的 parent (x) 叫做 pivot, 原来的 child (y) 叫做 rotator。
一棵二叉平衡树的子树，根是Root，左子树是x，右子树的根为RootR，右子树的两个孩子树分别为RLeftChild和RRightChild。则左旋后，该子树的根为RootR，右子树为RRightChild，左子树的根为Root，Root的两个孩子树分别为x(左)和RLeftChild(右)。
一棵二叉平衡树的子树，根是Root，右子树是x，左子树的根为RootL，左子树的两个孩子树分别为LLeftChild和LRightChild。则右旋后，该子树的根为RootL，左子树为LLeftChild，右子树的根为Root，Root的两个孩子树分别为LRightChild(左)和x(右)。
数一下旧的 parent 左 subtree 有多少 nodes? 右 subtree 有多少 nodes? 旋转后新的 parent 左右 subtrees 又各有多少 nodes? 发现右旋的效果会让树的重心往右移; 而左旋的效果则是让树的重心往左移。 如果你的树经历过许多 insert/remove 等等岁月的沧桑, 越长越歪, 在适当的时候对它进行一下旋转手术, 不就可以将它变回矮矮胖胖四平八稳的美丽模样吗? 所以左旋与右旋是几种平衡树共同采用的基本手术; 只不过不同的平衡树, 选择不同的时机/条件来动手术而已。
左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。
非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。
为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的(或者至少大部分是平衡的)。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。
