C++之AVL树的简单实现
一、AVL树的产生背景
在普通二叉树中我们有可能会遇到下面这类极端情况：
上面的极端情况会导致二叉树退化为链表、导致查询 / 插入 / 删除效率骤降。
为了解决这个问题，苏联数学家 Adelson-Velsky 和 Landis 于1962 年提出AVL树这个概念
二、AVL树的介绍
AVL树是一个自平衡二叉树，其满足任意节点的左右子树高度差（称为 “平衡因子”）的绝对值 ≤ 1。平衡因子=右子树高度-左子树高度。（当然也可以是左子树高度-右子树高度，这里用右-左讲解）
通过平衡因子的约束，AVL树能够有效维持二叉树的查询 / 插入 / 删除效率。
三、AVL树的容器模板
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>& x)
:_key(x)
,_right(nullptr)
,_left(nullptr)
,_parent(nullptr)
,_bf(0)
{ }
pair<K,V> _key;//pair存储键链值
AVLTreeNode* _right;
AVLTreeNode* _left;
AVLTreeNode* _parent;
int _bf;//平衡因子
};
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K,V> Node;
private:
Node* _root=nullptr;
};
除了常见的左右孩子指针以外，AVL树中还需要指向父亲的指针、当前节点的平衡因子、当前节点存储的pair键链值_key。
对于pair<K,V>类型的_key来说，主要参与比较与计算的就是键值_key.first，而_key.second作为链值通常不会参与计算，而是作为链值配套的值共同存储在节点中。
_key.second不显示初始化会调用默认初始化。
四、AVL部分功能的实现
1、插入
AVL树的插入基本遵循二叉树的插入规则，但是由于存在着平衡因子的约束，当插入过程中AVL树的平衡因子不满足绝对值小于等于1的时候就需要通过旋转操作来维护AVL树的结构。
bool insert(const pair<K,V>& key)
{
//先考虑树为空情况下的插入
if (_root == nullptr)
{
_root = new Node(key); return true;
}
Node* cur = _root;
Node* father = nullptr;
while (cur)
{
if (key.first > cur->_key.first)
{
father = cur;
cur = cur->_right;
}
else if (key.first < cur->_key.first)
{
father = cur;
cur = cur->_left;
}
else return false;
}
cur = new Node(key);//创建新节点
cur->_parent = father;
if (cur->_key.first > father->_key.first)
{
father->_right = cur;
}
else if (cur->_key.first < father->_key.first)
{
father->_left = cur;
}
else assert(false);
while (father)//插入完成后向上继续更新平衡因子
{
if (cur == father->_left)
{
father->_bf--;
}
else
{
father->_bf++;
}
if (father->_bf == 0) break;//平衡因子从-1/1变回0表明树的高度没有变，直接结束更新
else if (father->_bf == 1 || father->_bf == -1)
{
//当平衡因子为-1/1的时候，继续向上更新
cur = father;
father = father->_parent;
}
else if (father->_bf == 2 || father->_bf == -2)
{
//开始旋转操作,旋转操作是跟随平平衡因子向上走的，father会自然走到合适的地方开始旋转
if(father->_bf==-2&&cur->_bf==-1)
{
RotateR(father); //右单旋
}
else if (father->_bf == 2 && cur->_bf==1)
{
RotateL(father); //左单旋
}
else if (father->_bf == 2 && cur->_bf == -1)
{
RotateRL(father); //左右双旋
}
else if (father->_bf == -2 && cur->_bf == 1)
{
RotateLR(father); //右左双旋
}
}
else assert(false);//正规的红黑树在插入的时候不会出现平衡因子绝对值大于2的情况
}
}
在插入完成后，平衡因子向上更新的时候：
1、如果当前节点的平衡因子为0，则说明当前（子）树的高度并未发生改变，更新停止。
2、如果当前节点的平衡因子为-1/1，则说明当前（子）树的高度差发生改变，需要继续向上更新。
3、如果当前节点的平衡因子为-2/2，则说明当前（子）树并不符合AVL树的规则，需要进行旋转操作，然后继续向上更新。
4、如果当前节点的平衡因子的绝对值大于2，则说明该树原本就不是AVL树，插入操作无效。
5、如果不断更新到根，且根的平衡因子为-1/1也更新正常结束。
2、旋转操作
右单旋：
上图中就是两个经典的需要右旋的情况，但总体上可以抽象看成下面这种情况：
通过上面图的观察，我们可以得到实现右旋的前提是：father->_bf==-1&&cur->_bf==-1。
在翻转的时候需要注意以下情况：
1、我们以cur为轴进行右旋，并将cur->_left插到father的左孩子处，将cur的右孩子更新为father
2、存在father->_right==nullptr的情况，对于该情况需要特殊考虑防止空指针解引用。
3、旋转的时候别忘了更新father->_parent和cur->_right->_parent的指向。
4、需要考虑father是否为AVL树的根节点。如果是，cur->_parent置空；如果不是，则需要再判断father这个子树是father->_parent的左孩子还是右孩子，并以此分别处理father->_parent对cur的指向。
5、右旋完成后被调整的树会恢复平衡，cur和father的平衡因子都会变为0。
void RotateR( Node* father) //右单旋
{
Node* cu = father->_left;
Node* cuR = cu->_right;
Node* fatherFather = father->_parent;
cu->_right = father;
father->_parent = cu;
father->_left = cuR;
if(cuR)
cuR->_parent = father;
if (fatherFather)
{
cu->_parent = fatherFather;
if (fatherFather->_left == father)
{
fatherFather->_left = cu;
}
else if (fatherFather->_right == father)
{
fatherFather->_right = cu;
}
}
else
{
_root = cu;
cu->_parent = nullptr;
}
father->_bf = cu->_bf = 0;
}
左单旋：
左旋情况的抽象图：
当father->_bf==2&&cur->_bf==1的时候进行左旋操作。
左旋的操作与右旋的思考逻辑大体上相同，仅需要在一些细节问题上与右旋保持区分，明了右旋后便很简单，这里便不再赘述。
void RotateL( Node* father)//左单旋
{
Node* cu = father->_right;
Node* cuL = cu->_left;
Node* fatherFather = father->_parent;
cu->_left = father;
father->_parent = cu;
father->_right = cuL;
if (cuL)
cuL->_parent = father;
if (fatherFather)
{
cu->_parent = fatherFather;
if (fatherFather->_left == father)
{
fatherFather->_left = cu;
}
else if (fatherFather->_right == father)
{
fatherFather->_right = cu;
}
}
else
{
_root = cu;
cu->_parent = nullptr;
}
father->_bf = cu->_bf = 0;
}
左右双旋：
上面两种情况单靠右旋无法平衡AVL树，要解决这个问题我们需要先以5为根进行左旋，再以10为根进行右旋。
对于左右双旋的情况可以抽象成下面的图示：
注意事项：
1、使用左右双旋的条件是father->_bf==-2&&subL->_bf==1，左右双旋可以直接复用左单旋和右单旋的函数
2、需要考虑subLR的平衡因子的三种情况（1/-1/0），这虽然不影响旋转但会影响平衡因子的更新。
3、由于在旋转的过程中会改变suLR的平衡因子，故需要提前记录suLR的平衡因子
void RotateLR( Node* father)
{
Node* cu = father->_left;
Node* cuR = cu->_right;
int bf = cuR->_bf;
RotateL(cu);
RotateR(father);
if (bf == 0)
{
father->_bf = 0;
cu->_bf = 0;
cuR->_bf = 0;
}
else if (bf == -1)
{
father->_bf = 1;
cu->_bf = 0;
cuR->_bf = 0;
}
else if (bf == 1)
{
father->_bf = 0;
cu->_bf = -1;
cuR->_bf = 0;
}
}
右左双旋：
右左双旋的抽象图如下：
右左双旋的前提是：father->_bf==2&&subR->_bf==-1
右左双旋的逻辑与左右双旋很类似，掌握左右双旋的实现逻辑后便能很快的掌握右左双旋，这里也不再赘述。
void RotateRL(Node* father)
{
Node* cu = father->_right;
Node* cuL = cu->_left;
int bf = cuL->_bf;
RotateR(cu);
RotateL(father);
if (bf == 0)
{
father->_bf = 0;
cu->_bf = 0;
cuL->_bf = 0;
}
else if (bf == -1)
{
father->_bf = 0;
cu->_bf = 1;
cuL->_bf = 0;
}
else if (bf == 1)
{
father->_bf = -1;
cu->_bf = 0;
cuL->_bf = 0;
}
}
2、AVL树的平衡性检测
我们不通过平衡因子来检查AVL是否平衡，因为存在平衡因子更新出错的情况。我们通过对右左子树高度差的检查来判断是否平衡。
要求出一个（子）树的高度，我们可以使用递归。
int Height(Node* root)
{
if (root == nullptr) return 0;
int LeftHeight = Height(root->_left);
int RightHeight = Height(root->_right);
int height = LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
//总高度是max(左高,右高)+1
return height;
}
在检测平衡性的过程中主要看两点：
1、右左树的高度差是否异常
2、当前节点的平衡因子是否异常
bool IsBalanceTree(Node* root)
{
if (root == nullptr) return true;
int LeftHeight = Height(root->_left);
int RightHeight = Height(root->_right);
int bf = RightHeight - LeftHeight;
if (abs(bf) >= 2 )
{
cout << "高度异常" << endl;
return false;
}
if (bf!=root->_bf)
{
cout << "平衡因子异常" << endl;
return false;
return IsBalanceTree(root->_left)&&IsBalanceTree(root->_right);
}
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
17
0- 0
已为社区贡献4条内容
所有评论(0)