概念
AVL树是一种自平衡二叉搜索树(BST),被命名为Adelson-Velskii和Landis树,以它们的发明者们的名字命名。AVL树通过在插入和删除操作后进行自旋操作来保持树的平衡,以确保树的高度始终保持在O(logN)。这样可以减少树的平均长度,提高搜索效率。
一颗二叉搜索树,如果每个根节点的左右子树的高度差的绝对值不超过1,那么这就是一颗AVL树
比如这就是一颗高度不平衡的树:
这是一颗AVL树:
那么我们要如何实现一颗AVL树?
一般的二叉搜索树在插入新节点以及删除节点时,都有可能会破坏树的平衡,所以AVL树需要对插入以及删除接口做修改,每次插入删除时,都要检测一下当前的树时候符合AVL树,如果不符合,要做出相应的调整措施。
实现
插入
限制于AVL树的要求,每个根节点的左右子树高度差绝对值不超过1,我们在此处为AVL树增加一个成员_bf,称为平衡因子(balance factor),其值为左右子树高度的差值,当这个差值的绝对值>=2,就说明这个节点的左右子树不平衡,那么我们就要使用相应的手段调整这棵树。在此处,本博客的平衡因子为 右子树高度 - 左子树高度,这样顺序没有严格要求。
AVL树节点类:
template<class K, class V> struct AVLTreeNode { AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; pair<K, V> _kv; AVLTreeNode(const pair<K, V>& kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) , _kv(kv) {} };
_left
:指向左子树
_right
:指向右子树
_parent
:指向父节点
_bf
:平衡因子
_kv
:存储的键值对
首先,由于平衡因子的限制,我们的AVL树任何一颗高为h + 1的子树只有可能会出现以下三种情况:
也就是,平衡因子为0
,1
,-1
三种情况。
现在对这个AVL树进行插入操作,也就有多种可能,由于平衡因子为1
与-1
的情况是对称的,所以此处先举例平衡因子为-1
的情况:
三种情况分别是:
- 两棵子树等高的情况,在任意一边插入
- 两棵子树不等高的情况,在矮的子树插入
- 两颗子树不等高的情况,在高的子树插入
首先,对于第一种情况,两棵子树等高,在任意一边插入:
对于这颗子树,其会有一颗子树变高,一颗子树不变,更新平衡因子:从_bf = 0变成_bf = 1或_bf = -1,此时平衡因子还处于正常范围内,这颗子树还是一颗AVL树。但是对于这颗子树的父节点,其一边的子树高度增加,所以还要往上影响父节点,往上继续判断。
情况一:_bf = 0变成_bf = 1或_bf = -1,不影响AVL结构,影响父节点
对于第二种情况: 两棵子树不等高的情况,在矮的子树插入:
对于这颗子树,其矮的子树变高了,而且会与另外一颗子树等高,更新平衡因子:从_bf = 1或_bf = -1变成_bf = 0。不影响AVL结构,原先整个子树高度是h + 1,插入节点后并没有影响整颗子树的高度,所以对于这个子树的父节点,不会受到影响。
情况二:_bf = 1或_bf = -1变成_bf = 0,不影响AVL结构,不影响父节点
对于第三种情况:两颗子树不等高的情况,在高的子树插入:
对于这颗子树,其高的子树变得更高了,更新平衡因子:从_bf = 1或_bf = -1变成_bf = 2或_bf = -2。这个插入操作影响了AVL树的结构,此时要立刻调整当前子树,让其平衡。
情况三:_bf = 1或_bf = -1变成_bf = 2或_bf = -2,影响AVL结构,立刻调整子树
那么我们先写出当前的代码逻辑,既然要插入,那么就要先找到合适的位置插入,代码如下:
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); } 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->_left = cur; else parent->_right = cur; cur->_parent = parent; //调整平衡 //...... //...... //...... return true; }
接下来,我先解析以上代码的逻辑:
if (_root == nullptr) { _root = new Node(kv); }
如果我们插入节点时,根节点_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; } }
以上代码,是在找到合适的插入位置,当key大于当前节点cur->_kv.first < kv.first,那么cur就向左寻找,反之向右寻找。如果当前节点值等于key,那么说明该节点已经存在,返回false代表插入失败。当我们的cur为空指针,说明已经找到了插入的节点,此时跳出循环进行插入。
cur = new Node(kv); if (parent->_kv.first > kv.first) parent->_left = cur; else parent->_right = cur; cur->_parent = parent;
到达此处,说明前面已经找到插入的位置了,而parent节点就是插入位置的父亲节点。根据key的大小,来判断插入到左边还是右边,插入完成后,再让新节点的_parent指向parent。
至此我们就完成了插入操作,接下来就要根据一开始推导的三种情况进行调整。
既然我们在parent处插入了节点,那么我们第一步就是更新parent的平衡因子:
如果cur是parent的左子树,那么平衡因子-1
如果cur
是parent
的右子树,那么平衡因子+1
if (cur == parent->_left) parent->_bf--; else parent->_bf++;
更新完平衡因子后,就要判断属于三种情况的哪一种:
if (parent->_bf == 0) { //情况二 } else if (parent->_bf == 1 || parent->_bf == -1) { //情况一 } else if (parent->_bf == 2 || parent->_bf == -2) { //情况三 } else { assert(false); }
如果我们的平衡因子在插入后是0,说明原先平衡因子是1或-1,此操作是两棵子树不等高的情况,在矮的子树插入,即情况二。
如果我们的平衡因子在插入后是1或-1,说明原先平衡因子是0,此操作是两棵子树等高的情况,在任意一边插入,即情况一。
如果我们的平衡因子在插入后是2或-2,说明原先平衡因子是1或-1,此操作是两颗子树不等高的情况,在高的子树插入,即情况三。
如果不是以上情况,说明在插入这个节点之前,就已经违反了AVL树的规则,直接assert退出程序,避免出现更糟糕的错误。
代码实现:
情况一:
_bf = 0
变成_bf = 1
或_bf = -1
,不影响AVL结构,影响父节点
其不会影响自身的AVL结构,所以不用对自生做操作,但是由于其高度增加了,所以有可能会影响其父节点,那么此时我们就要去看看父节点是否平衡。而对于其父节点而言,也必然会是三种情况之一,所以我们只需要一个循环即可:
while (parent) { if (cur == parent->_left) parent->_bf--; else parent->_bf++; if (parent->_bf == 0) { //情况二 } else if (parent->_bf == 1 || parent->_bf == -1) { cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //情况三 } else { assert(false); } }
解析:
while (parent) { //...... }
这个while
循环用于不停的判断父节点的平衡因子,并作出调整,直到某次调整不会影响父节点,或者已经到达根节点了,就退出循环。
parent->_bf--; else parent->_bf++;
这个步骤是在更新父节点的平衡因子。
后续判断当前的父节点属于哪一种情况,并做出相应措施,其中我们已经分析了第一种情况:
else if (parent->_bf == 1 || parent->_bf == -1) { cur = cur->_parent; parent = parent->_parent; }
如果当前的处于情况一,那么此次不需要调整,但是会影响其父节点,所以parent = parent->_parent;
来更新父节点,并进入下一次while循环判断。
情况二:
_bf = 1
或_bf = -1
变成_bf = 0
,不影响AVL结构,不影响父节点
因为其不会影响自己以外的节点,也没有破坏平衡,所以直接跳出while
循环,啥也不用做。
if (parent->_bf == 0) { break; }
情况三:_bf = 1
或_bf = -1
变成_bf = 2
或_bf = -2
,影响AVL结构,立刻调整子树
我们先看到当前的调整总代码:
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 = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //情况三 //调整平衡 //...... //...... //...... } else { assert(false); } }
现在只差情况三了,而情况三比较复杂,我们现在分析一下:
第三种情况如下:
也就是子树不等高的情况下,在高子树插入节点,导致原本高的子树更高了,破坏了平衡。
以左侧为例,我们将高度为h
的子树拆分出来,其一定是是以下情况之一:
为什么一定是这两种情况?高度为h
的子树的两个子树一定是h-1
吗?其实并不是的,我们先看看如果有一颗子树不为h-1
会发生什么:
可以看到,这两种插入的情况,左子树的值分别是-2和0。对于0,此时左子树本身高度既没有变化,也没有破坏AVL结构,根本就不会影响到最高处的节点。对于-2,此时左子树已经破坏了AVL结构,此时应该先对左子树直接调整,处理问题,而不是留到最顶上的节点时,再去调整左子树。因此这两种情况下,循环根本就到不了最顶部的节点,情况三的两棵子树高度一定相等。
也就是以下情况:
对于左侧情况,叫做LL失衡
(L表示left),对于右侧情况,叫做LR失衡
(R表示right)。
与LL失衡
对应的是RR失衡
,我们先解决这两种情况的失衡:
想要解决这两种失衡,就分别要用到左单旋算法
和右单旋算法
。
右单旋
我们先看到右单旋的示意图,再做讲解:
我来解析一下以上过程:
我们在subL节点的左子树插入了一个节点,导致parent失衡,接着我们就要尝试调整节点,让这棵树平衡。
由于subL的右子树subLR高度为h-1,而parent的右子树高度也为h-1,此时我们可以想办法把这两个h-1的等高子树凑到一起去,于是我们把parent的左子树断开,把subL的右子树拿去给parent做左子树,此时parent就得到了等高的两棵子树。也就是第二张图片的情况。
随后,以parent为根的树,总高度为h,而subL的左子树刚好高度也是h-1+1 = h,所以我们可以把parent交给subL做子树,这样subL的两边也就平衡了。而刚刚我们把subL的右子树空出来了,此时可以直接转移,就得到了第三种图片的情况。
这个情况下,我们以subL为根的树是一颗平衡的树,而且平衡因子为0,插入节点前以parent为根的子树,高度为h+1,插入节点且旋转后高度仍为h+1。插入前后高度不变,不会影响父节点,直接跳出循环。
接下来我们完成右单旋的代码:
//右单旋 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 = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } parent->_bf = 0; subL->_bf = 0; }
代码解析:
parent->_left = subLR; if (subLR) subLR->_parent = parent;
此代码完成了parent
与subLR
之间的链接,要注意的是,subLR
有可能是空指针,比如这样:
所以在访问 subLR->_parent
之前,需要先确保subRL
不是空指针。
subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL;
这一段代码完成了subL
与parent
之间的链接,由于parent
可能还有父节点,所以我们先把parent
的父节点ppNode
保存下来,后续完成subL
与ppNode
链接。
if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; }
这一段代码,完成了ppNode与subL之间的链接,但是如果parent原先是_root节点的话,那么ppNode就是空指针,此时直接把_root更新为subR即可。
如果parent不是_root,那么直接进行链接即可,由于不确定parent原先是ppNode的左子树还是右子树,所以链接前需要检测一下。
parent->_bf = 0; subL->_bf = 0;
这段代码则是完成平衡因子的更新,左单旋后,parent
与subL
的平衡因子都变成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 = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } parent->_bf = 0; subR->_bf = 0; }
以下是一个左单旋的示例:
我们现在还有两种失衡没有解决:
对于这种失衡,我们需要用到双旋算法:左右双旋
和右左双旋
。
左右双旋
当AVL树出现LR失衡
,我们就需要用到左右双旋
,LR失衡
又分为以下两种情况:
也就是对subLR
进行了再细分,到底新节点插入了左子树还是右子树。那么我们先展示一下左右双旋的过程:
在
subLR
的左子树插入后旋转:
在
subLR
的右子树插入后旋转:
我来解析一下以上过程:
我们在subLR
节点的右子树插入了一个节点,导致parent
失衡,接着我们就要尝试调整节点,让这棵树平衡。
现在假设我们直接对parent
进行右单旋,我们就会得到:
可以发现,直接右单旋得到的树是不平衡的,subL的左子树高度为h-1,右子树高度为h+1,两者高度差为2。这是由于subLR的高度太高了,当把subLR移交给parent左子树,没有完成降低高度的功能。所以我们要想办法降低移交给parent的子树高度,再进行右单旋。
所以我们把subLR子树的根节点抽离出来,先对subL进行左单旋:
对subL进行左单旋,可以把subLR的左子树抽离出来,并提升subLR的高度。此时再进行右单旋,subLR就会把右子树交给parent。相比于直接进行右单旋,这个过程把subLR抽出来,parent得到的左子树少了一层高度(即subLR这层),所以parent这次没有出现不平衡的问题。
那为什么subLR到达顶部之后,也可以保持稳定呢?
可以看到,在subLR向上走的过程中,分别把左右子树交给了parent和subL,而parent和subL原先都有一个高度为h-1的子树,而subLR旋转过程中移交给parent和subL的子树高度分别是h-1和h-2,它们都低于h-1,移交过程中不会影响subL和parent的高度,而这两个节点最后分别成为了subLR的左右子树,所以subLR的左右子树最后高度一定都是h-1。因此subLR平衡因子一定为0。
现在我们来完成代码:
//左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; //更新平衡因子 }
现在的问题就是,要如何更新平衡因子?
在
subLR
的左子树插入后旋转:
在
subLR
的右子树插入后旋转:
当
subLR
就是新插入的节点:
可以看到,整体上有三种情况,三种情况对应的平衡因子最后都不同,所以我们要分类讨论。三种情况的区别在于:第一种情况subLR
的平衡因子为-1
,第二种情况subLR
的平衡因子为1
,第三种情况subLR
的平衡因子为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 == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } else if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
以下是一个右左双旋示例:
总代码展示
由于插入操作已经可以很好的理解AVL控制平衡的手段了,此处就不讲解erase操作了,总代码如下:
AVLTree.h
:
#pragma once #include <iostream> #include <assert.h> using namespace std; template<class K, class V> struct AVLTreeNode { AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; // balance factor pair<K, V> _kv; AVLTreeNode(const pair<K, V>& kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) , _kv(kv) {} }; 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); } 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->_left = cur; else parent->_right = cur; cur->_parent = parent; while (parent)//最坏情况一直更新到root,此时parent为nullptr { if (cur == parent->_left)//更新平衡因子 parent->_bf--; else parent->_bf++; if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1)//向上查找,检测是否出现不平衡 { cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //旋转 if (parent->_bf == 2 && cur->_bf == 1)//2,1说明右边子树深度阶梯式增加,所以往左旋转 RotateL(parent);//左单旋 else if (parent->_bf == -2 && cur->_bf == -1)//-2,-1说明左边子树深度阶梯式增加,所以往右旋转 RotateR(parent);//右单旋 else if (parent->_bf == -2 && cur->_bf == 1)//-2, 1说明左边子树中间深,先左单旋提高中间节点,再右单旋提高中间节点 RotateLR(parent); else if (parent->_bf == 2 && cur->_bf == -1)//2, -1说明右边子树中间深,先右单旋提高中间节点,再左单旋提高中间节点 RotateRL(parent); else assert(false); break; } else //说明插入前AVL出现了问题,直接报错 { assert(false); } } return true; } //左单旋 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 = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } parent->_bf = 0; subR->_bf = 0; } //右单旋 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 = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } parent->_bf = 0; subL->_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 == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } else if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } } //中序 void InOrder() { _InOrder(_root); cout << "end" << endl; } private: //中序 void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " - "; _InOrder(root->_right); } Node* _root = nullptr; };