C++数据结构：AVL树的插入、旋转与平衡全过程
目录
1 AVL树的概念
AVL树是最先发明的自平衡二叉查找树，AVL树可以是空树，AVL树满足二叉搜索树的性质。它的左右子树也都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。理解了AVL树，更有利于掌握红黑树。
AVL树引入了一个平衡因子的概念，每个节点都有一个平衡因子，任何节点的平衡因子等于右子树的高度减去左子树的高度，也就是说平衡因子为0/1/-1，AVL树不是必须有平衡因子，有了平衡因子有利于我们去观察和控制树是否平衡。
AVL是高度平衡搜索二叉树，为什么要求高度差不超过1，而不是高度差是0呢？按道理说0是更好的平衡，通过画图可以发现，有些情况是做不到高度差是0的。比如一棵树只有2个节点，高度差就是1，无法做到高度差是0。
AVL树整体节点数量和分布和完全二叉树类似，高度可以控制再logN，那么增删改查的效率也可以控制在O(logN)。
2 AVL树的实现
2.1 AVL树的结构
首先定义一个AVL树中一个节点的结构:
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;//平衡因子
AVLTreeNode(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树插入一个值的过程
AVL树插入一个值按照二叉搜索树的规则进行插入，从根节点开始比较，比当前节点小，往左走；比当前节点大，往右走；遇到空位置，插入节点。
新增节点之后，会影响祖先节点的高度，会影响部分祖先节点的平衡因子，所以要更新新增节点到根节点路径上的平衡因子，实际中最坏情况下更新到根，有些情况下更新到中间就停止了。这里下面会做详细分析。
更新平衡因子过程中没有出现问题，则插入结束。
更新平衡因子过程中出现不平衡（平衡因子更新成-2或2），需要进行旋转处理，本质是降低了子树的高度，不会影响上一层，所以插入结束。旋转操作也将重点介绍。
2.2.2 平衡因子更新
2.2.2.1 更新原则
- 平衡因子=右子树高度-左子树高度
- 只有子树高度变化才会影响当前节点的平衡因子
- 插入节点，会增加高度。因为平衡因子=右子树高度-左子树高度，所以新增节点在parent的右子树，parent的平衡因子++；新增节点在parent的左子树，parent平衡因子--
- parent所在子树的高度是否变化决定了是否会继续向上更新
2.2.2.2 更新停止条件
这里分三种情况讨论
第一种情况：更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0或者1->0，说明更新前parent子树一边高一边低，新增的节点插入在低的那边，插入后parent所在的子树高度不变，所以就不会影响parent的父亲节点的平衡因子，更新结束。
第二种情况：更新后parent的平衡因子等于1或-1，更新前parent的平衡因子变化为0->-1或者0->1，说明更新前parent子树两边一样高，新增的插入节点后，parent所在的子树一边高一边低，高度增加了1，会影响parent的父亲节点的平衡因子，所以要继续向上更新。
更新到中间节点，3为根的子树高度不变，不会影响上一层，更新结束。
第三种情况：更新后的平衡因子等于2或者-2，更新前更新中的parent的平衡因子变化为-1->2或者1->2，说明更新前parent子树一边高一边低，新增的节点在高的那边，parent所在的子树高的那边更高了，破坏了平衡。parent所在的子树不符合平衡的要求，需要做旋转处理。
旋转的目标有两个：一是把parent的子树旋转平衡，二是降低parent子树的高度，恢复到插入节点以前的高度，所以旋转后也不需要继续向上更新，插入结束。
更新到10节点，平衡因子为2，10所在的子树已经不再平衡，需要旋转处理。
2.2.3 插入节点即更新平衡因子代码实现
在说明完插入节点和更新平衡因子的原理后，在说明旋转的原理和操作之前，先完成插入节点和更新平衡因子的代码：
//插入函数
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
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--;
}
else
{
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)
{
//不平衡时，做旋转处理，下面将讲解
break;
}
else
{
assert(false);
}
}
return true;
}2.3 旋转
2.3.1 旋转的原则
- 保持搜索树的规则
- 让旋转的树从不满足变平衡，其次降低旋转树的高度
旋转总共分为4种：右单旋/左单旋/左右双旋/右左双旋
在下面的图中，有些节点是为了便于理解给出了具体值，实际上只要满足搜索树的性质，什么值都可以。
2.3.2 右单旋
本图展示的是根为10的树，有a/b/c抽象为三颗高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。
10可能是整棵树的根，也可能是子树的根。这里第二棵树的10的平衡因子是-2
在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的左右高度差超过1，违反平衡规则。10的左树过高，需要向右边旋转，控制两棵树的平衡。
核心步骤：因为5<b子树的值<10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。旋转后不会再影响上一层，插入结束。
符合右单旋的情况有很多种，这里再举几个例子：
情况1：a/b/c高度h==0
情况2：插入前a/b/c高度h==1 这里第二棵树的10的平衡因子是-2
情况3：插入前a/b/c高度h==2
b和c可以是x/y/z中任意一种
a必须是x，因为a如果是y/z，插入节点后y/z的高度+1，y/z自身就要旋转，只有a是x时，插入节点后高度+1，a不需要旋转。
2.3.3 右单旋代码实现
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
subL->_bf = 0;
parent->_bf = 0;
}2.3.4 左单旋
本图展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体跟上面右旋类似。
在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。
旋转核心步骤：因为10<b子树的值<15，将b变成10的右子树，10变成15的左子树，15变成这棵树的新的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10是整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
2.3.5 左单旋代码实现
//左单旋
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 (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subR;
}
else
{
pParent->_right = subR;
}
subR->_parent = pParent;
}
subR->_bf = 0;
parent->_bf = 0;
}2.3.6 左右双旋
情况1：插入前a/b/c高度h==0
情况2：插入前a/b/c高度h==1
如图所示，左边高时，如果插入位置不是在a子树，而是在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题。右单旋后，树依旧不平衡。右单旋能解决的是纯粹左边高的树，但是插入在b子树中，10为根的子树对于10是左边高，对于5就是右边高，所以需要两次旋转才能解决，以5为旋转点先进行一个左单旋，以10为旋转点进行一个右单旋，这棵树就平衡了。
下面我们将a/b/c子树抽象为高度h的AVL树进行分析，另外我们要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树，因为我们要对b的父亲节点5为旋转点进行左单旋，左单旋要动b的子树。b子树新增节点的位置不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里要分三个场景讨论
场景一：h>=1时，新增节点插入在e子树，e子树的高度从h-1变为h，然后更新平衡因子，引发旋转，其中8的平衡因子为-1，旋转后8和5的平衡因子为0，10平衡因子为1。
场景二：h>=1时，新增节点插入在f子树，f子树的高度从h-1变为h，然后更新平衡因子，引发旋转，其中8的平衡因子为-1，旋转后8和10的平衡因子为0，5平衡因子为1。
场景三：h=0时，a/b/c都是空树，b自己就是一个新增节点，更新平衡因子，引发旋转，其中8的平衡因子为0，旋转后8和5和10平衡因子均为0。
2.3.7 左右双旋代码实现
复用上面的右单旋和左单旋函数，更新平衡因子：
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}2.3.8 右左双旋
和左右双旋类似，分三个场景讨论
场景一：h>=1时，新增节点插入在e子树，e子树高度从h-1变为h，更新平衡因子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。
场景二：h>=1时，新增节点插入在f子树，f子树高度从h-1变为h，更新平衡因子，引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。
场景三：h=0时，a/b/c都是空树，b自己就是一个新增节点，更新平衡因子，引发旋转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0。
2.3.9 右左双旋代码实现
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
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树的查找
查找一个节点用二叉搜索树的逻辑实现即可，查找效率为O(logN)
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树是否合格，通过检查左右子树高度差的程序进行反向验证，同时检查一下节点的平衡因子更新是否出现问题
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);
}3 完整实现代码
#include <iostream>
#include <assert.h>
using namespace std;
template <class K,class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;//平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{ }
};
template <class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//插入函数
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
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--;
}
else
{
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)
{
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;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
subL->_bf = 0;
parent->_bf = 0;
}
//左单旋
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 (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subR;
}
else
{
pParent->_right = subR;
}
subR->_parent = pParent;
}
subR->_bf = 0;
parent->_bf = 0;
}
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_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->_right);
RotateL(parent);
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);
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
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;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
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;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 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);
}
private:
Node* _root=nullptr;
};以上就是AVL树的实现，其中插入操作是重难点，掌握了旋转原理和操作对掌握红黑树有重要作用
希望对您有所帮助，如果这篇文章对你有用，可以点点赞哦，你的支持就是我写下去的动力，后续会不断地分享知识。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
28
0- 0
已为社区贡献5条内容
所有评论(0)