二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在 1962 年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称为 AVL 树,其实就是一颗 平衡的二叉排序树 ,解决了二叉查找树的不平衡问题,即斜树。
AVL树或者是一颗空树,或者是具有下列性质的二叉搜索树:
举个例子,下图就是一颗典型的 AVL 树,每个节点旁边都标注了平衡因子:
上面是一颗典型的平衡二叉树,首先它是一颗二叉排序树,其次每一个结点的平衡因子都是 -1,0,1 三个数当中的一个。
红色的数字为结点的平衡因子,对于任意一个叶子结点而言,其左右孩子都为空,左子树的深度为 0 ,右子树的深度为 0 ,所以 AVL树当中的叶子结点的平衡因子都是 0 ;
其他结点的平衡因子同样通过 右子树深度减去左子树深度 可以求得,比如结点 3 的 左子树深度为 2,右子树深度为1 ,则平衡因子为 1 − 2 = − 1 1 - 2 = -1 1−2=−1。
如果一棵二叉搜索树是高度平衡的,它就是 AVL 树。如果它有 n 个结点,其高度可保持在 O ( l o g n ) O(logn) O(logn),搜索时间复杂度 O ( l o g n O(log n O(logn)。
再来看看不平衡的情况,如下面这颗树:
上图中就是不平衡的二叉排序树,非 AVL树 。结点 5 的平衡因子为 -2,该平衡因子是结点 5 右子树深度 2 减去左子树深度 4 所得;
我们要学习的就是将这种不平衡的二叉搜索树转化为 AVL树。
2. AVL树的结点我们直接按照 KV 模型来构造 AVL 树,需要把结点定义为 三叉链结构,并在每个结点当中引入平衡因子(右子树高度-左子树高度)。
对于结点的构造函数,由于新构造结点的左右子树均为空树,所以只需要将新构造结点的平衡因子初始设置为 0 即可。
代码示例
templatestruct AVLTreeNode
{// 存储的键值对
pair_kv;
// 三叉链
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
// 平衡因子(balance factor)
int _bf; // 右子树高度 - 左子树高度
// 构造函数
AVLTreeNode(const pair& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
};
3. AVL树的插入对平衡二叉树的插入操作而言,其本质上比二叉搜索树的插入操作多了一个平衡操作,解决了二叉搜索树插入操作可能出现的斜树,不平衡问题。
那么 AVL 树的插入过程可以分为两步:
当 AVL 树插入一个新结点以后,需要更新插入结点的祖先的平衡因子,因为新结点(也就是叶子结点)的平衡因子为 0,但是它影响的是它的父亲,它父亲的父亲…,所以要更新到祖先结点。
所以我们要从新增结点开始,往上沿着祖先路径更新,那么更新的规则如下:
+1
即可-1
即可为什么呢?因为平衡因子的计算方法是:右子树高度 - 左子树高度,如果插入在右边,那么最后的结果肯定是要++
,反之,则--
。
当 parent 的平衡因子更新完以后,可能出现三种情况:0,正负 1,正负 2。
(1)parent 的平衡因子为 0
如果 parent 的平衡因子为 0,说明插入之前 parent 的平衡因子为正负 1,插入后被调整成 0,此时满足 AVL 树的性质,则插入成功。
如下图所示,插入后使得 parent 左右子树的高度相等了,此操作并没有改变以 parent 为根结点的子树的高度,从而不会影响 parent 的父结点的平衡因子,因此无需继续往上更新平衡因子。
(2)如果 parent 的平衡因子为正负 1
如果 parent 的平衡因子为正负 1,说明插入前 parent 的平衡因子一定为 0,插入后被更新成正负 1。
如下图所示,当新增一个结点以后,parent 的平衡因子从 0 变成了 1,说明新结点的插入使得 parent 的右子树增高了,即改变了以 parent 为根结点的子树的高度,从而会影响 parent 的父结点的平衡因子,因此需要继续往上更新平衡因子。
如下图所示,当新增一个结点以后,parent 的平衡因子从 0 变成了 -1,说明新结点的插入使得 parent 的左子树增高了,即改变了以 parent 为根结点的子树的高度,从而会影响 parent 的父结点的平衡因子,因此需要继续往上更新平衡因子。
进而引出了下面的第 3 种情况。
(3)如果 parent 的平衡因子为正负 2
如果 parent 的平衡因子为 -2,此时 parent 结点的左右子树高度之差的绝对值已经超过 1 了,则 parent 的平衡因子违反平衡树的性质,那么就停止更新,需要对其进行旋转处。
如果 parent 的平衡因子为 2,此时 parent 结点的左右子树高度之差的绝对值已经超过 1 了,则 parent 的平衡因子违反平衡树的性质,那么就停止更新,需要对其进行旋转处。
可以看到,当 parent 的平衡因子为正负 2 时,cur 的平衡因子必定是正负 1 而不会是 0。
🍑 插入函数的实现上面我们分析了,如果在更新平衡因子的过程当中,出现了平衡因子为正负 2 的结点,此时需要对 以该结点为根结点的树 进行旋转处理(待会儿再讲旋转)。
我们定义一个cur
用来表示 新增结点,定义一个parent
用来表示 新增结点的父亲结点。
那么我们更新平衡因子时,第一个要更新的就是 parent 结点的平衡因子,更新完 parent 结点的平衡因子后,若是需要继续往上进行平衡因子的更新,那么要执行以下操作:
if (parent->_bf == 1 || parent->_bf == -1)
{cur = cur->_parent; // cur指向了它的父亲
parent = parent->_parent; // 它的父亲指向了它的祖先
}
可以看到,我们之所以将 AVL 树结点的结构设置为三叉链结构,是因为我们可以很方便的通过父指针找到其父结点,进而对其平衡因子进行更新。
而当 parent 的平衡因子为正负 2 时,我们需要对其进行旋转操作,当旋转完成以后,就无需继续往上更新平衡因子了,即树的高度没有发生变化,也就不会影响其父结点的平衡因子了。
if (parent->_bf == 2 || parent->_bf == -2)
{// 旋转的四种处理方式
// 1.左单旋
// 2.右单旋
// 3.左右双旋
// 4.右左双旋
// 当旋转完成以后,直接跳出
break;
}
代码示例
public:
// 插入函数
bool Insert(const pair& kv)
{// 如果AVL树是空树,把插入节点直接作为根节点
if (_root == nullptr)
{ _root = new Node(kv);
_root->_bf = 0;
return true;
}
// 1.按照二叉搜索树的规则插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{ if (cur->_kv.first< kv.first) // 待插入节点的key值大于当前节点的key值
{ // 往右子树走
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first >kv.first) // 待插入节点的key值小于当前节点的key值
{ // 往左子树走
parent = cur;
cur = cur->_left;
}
else // 待插入节点的key值等于当前节点的key值
{ return false; // 插入失败,返回false
}
}
// 2.当循环结束,说明cur找到了空的位置,那么就插入
cur = new Node(kv); // 构造一个新节点
if (parent->_kv.first< kv.first) // 如果新节点的key值大于当前parent节点的key值
{ // 就把新节点链接到parent的右边
parent->_right = cur;
}
else // 如果新节点的key值小于当前parent节点的key值
{ // 就把新节点链接到parent的左边
parent->_left = cur;
}
cur->_parent = parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链)
// 3.更新平衡因子,如果出现不平衡,则需要进行旋转
while (parent) // 最远要更新到根节点去
{ if (cur == parent->_right) // 如果cur插在parent的右边,说明parent的右子树增高
{ parent->_bf++; // 那么parent的平衡因子要++
}
else // 如果cur插在parent的左边,说明parent的左子树增高
{ parent->_bf--; // 那么parent的平衡因子要--
}
// 判断是否更新结束,或者是否需要进行旋转
if (parent->_bf == 0) // 如果parent的bf等于0,说明左右子树高度一致,就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了)
{ // 高度不变,更新结束
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新平衡因子(插入节点导致某一边变高了,说明parent所在的子树高度改变了)
{ // 子树的高度变了,就要继续往上更新祖先
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 说明插入节点导致本来高的一边又变高了,子树不平衡了,那么此时需要做旋转处理
{ // 旋转的四种处理方式
// 1.左单旋
// 2.右单旋
// 3.左右双旋
// 4.右左双旋
// 旋转完成,跳出
break;
}
else
{ // 如果程序走到了这里,说明在插入节点之前AVL树就存在不平衡的子树,也就是存在平衡因子 >= 2的节点
// 所以这里加一个断言进行处理
assert(false);
}
}
// 插入成功,返回true
return true;
}
4. AVL树的旋转如果在一棵原本是平衡的 AVL 树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。
根据节点插入位置的不同,AVL 树的旋转分为四种:
其实我们只要搞懂 LL 和 RR 就好了,因为 LR 和 RL 都是由它们演变而来的。
不管是什么旋转,都必须满足两点原则:
下面是一个 AVL 树的抽象图,长方形条代表的是子树,h
表示 a,b,c 三颗子树的高度。
现在我们在 c 子树的中插入一个新结点,那么此时 c 子树的高度就变成了 h + 1,同时结点 60 的平衡因子为 1,结点 30 的平衡因子为 2,此时右边的高度大于左边的高度,需要进行左单旋。
左单旋的步骤如下:
左单旋图如下所示:
经过旋转以后,它们的平衡因子就发生了变化:
这样旋转以后还满足二叉搜索树的性质吗?当面满足,原因如下:
什么时候需要用到左旋操作呢?可以看到,当 parent 的平衡因子为 2,cur 的平衡因子为 1 时,需要进行左单旋。并且经过左单旋后,树的高度没有发生变化,所以左单旋后无需继续往上更新平衡因子。
左单旋动图演示:
可以看到,我们在 32 的右边插入一个值为 35 的新节点,那么此时 32 的平衡因子从 0 变成了 1,29 的平衡因子从 1 变成了 2,出现了右边高,左边低的局面,所以需要进行左单旋
代码示例
private:
// 左单旋(右边高需要左单旋)
void RotateL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* ppNode = parent->_parent; // 先保存parent的parent
// 1.建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL) // 如果subRL节点不为空,那么要更新它的parent
{ subRL->_parent = parent;
}
// 2.建立subR和parent之间的关系
subR->_left = parent;
parent->_parent = subR;
// 3.建立ppNode和subR之间的关系(分情况讨论parent是整颗树的根,还是局部子树)
if (parent == _root) // 当parent是根节点时
{ _root = subR; // subR就变成了新的根节点
_root->_parent = nullptr; // 根节点的的parent为空
}
else // 当parent是整个树的局部子树时
{ if (parent == ppNode->_left) // 如果parent在ppNode的左边
{ ppNode->_left = subR; // 那么subR就是parent的左子树
}
else // 如果parent在ppNode的右边
{ ppNode->_right = subR; // 那么subR就是parent的右子树
}
subR->_parent = ppNode; // subR的parent还要指向ppNode
}
// 更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
还有一点需要注意,如果在旋转前 parent(30) 就是树的根,那么此时只需要更新根结点为 subR(60)即可。
如果 parent(30) 只是整颗树局部的一颗子树,那么此时就需要看 30 是它父亲的左子树还是右子树,然后再和 subR 链接起来,如下图所示:
下面是一个 AVL 树的抽象图,长方形条代表的是子树,h
表示 a,b,c 三颗子树的高度。
现在我们在 a 子树的中插入一个新结点,那么此时 a 子树的高度就变成了 h + 1,同时结点 60 的平衡因子为 -2,结点 30 的平衡因子为 -1,此时左边的高度大于右边的高度,需要进行右单旋。
右单旋的步骤如下:
右单旋图如下所示:
经过旋转以后,它们的平衡因子就发生了变化:
这样旋转以后还满足二叉搜索树的性质吗?当面满足,原因如下:
什么时候需要用到右旋操作呢?可以看到,当 parent 的平衡因子为 -2,cur 的平衡因子为 -1 时,需要进行右单旋。并且经过右单旋后,树的高度没有发生变化,所以右单旋后无需继续往上更新平衡因子。
右单旋动图演示:
可以看到,我们在 9 的左边插入一个值为 5 的新节点,那么此时 9 的平衡因子从 0 变成了 -1,11 的平衡因子从 -1 变成了 -2,出现了左边高,右边低的局面,所以需要进行右单旋
代码示例
private:
// 右单旋(左边高就右单旋)
void RotateR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
// 1.建立parent和subLR之间的关系
parent->_left = subLR;
if (subLR) // 如果subLR节点不为空,那么要更新它的parent
{ subLR->_parent = parent;
}
// 2.建立subL和parent之间的关系
subL->_right = parent;
parent->_parent = subL;
// 3.建立ppNode和subL之间的关系(分情况讨论parent是整颗树的根,还是局部子树)
if (parent == _root) // 当parent是根节点时
{ _root = subL; // subL就变成了新的根节点
_root->_parent = nullptr; // 根节点的的parent为空
}
else // 当parent是整个树的局部子树时
{ if (parent == ppNode->_left) // 如果parent在ppNode的左边
{ ppNode->_left = subL; // 那么subL就是parent的左子树
}
else // 如果parent在ppNode的右边
{ ppNode->_right = subL; // 那么subL就是parent的右子树
}
subL->_parent = ppNode; // subR的parent还要指向ppNode
}
// 更新平衡因子
parent->_bf = 0;
subL->_bf = 0;
}
需要注意,如果在旋转前 parent(60) 就是树的根,那么此时只需要更新根结点为 subL(30)即可。
如果 parent(60) 只是整颗树局部的一颗子树,那么此时就需要看 60 是它父亲的左子树还是右子树,然后再和 subL 链接起来。
🍑 左右双旋下面是一个 AVL 树的抽象图,长方形条代表的是子树,h
表示 a 和 d 两颗子树的高度,h-1
代表 b 和 c 两颗子树的高度。
现在我们在 b 子树的中插入一个新结点,那么此时 b 子树的高度就变成了 h,同时结点 60 的平衡因子变成了 -1,结点 30 的平衡因子变成了 1,结点 90 的平衡因子变成了 -2,此时如果单纯的以结点 90 为旋转点进行左单旋或者右单旋以后,那么仍然不是 AVL 树,所以需要采取左右双旋的方式。
注意:在 b 子树当中新增结点,或是在 c 子树当中新增结点,均会引发左右双旋,这里以在 b 子树当中新增结点为例。
左右双旋的步骤如下:
(1)以 30 为旋转点进行左单旋
(2)以 90 为旋转点进行右单旋
左右双旋后,实际上就是让 subLR 的左子树和右子树,分别作为 subL 和 parent 的右子树和左子树,再让 subL 和 parent 分别作为 subLR 的左右子树,最后让 subLR 作为整个子树的根
这样旋转以后还满足二叉搜索树的性质吗?当面满足,原因如下:
左右双旋后,平衡因子的更新随着 subLR 原始平衡因子的不同分为以下三种情况:
(1)当 subLR 原始平衡因子是 -1 时,左右双旋后 parent、subL、subLR 的平衡因子分别更新为 1、0、0
(2)当 subLR 原始平衡因子是 1 时,左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、-1、0
(3)当 subLR 原始平衡因子是 0 时(说明 subLR 为新增结点),左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、0、0
可以看到,经过左右双旋后,树的高度没有发生变化,所以左右双旋后无需继续往上更新平衡因子。
代码示例
private:
// 左右双旋(先左单旋,再右单旋)
void RotateLR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
// 1.先以subL为旋转点进行左单旋
RotateL(parent->_left);
// 2.再以parent为旋转点进行右单旋
RotateR(parent);
// 3.更新平衡因子
if (bf == 0)
{ parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{ parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{ parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{ // 如果走到了这里,说明subLR的平衡因子在旋转前就有问题
assert(false);
}
}
🍑 右左双旋下面是一个 AVL 树的抽象图,长方形条代表的是子树,h
表示 a 和 d 两颗子树的高度,h-1
代表 b 和 c 两颗子树的高度。
现在我们在 c 子树的中插入一个新结点,那么此时 c 子树的高度就变成了 h,同时结点 60 的平衡因子变成了 1,结点 00 的平衡因子变成了 -1,结点 30 的平衡因子变成了 -2,此时如果单纯的以结点 30 为旋转点进行左单旋或者右单旋以后,那么仍然不是 AVL 树,所以需要采取右左双旋的方式。
注意:在 b 子树当中新增结点,或是在 c 子树当中新增结点,均会引发右左双旋,这里以在 c 子树当中新增结点为例。
右左双旋的步骤如下:
(1)以 90 为旋转点进行右单旋
(2)以 30 为旋转点进行左单旋
右左双旋后,实际上就是让 subRL 的左子树和右子树,分别作为 parent 和 subR 的右子树和左子树,再让 parent 和 subR 分别作为 subRL 的左右子树,最后让 subRL 作为整个子树的根。
这样旋转以后还满足二叉搜索树的性质吗?当面满足,原因如下:
右左双旋后,平衡因子的更新随着 subLR 原始平衡因子的不同分为以下三种情况:
(1)当 subRL 原始平衡因子是 1 时,左右双旋后 parent、subR、subRL 的平衡因子分别更新为 -1、0、0
(2)当 subRL 原始平衡因子是 -1 时,左右双旋后 parent、subR、subRL 的平衡因子分别更新为 0、1、0
(3)当 subRL 原始平衡因子是 0 时(说明 subRL为新增结点),左右双旋后 parent、subR、subRL 的平衡因子分别更新为0、0、0
可以看到,经过右左双旋后,树的高度没有发生变化,所以右左双旋后无需继续往上更新平衡因子。
代码示例
private:
// 右左双旋(先右单旋,再左单旋)
void RotateRL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
// 1.先以subR为旋转点进行右单旋
RotateR(parent->_right);
// 2.再以parent为旋转点进行左单旋
RotateL(parent);
// 3.更新平衡因子
if (bf == 0)
{ subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{ subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{ subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else
{ // 如果走到了这里,说明subRL的平衡因子在旋转前就有问题
assert(false);
}
}
🍑 总结假如以 parent 为根的子树不平衡,即 parent 的平衡因子为 2 或者 -2,分以下情况考虑
旋转完成后,原 parent 为根的子树个高度降低,已经平衡,不需要再向上更新。
6. AVL树的删除平衡二叉树的删除操作与插入操作类似,先执行标准的 BST 删除操作(可以参考文章: 什么是二叉查找树),然后进行相应的平衡操作。
主要是三个大思路:
只不过与二叉搜索树的删除不同的是,删除节点后的平衡因子需要不断更新,最差情况下一直要调整到根节点的位置。
下面简单讲解一下删除的算法思想吧。
🍑 算法思想我们以删除一个结点w
为例进行说明平衡二叉树删除操作的具体算法步骤:
w
执行标准的二叉搜索树的删除操作;w
开始,向上回溯,找到第一个不平衡的结点z
(即平衡因子不是 -1,0 或 1 的结点),设y
为结点z
的高度最高的孩子结点;x
是结点y
的高度最高的孩子结点。z
为根结点的子树进行平衡操作,其中x
、y
、z
可以的位置有四种情况,BST 删除操作之后的平衡操作也就处理以下四种情况:y
是z
的左孩子,x
是y
的左孩子 (Left Left ,LL );y
是z
的左孩子,x
是y
的右孩子 (Left Right ,LR );y
是z
的右孩子,x
是y
的右孩子 (Right Right ,RR );y
是z
的右孩子,x
是y
的左孩子 (Right Right ,RL );这里的四种情况与插入操作一样,但需要注意的是,插入操作仅需要对以z
为根的子树进行平衡操作;而平衡二叉树的删除操作就不一样,先对以z
为根的子树进行平衡操作,之后可能需要对z
的祖先结点进行平衡操作,向上回溯直到根结点。
我们已删除下图中的结点 32 为例进行说明。
第一步:由于 32 结点为叶子结点,直接删除,并保存删除结点的父节点 17 。
第二步:从节点 17 向上回溯,找到第一个不平衡结点 44 ,并找到不平衡结点的左右孩子中深度最深的结点 78 (即 y );以及 y 的孩子结点当中深度最深的结点 50 (即 x )。 发现为 RL 的情况。
第三步:对结点 78 进行右旋操作
第四步:对结点 44 进行左旋操作
我们以删除下图中的结点 80 为例进行说明。
第一步,由于结点 80 为叶子结点,则直接删除,并保存结点 80 的父结点 78 。
第二步:从结点 78 开始寻找第一个不平衡结点,发现就是结点 78 本身(即结点 z ),找到结点 78 深度最深的叶子结点 60 (即结点 y ),以及结点 y 的深度最深的叶结点 55 (即结点 x )。即 LL 的情况。
第三步:右旋结点 78
第四步:从旋转后的返回的新的根结点 60 向上回溯(这里就和平衡二叉树的插入操作有别了奥,平衡二叉树的插入操作仅对第一个不平衡结点的子树进行平衡操作,而AVL的删除需要不断地回溯,直到根结点平衡为止 ),判断是否还有不平衡结点,发现整棵树的根结点 50 为第一个不平衡结点,找到对应的 y 结点 25 和 x 结点 10 。同样是 LL 的情况。
第五步:对 z 结点 50 进行右旋操作。
关于左旋与右旋操作,以及平衡因子的计算与之前讲的文章( 什么是二叉查找树)中的实现是一致的,我们直接看 AVL 树删除操作的实现代码:
代码示例
// 删除函数
bool Erase(const K& key)
{//用于遍历二叉树
Node* parent = nullptr;
Node* cur = _root;
//用于标记实际的删除结点及其父结点
Node* delParentPos = nullptr;
Node* delPos = nullptr;
while (cur)
{ if (key< cur->_kv.first) //所给key值小于当前结点的key值
{ //往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (key >cur->_kv.first) //所给key值大于当前结点的key值
{ //往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //找到了待删除结点
{ if (cur->_left == nullptr) //待删除结点的左子树为空
{if (cur == _root) //待删除结点是根结点
{_root = _root->_right; //让根结点的右子树作为新的根结点
if (_root)
_root->_parent = nullptr;
delete cur; //删除原根结点
return true; //根结点无祖先结点,无需进行平衡因子的更新操作
}
else
{delParentPos = parent; //标记实际删除结点的父结点
delPos = cur; //标记实际删除的结点
}
break; //删除结点有祖先结点,需更新平衡因子
}
else if (cur->_right == nullptr) //待删除结点的右子树为空
{if (cur == _root) //待删除结点是根结点
{_root = _root->_left; //让根结点的左子树作为新的根结点
if (_root)
_root->_parent = nullptr;
delete cur; //删除原根结点
return true; //根结点无祖先结点,无需进行平衡因子的更新操作
}
else
{delParentPos = parent; //标记实际删除结点的父结点
delPos = cur; //标记实际删除的结点
}
break; //删除结点有祖先结点,需更新平衡因子
}
else //待删除结点的左右子树均不为空
{//替换法删除
//寻找待删除结点右子树当中key值最小的结点作为实际删除结点
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{minParent = minRight;
minRight = minRight->_left;
}
cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key
cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value
delParentPos = minParent; //标记实际删除结点的父结点
delPos = minRight; //标记实际删除的结点
break; //删除结点有祖先结点,需更新平衡因子
}
}
}
if (delParentPos == nullptr) //delParentPos没有被修改过,说明没有找到待删除结点
{ return false;
}
//记录待删除结点及其父结点(用于后续实际删除)
Node* del = delPos;
Node* delP = delParentPos;
//更新平衡因子
while (delPos != _root) //最坏一路更新到根结点
{ if (delPos == delParentPos->_left) //delParentPos的左子树高度降低
{ delParentPos->_bf++; //delParentPos的平衡因子++
}
else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低
{ delParentPos->_bf--; //delParentPos的平衡因子--
}
//判断是否更新结束或需要进行旋转
if (delParentPos->_bf == 0)//需要继续往上更新平衡因子
{ //delParentPos树的高度变化,会影响其父结点的平衡因子,需要继续往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
}
else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束
{ break; //delParent树的高度没有发生变化,不会影响其父结点及以上结点的平衡因子
}
else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转(此时delParentPos树已经不平衡了)
{ if (delParentPos->_bf == -2)
{if (delParentPos->_left->_bf == -1)
{Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
RotateR(delParentPos); //右单旋
delParentPos = tmp; //更新根结点
}
else if (delParentPos->_left->_bf == 1)
{Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点
RotateLR(delParentPos); //左右双旋
delParentPos = tmp; //更新根结点
}
else //delParentPos->_left->_bf == 0
{Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
RotateR(delParentPos); //右单旋
delParentPos = tmp; //更新根结点
//平衡因子调整
delParentPos->_bf = 1;
delParentPos->_right->_bf = -1;
break; //更正
}
}
else //delParentPos->_bf == 2
{if (delParentPos->_right->_bf == -1)
{Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点
RotateRL(delParentPos); //右左双旋
delParentPos = tmp; //更新根结点
}
else if (delParentPos->_right->_bf == 1)
{Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
RotateL(delParentPos); //左单旋
delParentPos = tmp; //更新根结点
}
else //delParentPos->_right->_bf == 0
{Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
RotateL(delParentPos); //左单旋
delParentPos = tmp; //更新根结点
//平衡因子调整
delParentPos->_bf = -1;
delParentPos->_left->_bf = 1;
break; //更正
}
}
//delParentPos树的高度变化,会影响其父结点的平衡因子,需要继续往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
//break; //error
}
else
{ assert(false); //在删除前树的平衡因子就有问题
}
}
//进行实际删除
if (del->_left == nullptr) //实际删除结点的左子树为空
{ if (del == delP->_left) //实际删除结点是其父结点的左孩子
{ delP->_left = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
else //实际删除结点是其父结点的右孩子
{ delP->_right = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
}
else //实际删除结点的右子树为空
{ if (del == delP->_left) //实际删除结点是其父结点的左孩子
{ delP->_left = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
else //实际删除结点是其父结点的右孩子
{ delP->_right = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
}
delete del; //实际删除结点
return true;
}
7. AVL树的遍历中序遍历和二叉树的中序实现一样,只不过因为中序是递归遍历,涉及到传参,所以需要写一个子函数。
代码示例
private:
// 中序遍历(子函数)
void _InOrder(Node* root)
{if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_kv.first<< " ";
_InOrder(root->_right);
}
public:
// 中序遍历
void InOrder()
{_InOrder(_root);
cout<< endl;
}
8. AVL树的查找AVL树的查找与二叉搜索树一样:
代码示例
public:
// 查找函数
Node* Find(const K& key)
{Node* cur = _root;
while (cur)
{ if (cur->_kv.first< key) // key值大于该结点的值
{ cur = cur->_left; // 在该结点的右子树当中查找
}
else if (cur->_kv.first< key) // key值小于该结点的值
{ cur = cur->_right; // 在该结点的左子树当中查找
}
else // 当前节点的值等于key值
{ return cur; //返回该结点
}
}
return nullptr; //查找失败
}
9. AVL树的高度这里和求二叉树的深度是一样的方式,采用分治的思想:
若为空树,则深度为 0。
若不为空树,则深度 = 左右子树中深度大的值 + 1(为什么要加1呢?因为还有第一层,也就是根节点这一层!)
代码示例
private:
// 求树的高度(子函数)
int _Height(Node* root)
{if (root == nullptr) // 空树高度为0
return 0;
int lh = _Height(root->_left); // 递归计算左子树高度
int rh = _Height(root->_right); // 递归计算右子树高度
return lh >rh ? lh + 1 : rh + 1; // 左树高度或者右树高度大的哪一个,然后再+1,就是整棵树的高度
}
public:
// 树的高度
int Height()
{return _Height(_root);
}
10. AVL树的验证AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分为下面两步:
(1)验证其为二叉搜索树
(2)验证其为平衡树
每个节点子树高度差的绝对值不超过 1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确
检测二叉树是否平衡的代码
private:
// 判断是否为平衡二叉树(子函数)
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 (diff != root->_bf)
{ cout<< root->_kv.first<< "节点平衡因子不符合实际"<< endl;
return false;
}
// pRoot的左和右如果都是AVL树,则该树一定是AVL树
return _IsBalanceTree(root->_left)
&& _IsBalanceTree(root->_right);
}
public:
// 判断是否为平衡二叉树
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}
🍑 数据测试(1)测试一组有序值
// 插入有序值
void TestAVLTree1()
{const int N = 20;
vectorv;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i< N; ++i)
{v.push_back(i);
}
AVLTreet;
for (auto e : v)
{t.Insert(make_pair(e, e));
}
if (t.IsBalanceTree())
{cout<< "AVL树平衡"<< endl;
}
else
{cout<< "AVL树不平衡"<< endl;
}
cout<< "AVL树高度:"<< t.Height()<< endl;
cout<< "中序遍历:";
t.InOrder();
}
运行结果
(2)测试一组随机值
// 插入随机值
void TestAVLTree2()
{const size_t N = 20;
vectorv;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i< N; ++i)
{v.push_back(rand());
}
AVLTreet;
for (auto e : v)
{t.Insert(make_pair(e, e));
}
if (t.IsBalanceTree())
{cout<< "AVL树平衡"<< endl;
}
else
{cout<< "AVL树不平衡"<< endl;
}
cout<< "AVL树高度:"<< t.Height()<< endl;
cout<< "中序遍历:";
t.InOrder();
}
运行结果
优点:
缺点:
时间复杂度分析:
总结:
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享文章:C/C++数据结构(十一)——平衡二叉树(AVL树)-创新互联
链接分享:https://www.cdcxhl.com/article48/djheep.html
成都网站建设公司_创新互联,为您提供商城网站、微信小程序、网站策划、App开发、Google、企业网站制作
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联