基本操作

几乎所有平衡树的操作都基于树旋转操作，通过旋转操作可以使得树趋于平衡。 对一棵查找树（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。

各种平衡树

AVL树，经典平衡树, 所有操作的最坏复杂度都是 O ( log ⁡ ⁡ --> n ) {\displaystyle O(\log {n})} 的。

Treap，利用随机堆的期望深度来优化树的深度，达到较优的期望复杂度。

伸展树，使得经常查找的结点深度较小，从而降低均摊复杂度。

红黑树。

加衡树。

2-3树

AA树

替罪羊树

节点大小平衡树

其他类型

跳表，一种支持平衡树大多数操作的数据结构

应用

用于表示有序的线性数据结构，如优先队列、关联数组、键-值的映射等。自平衡的二叉查找树的实现与其竞争对手hash表的实现，各具有优缺点。自平衡二叉查找树在按序遍历所有键值时是量级最优的，hash表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于hash表， O(log n)对比O(n)；但平均时间复杂度逊于hash表，O(log n)对比O(1)。

自平衡二叉查找树的排序方法，虽然在平均时间复杂度上也是O(n log n)，但由于cache性能、树的调整操作等，性能上不如快速排序、堆排序、合并排序。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。