平衡树

平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。

在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

旋转（Rotate）：几乎所有平衡树的操作都基于树旋转操作（也有部分基于重构，如替罪羊树），通过旋转操作可以使得树趋于平衡。对一棵查找树（search tree）进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量 n 成比例。如果可以让树维持平衡，也就是让h维持在${\displaystyle O(\log <!--\; \; -->n)}$，且最大的数。

查询后继（successor）：后继定义为大于，且最小的数。

在维护节点大小（size）后，可以支持以下操作：

查询排名（rank）：排名定义为比x小的数的个数加一。

查询第k大：即排名为的数。

以下数据结构支持平衡树大多数操作，但实现有根本不同:

用于表示有序的线性数据结构，如优先队列、关联数组、键(key)-值(value)的映射等。自平衡的二叉查找树与哈希表的相比，各有优缺。平衡树在按序遍历所有键值时是量级最优的，哈希表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于哈希表， ${\displaystyle O(\log <!--\; \; -->n)}$对比${\displaystyle O(n)}$；但平均时间复杂度逊于hash表，${\displaystyle O(\log <!--\; \; -->n)}$对比${\displaystyle O(1)}$。

平衡树的排序方法，虽然在平均时间复杂度上也是${\displaystyle O(n\log <!--\; \; -->n)}$，但由于cache性能、树的调整操作等，性能上不如快速排序、堆排序、归并排序等同为${\displaystyle O(n\log <!--\; \; -->n)}$复杂度的排序。