C++（初阶）（十八）——AVL树

AVL树

概念

1，AVL树是最先发明的⾃平衡⼆叉查找树，AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制高度差去控制平衡。AVL树是特殊的二叉搜索树，它的左右⼦树都是AVL树，且左右子树的高度差的绝对值不超过1。空树也是AVL树。

2，AVL树实现的本质是控制左右子树的高度差的绝对值不超过1，也就是只要符合该条性质，并且不破坏AVL树结构的方法逻辑上都是可以的。

下面就是一种普遍的实现方法：

首先我们要了解一个概念：平衡因子(balancefactor)，对于AVL树的每个结点，都包含一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说正常AVL树的任何结点的平衡因⼦等于0/1/-1，也就是说如果平衡因子出现其他的值，AVL树就出现了问题，需要进行一系列调整。

但是要注意的一点是：AVL树并不是必须需要平衡因子，平衡因子只是方便我们控制左右子树的高度差的绝对值不超过1。

3，AVL树整体结点数量和分布和完全⼆叉树类似，高度可以控制在logN，那么增删查改的效率也可以控制在O(logN) ，相⽐⼆叉搜索树有了很大的提升。

例如下面就不是AVL树，结点10，左子树高度为0，右子树高度为2，不符合定义所以不是AVL树。

为了成为AVL树，我们需要进行调整，使之变为如下图所示，具体操作之后详述。

实现

AVL树的结点

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;				//键值对AVLTreeNode<K, V>* _left;	//左子树AVLTreeNode<K, V>* _right;	//右子树//后续更新平衡因⼦需要parent指针AVLTreeNode<K, V>* _parent;int _bf; // balance factor,平衡因子//构造AVLTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};

插入

插入方法

1，按照二叉搜索树规则插入

2，更新平衡因子（只会影响插入结点的祖先，所以只需要更新祖先的平衡因子，最坏的情况下要更新到根结点）

3，如果更新结点没有出现高度差>1的情况，那么插入结束：

如果出现高度差>1的情况，使AVL树出现不平衡，那么需要对不平衡子树进行旋转调整，使其平衡，至此插入结束。

平衡因子更新

1，平衡因子=右子树高度-左子树高度。

2，只有子树高度变化才会影响当前结点平衡因子。

3，插⼊结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在 parent的左子树，parent平衡因子–

4，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⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新，插⼊结束。

四，不断更新，更新到根，根的平衡因子是1或-1也停止了。

插入代码参考：

//插入
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}//记录cur的父结点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);//此处还要对key和parent的左右节点的值比较后插入合适的位置if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;//更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else if (cur == parent->_right){parent->_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){//不平衡，旋转，之后breakif (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);}break;}else{//正常情况下不会执行，但是如果前面的条件出现问题会执行并报错assert(false);}}return true;	
}

旋转

1，必须保持搜索树的规则

2，让旋转的树从不满足变平衡，其次降低旋转树的高度

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

右单旋

代码参考：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;//记录一下，下面需要Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = ppnode;}else{if (parent == ppnode->_left){ppnode->_left = subL;}else if (parent == ppnode->_right){ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = parent->_bf = 0;
}

左单旋

与右单旋类似。

代码参考：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;//记录一下，下面需要Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = ppnode;}else{if (parent == ppnode->_left){ppnode->_left = subR;}else if (parent == ppnode->_right){ppnode->_right = subR;}subR->_parent = ppnode;}subR->_bf = parent->_bf = 0;
}

左右双旋

如果我们继续使用上述右单旋（左单旋）是无法解决某些情况的。

例如：仅使用右单旋，以11为旋转点，发现旋转后AVL树依旧是不平衡的。

于是我们就需要使用左右双旋，所选取的旋转点（也就是传的parent）是不同的，这点很好实现，复用代码即可。但是思考一下，仅仅对右单旋和左单旋的代码复用，能否完成我们的需求呢？分析后发现仅仅复用是不够的，因为我们对平衡因子没有办法处理，所以我们需要额外对旋转后的平衡因子进行更新。

代码参考：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

右左双旋

与左右双旋类似。

代码参考：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent);RotateL(parent->_right);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 if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

遍历

中序遍历AVL树是有序的，使用中序遍历

void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}

AVL平衡检测

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;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

完整代码

[link]（https://gitee.com/any10/c_plus_plus/tree/master/2025c%2B%2B/AVLTree_5_03）