平衡树：修订间差异

平衡树是计算机科学中的一类数据结构。 二叉查找树是计算机科学中的一种重要的查找结构，而一般的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。

不平衡的树结构

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

平衡的树结构

基本操作

几乎所有平衡树的操作都基于树旋转操作，通过旋转操作可以使得树趋于平衡。

各种平衡树

• AVL树，经典平衡树, 所有操作的最坏复杂度都是$O(\log {n})$的。
• Treap，利用随机堆的期望深度来优化树的深度，达到较优的期望复杂度。
• 伸展树，使得经常查找的结点深度较小，从而降低均摊复杂度。
• 红黑树。
• 節點大小平衡樹。