C++ AVL 树原理与实现
1. AVL 树的概念
AVL 树是最先发明的自平衡二叉查找树。它是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。
AVL 树得名于它的发明者 G.M.Adelson-Velsky 和 E.M.Landis，他们在 1962 年的论文中发表了它。
AVL 树引入一个平衡因子 (balance factor) 的概念，每个结点都有一个平衡因子。任何结点的平衡因子等于右子树的高度减去左子树的高度。因此，任何结点的平衡因子只能是 0、1 或 -1。有了平衡因子可以更方便地观察和控制树是否平衡。
为什么 AVL 树要求高度差不超过 1，而不是高度差是 0？因为有些情况下无法做到高度差是 0（例如 2 个结点、4 个结点等），高度差为 1 是最佳平衡状态。
AVL 树整体结点数量和分布和完全二叉树类似，高度可以控制在 logN，增删查改的效率也可以控制在 O(logN)，相比普通二叉搜索树有了本质的提升。
2. AVL 树的插入
AVL 树插入一个值的大概过程
- 插入一个值按二叉搜索树规则进行插入。
- 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子。所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了。
- 更新平衡因子过程中没有出现问题，则插入结束。
- 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。
平衡因子更新
更新原则
- 平衡因子 = 右子树高度 - 左子树高度
- 只有子树高度变化才会影响当前结点平衡因子。
- 插入结点，会增加高度。所以新增结点在 parent 的右子树，parent 的平衡因子++；新增结点在 parent 的左子树，parent 平衡因子--。
- parent 所在子树的高度是否变化决定了是否会继续往上更新。
更新停止条件
- 更新后 parent 的平衡因子等于 0，说明更新前 parent 子树一边高一边低，新增的结点插入在低的那边，插入后 parent 所在的子树高度不变，不会影响 parent 的父亲结点的平衡因子，更新结束。
- 更新后 parent 的平衡因子等于 1 或 -1，说明更新前 parent 子树两边一样高，新增的插入结点后，parent 所在的子树一边高一边低，parent 所在的子树符合平衡要求，但是高度增加了 1，会影响 parent 的父亲结点的平衡因子，所以要继续向上更新。
- 更新后 parent 的平衡因子等于 2 或 -2，说明更新前 parent 子树一边高一边低，新增的插入结点在高的那边，parent 所在的子树高的那边更高了，破坏了平衡，需要旋转处理。旋转的目标有两个：1. 把 parent 子树旋转平衡。2. 降低 parent 子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
- 不断更新，更新到根，根的平衡因子是 1 或 -1 也停止了。
3. AVL 树的右转
旋转的原则
- 保持搜索树的规则。
- 让旋转的树从不满足变平衡，其次降低旋转树的高度。
旋转总共分为四种：左单旋、右单旋、左右双旋、右左双旋。
右单旋
在 a 子树中插入一个新结点，导致 a 子树的高度从 h 变成 h+1，不断向上更新平衡因子，导致 10 的平衡因子从 -1 变成 -2，10 为根的树左右高度差超过 1，违反平衡规则。10 为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。
旋转核心步骤：因为 5 < b 子树的值 < 10，将 b 变成 10 的左子树，10 变成 5 的右子树，5 变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的 h+2，符合旋转原则。
// 右单旋代码
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
(subLR) {
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
(parent == _root) {
_root = subL;
subL->_parent = ;
} {
(ppNode->_left == parent) {
ppNode->_left = subL;
} {
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
parent->_bf = ;
subL->_bf = ;
}
