AVL 树
进阶AVL 树在每次更新后主动修高度，换来稳定的 O(log n)。
// 算法讲解
AVL 树
默认示例会触发一次 LL 失衡，从而执行左旋/右旋修复。
待机
速度 中
待机 ⌨1int height(Node* node) {
2 return node ? node->height : 0;
3}
4
5int balanceFactor(Node* node) {
6 return height(node->left) - height(node->right);
7}
8
9Node* rotateLeft(Node* x) {
10 Node* y = x->right;
11 x->right = y->left;
12 y->left = x;
13 return y;
14}
复杂度分析
时间 查找/插入/删除 O(log n)
空间 O(n)
最优 O(log n)
最坏 O(log n)
算法讲解
AVL 树要求每个节点左右子树高度差绝对值不超过 1，因此它比普通 BST 更稳定。
插入或删除导致失衡时，需要根据形态执行 LL、RR、LR、RL 四类旋转。
它的优势是查找性能很稳，代价是更新时维护平衡因子和旋转逻辑更复杂。
把 AVL 学明白之后，再看红黑树会更容易理解"不同平衡策略之间的权衡"。