平衡树

二叉搜索树上的大多数操作需要的时间与树的高度成正比，因此希望保持树的高度较小。有高度的二叉树 h 最多可以包含 2⁰+2¹+ +2^h = 2^h+1—1 节点。因此，对于任何具有 n 节点和高度 h以下内容:

这意味着:

  。

换句话说，二叉树的最小高度 n 节点是 log₂（n)， 向下舍入；也就是说，   。^[2]

然而，在相当常见的情况下，最简单的BST项目插入算法可能会生成一个带有n个节点的树。例如，当项目以关键字有序的顺序被插入时，树退化成一个n个节点的链表。这两种情况下的性能差异可能是巨大的:因为 n =1,000,000，最小高度是 19。

如果数据项提前知道，那么在平均意义上，通过以随机顺序插入，高度可以保持较小，从而形成 随机二元搜索树。 然而，有许多情况(例如在线算法）下随机化 不可行。

自平衡二叉树通过在关键字插入时，在树上执行转换(例如 树旋转)，为了保持高度与log₂（n)成比例。虽然某种程度上涉及了一定的开销， 从长远来看，这可能是合理的，因为它确保了以后操作的快速执行。

虽然有可能以预期的最小高度维持BST O(log n) 时间操作(查找/插入/移除)，维护这种结构所需的额外空间要求往往超过搜索时间的减少。相比之下，AVL树保证在最佳高度的1.44倍之内，而在初始实现中只需要额外的两个存储位。^[2] 因此，大多数自平衡BST算法将高度保持在该下限的常数因子内。

在 渐近 ("Big-0”)意义上，包含 n 项目的自平衡的BST结构允许在O(log n )最坏时间内查找、插入和删除项目 )，以及在O(n)时间内有序枚举所有项目。 对于某些实现，这些是每个操作的时间限制，而对于其他实现，它们是一系列操作的摊还分析时间界。 这些时间在所有仅通过比较操作关键字的数据结构中是渐近最优的。

实现这种类型树的数据结构包括:

• 2-3棵树
• AA树
• AVL树
• b树
• 红黑树
• 替罪羊树
• 伸展树
• Treap
• 重量平衡树

自平衡二叉搜索树可以自然地用于构建和维护有序列表，例如优先级队列. 它们也可以用于关联数组 .键值对只需根据键的顺序插入即可。在这种情况下，自平衡BST具有 许多优点和缺点 相比于他们的主要竞争对手（哈希表）。自平衡BST的一个优点是，它们允许项目以关键字顺序的快速(实际上是渐近最优的)枚举，哈希表不提供。一个缺点是，当可能有多个项目具有相同的密钥时，它们的查找算法变得更加复杂。自平衡BST比哈希表具有更好的最坏情况查找性能(0(log n)比0(n))，但是比0(1)具有更差的平均情况性能(0(log n))。

自平衡BST可用于实现任何需要可变有序列表的算法，以实现最佳最坏情况渐近性能。例如，如果 二叉树排序 是用自平衡BST实现的，我们还有一个非常简单的描述 渐近最优的 o(n log n)排序算法。类似地，计算几何学中的许多算法利用自平衡BSt的各种变化来解决以下问题,,比如 线段交点 问题和 点位置 高效解决问题。 (然而，对于一般情况下的性能，自平衡BST可能不如其他解决方案有效。 二叉树排序,尤其可能不如 归并排序, 快速排序，或 堆排序，因为树平衡开销以及 缓存 访问模式。)

自平衡BST是灵活的数据结构，因为很容易扩展它们来有效地记录附加信息或执行新的操作。例如，可以记录每个子树中具有某个属性的节点数，从而可以用该属性在0(log n)时间内计数某个键范围内的节点数。这些扩展可以用来优化数据库查询或其他列表处理算法。