树与层次结构
平衡树
平衡树是一种会主动让自己保持低矮、绝不退化成长藤的查找树。它的动机正是普通二叉搜索树的弱点：喂给它有序数据，它就会跌到 O(n)。平衡树额外加上一条把树高限制在约 log n 的规则，于是无论键以什么顺序到来，查找、插入和删除都被锁定在 O(log n)。
两种著名的设计能说明这个思路。AVL 树要求每个节点左右子树的高度相差不超过一——很严格，所以它非常矮、查找很快。红黑树则给节点染上红色或黑色，施加较宽松的规则，仍把树高约束在 2·log n 左右——稍高一些，但维护更便宜，这也是许多标准库的有序映射和集合都以它为底层的原因。两者都在每个节点里多存一点记账信息（高度或颜色）。
当一次插入或删除使树失去平衡时，就用旋转来修复：这是一种小而局部的重排，让某个节点与它的子节点互换支点，重新分配子树、降低树高，同时不破坏“左小右大”的排序。一次旋转只动几个指针，因此是 O(1)；而沿着回到根的路径上你最多只需 O(log n) 次旋转——整个结构正是这样才能廉价地保持平衡。
// x y
// / \ / \
// y C --> A x
// / \ / \
// A B B C
Node* rotateRight(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
return y; // y is the new subtree root
}一次单右旋——保持查找树平衡的 O(1) 局部修复。
AVL 树更矮（查找更快）；红黑树重平衡时旋转更少（更新更快）——两者都保证 O(log n)。
又称
另见