【数据结构】AVL树的实现

1. AVL 的概念

• AVL树是最先发明的自平衡二叉查找树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AV树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
• AVL树实现这里我们引入一个平衡因子(balancefactor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
• AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN，那么增删查改的效率也可以控制在O(logN），相比二叉搜索树有了本质的提升。

2. AVL 树的实现

2.1 AVL 树的结构

相比于二叉搜索树，AVL 因为要控制左右子树高度差，所以引入了 平衡因子，而为了更行平衡因子，它又引入了一个 父指针。

// 节点结构
template<class K, class V>
struct AVLTreeNode
{// 需要parent指针，后续更新平衡因⼦可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};// AVL树
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:// ...
private:Node* _root = nullptr;
};

2.2 AVL 树的插入

2.2.1 AVL 树插入一个值的大致过程

1. 插入一个值按二叉搜索树规则进行插入。
2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
3. 更新平衡因子过程中没有出现问题，则插入结束
4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。

2.2.2 平衡因子更新

更新原则：

• 平衡因子＝右子树高度-左子树高度
• 只有子树高度变化才会影响当前结点平衡因子。
• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子–
• parent所在子树的高度是否变化决定了是否会继续往上更新

更新停止条件：

• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0或者1->0，说明更新前parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。
• 更新后parent的平衡因子等于1或-1，更新前更新中parent的平衡因子变化为0->1或者0->-1，说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。
• 更新后parent的平衡因子等于2或-2，更新前更新中parent的平衡因子变化为1->2或者-1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。

更新到10结点，平衡因子为2，10所在的子树已经不平衡，需要旋转处理

更新到中间结点，3为根的子树高度不变，不会影响上一层，更新结束

最坏更新到根停止

插入其实就是在二叉搜索树的插入上增加了更新平衡因子机制，而更新平衡因子时可能需要旋转操作，旋转操作后面在讲。

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent){// 更新平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0){// 更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 继续往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 不平衡了，旋转处理，旋转部分后文讲if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}

2.3 旋转

2.3.1 旋转的原则

1. 保持搜索树的规则
2. 让旋转的树从不满足变平衡，其次降低旋转树的高度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

2.3.2 右单旋

触发条件

• 失衡节点A的左子树高度 - 右子树高度 = 2（即平衡因子为-2）。
• A的左孩子B的平衡因子为-1（即B的左子树更高，形成LL型失衡）。

操作步骤

1. 提升左孩子B为新的根节点。
2. 原根节点A成为B的右孩子。
3. 处理B的右子树：如果B原本有右子树BR，将其作为A的新左子树。
4. 更新平衡因子：旋转后，A和B的平衡因子均变为0。

失衡结构：A (BF=-2)/B (BF=-1)/C右旋过程：
1. 将B提升为根，A成为B的右孩子：B/ \C   A
2. 原B的右子树（假设为空）无需处理。
最终平衡因子：B(BF=0), A(BF=0)原结构（LL失衡）：parent (bf=-2)/subL (bf=-1)/   \X   subLR旋转后：subL (bf=0)/   \X   parent (bf=0)/subLR

代码：

	void RorateR(Node* parent){// 1. 获取左孩子subL及其右子树subLRNode* subL = parent->_left;  // 保存左子树根节点subLNode* subLR = subL->_right;  // 保存subL的右子树// 2. 调整parent和subLR的父子关系parent->_left = subLR;		 // 将subLR挂到parent的左侧if (subLR)					 // 若subKR存在，更新它的父指针subLR->_parent = parent;// 3. 调整subL和parent的父子关系Node* pParent = parent->_parent; // 记录原parent的父节点（可能为空）subL->_right = parent;			 // 将parent作为subL的右孩子parent->_parent = subL;			 // 更新parent的父节点// 4. 将subL连接到原parent的父节点（整棵树的连接）if (parent == root)				 // 若parent是根节点{_root = subL;				 // 更新根节点为subLsubL->_parent = nullptr;	 // 新根节点的父指针置空}else{if (pParent->_left == parent) // 判断原parent是左孩子还是右孩子pParent->_left = subL;    // 将subL挂到原祖父的左elsepParent->_right = subL;   // 将subL挂到原祖父的右subL->_parent = pParent;	  // 更新subL的父指针}// 更新平衡因子subL->_bf = 0;parent->_bf = 0;}

2.3.3 左单旋

触发条件

• 失衡节点A的平衡因子为+2。
• A的右孩子B的平衡因子为+1（形成RR型失衡）。

操作步骤

1. 提升右孩子B为新的根节点。
2. 原根节点A成为B的左孩子。
3. 处理B的左子树：如果B原本有左子树BL，将其作为A的新右子树。
4. 更新平衡因子：A和B的平衡因子均变为0。

失衡结构：A (BF=+2)\B (BF=+1)\C左旋过程：
1. 将B提升为根，A成为B的左孩子：B/ \A   C
最终平衡因子：B(BF=0), A(BF=0)原结构（LL失衡）：parent (bf=+2)\subR (bf=+1)/   \subRL   X
旋转后：subR (bf=0)/   \parent    X\subRL

代码就和右单旋刚好相反，不做过多解释：

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == pParent->_left)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}parent->_bf = subR->_bf = 0;}

2.3.4 左右双旋

为什么需要双旋转？

• 单旋转无法解决之字型失衡：例如在LR失衡中，失衡路径是左→右，直接右旋会破坏结构，需先通过左旋将其转化为LL型。
• 平衡因子动态调整：双旋转后需根据中间节点的原始平衡因子重新计算各节点的平衡因子。

先通过单旋调整成上面可以单旋的类型，再通过单旋解决问题。

触发条件

• 失衡节点A的平衡因子为-2。
• A的左孩子B的平衡因子为+1（形成LR型失衡，即B的右子树更高）。

操作步骤

1. 先对B左旋（转化为LL型）：
   • 将B的右孩子C提升为A的新左孩子。
   • B成为C的左孩子，C的原左子树成为B的右子树。
2. 再对A右旋：
   • 将C提升为根，A成为C的右孩子。
3. 更新平衡因子：
   • 若C原平衡因子为0，则A和B均变为0。
   • 若C原平衡因子为+1，则A(BF=0), B(BF=-1), C(BF=0)。
   • 若C原平衡因子为-1，则A(BF=+1), B(BF=0), C(BF=0)。

初始失衡结构：A (BF=-2)/B (BF=+1)\C (BF=0)步骤1：对B左旋后：A/C/B步骤2：对A右旋后：C/ \B   A
平衡因子：C(BF=0), B(BF=0), A(BF=0)初始结构（LR失衡）parent (bf=-2)/subL (bf=+1)\subLR (bf=-1/0/+1)/   \CL   CR旋转后结构subLR (bf=0)/      \subL       parent/  \       /   \CL   CR_L  CR_R  CR

	void RotateLR(Node* parent){// 1. 获取相关节点Node* subL = parent->_left; // parent的左孩子Node* subLR = subL->_right; // subL的右孩子（subLR，即失衡的中间节点）int bf = subLR->_bf;		// 保存subLR的原始平衡因子// 2. 双旋操作RotateL(parent->_left);		// 先对subL进行左旋（将subLR提升为subL的位置）RotateR(parent);			// 再对parent进行右旋（将subLR提升为根）// 3. 根据subLR的原始平衡因子调整平衡因子if (bf == -1)				// subLR的左子树更高{subLR->_bf = 0;			// 新根subLR平衡因子归零subL->_bf = 0;			// 原左子树subL平衡因子归零parent->_bf = 1;		// 原根parent右子树更高（平衡因子+1）}else if (bf == 1)			// subLR的右子树更高{subLR->_bf = 0;			// 新根subLR平衡因子归零subL->_bf = -1;			// 原左子树subL左子树更高（平衡因子-1）parent->_bf = 0;		// 原根parent平衡因子归零}else if (bf == 0)			// subLR左右子树等高{subLR->_bf = 0;			// 所有相关节点平衡因子归零subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

2.3.5 右左双选

触发条件

• 失衡节点A的平衡因子为+2。
• A的右孩子B的平衡因子为-1（形成RL型失衡，即B的左子树更高）。

操作步骤

1. 先对B右旋（转化为RR型）：
   • 将B的左孩子C提升为A的新右孩子。
   • B成为C的右孩子，C的原右子树成为B的左子树。
2. 再对A左旋：
   • 将C提升为根，A成为C的左孩子。
3. 更新平衡因子：
   • 若C原平衡因子为0，则A和B均变为0。
   • 若C原平衡因子为+1，则A(BF=-1), B(BF=0), C(BF=0)。
   • 若C原平衡因子为-1，则A(BF=0), B(BF=+1), C(BF=0)。

初始失衡结构：A (BF=+2)\B (BF=-1)/C (BF=0)步骤1：对B右旋后：A\C\B步骤2：对A左旋后：C/ \A   B
平衡因子：C(BF=0), A(BF=0), B(BF=0)初始结构（RL失衡）parent (bf=+2)\subR (bf=-1)/subRL (bf= -1/0/+1)/   \CL   CR旋转后结构subRL (bf=0)/      \parent     subR/   \      /   \CL  CR_L  CR_R  CR

和左右双旋相反：

	void RotateRL(Node* parent){// 1. 获取相关节点Node* subR = parent->_right;Node* subRL = subR->_left;	// subR的左孩子（subRL，即失衡的中间节点）int bf = subRL->_bf;		// 保存subRL的原始平衡因子// 2. 双旋转操作RotateR(parent->_right);	// 先对subR进行右旋（将subRL提升为subR的位置）RotateL(parent);			// 再对parent进行左旋（将subRL提升为根）// 3. 根据subRL的原始平衡因子调整平衡因子if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

2.4 AVL 树的查找

通过二叉搜索树的规则进行查找就是了，这个不难

	Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}

2.5 AVL 树平衡检测

我们实现的AVL树是否合格，我们通过检查左右子树高度差的的程序进行反向验证，同时检查一下结点的平衡因子更新是否出现了问题。

这里简单提一下，因为 AVL 树是棵树，所以我们常见的遍历方式是通过递归调用，而这种 递归调用 直接暴露给用户显然不太合适，所以我们这里选择暴露一个公有接口，提供简洁的访问入口，隐藏内部实现细节，再通过私有辅助函数去完成内部实现细节。这种写法属于 包装器模式 的一种应用，有兴趣的自己去搜下。

class AVLTree
{
public:int Height(){return _Height(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}
private:int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}