欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 汽车 > 时评 > 【C++ 第十三章】AVL 二叉平衡树

【C++ 第十三章】AVL 二叉平衡树

2024/10/24 15:22:27 来源：https://blog.csdn.net/2301_79499548/article/details/141333039  浏览:  次   关键词：【C++ 第十三章】AVL 二叉平衡树

1. AVL树的概念

        普通二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

        因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

即为 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过 1 (-1/0/1)

子树高度：即 从根节点开始算，一直到最后一层叶子节点 中，一共多少树层

我们本文默认 左右子树高度之差 = 右子树高度 - 左子树高度

（右减左 和 左减右 都一样的，意义一样）

如果一棵二叉搜索树是高度平衡的，它就是AVL树。

如果它有 N 个结点，其高度可保持在 logN 层 ，搜索时间复杂度O(logN)。

下图中数字为  左右子树高度之差

2. AVL树节点 类

节点默认  key/value 键值对模型

template<class K, class V>
struct AVLTreeNode 
{typedef AVLTreeNode<K, V> Node;pair<K, V> _kv;Node* _left;Node* _right;Node* _parent;int _bf; // 存平衡因子：balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};

3. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

3.1 按照二叉搜索树的方式插入新节点

// 插入
Node* insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node(kv);return _root;}Node* cur = _root;Node* parent = cur;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;}}// 在 cur 的位置插入该节点cur = new Node(kv);if ((parent->_kv).first > kv.first) parent->_left = cur;else  parent->_right = cur;cur->_parent = parent; // 每个节点连接父节点// 更新平衡因子// .....return _root;
}

3.2 调整节点的平衡因子

前面提过 左右子树高度之差 即为 平衡因子

插入一个节点，会影响子树的高度，因此影响一系列 平衡因子

当前插入一个节点 cur ，其 父节点 parent 和 祖先节点 的 平衡因子 都可能被影响

⭐例如：

1、当在 节点 8 的左边插入一个 节点，节点 8 的 平衡因子变成 0，其他的节点不变

2、当在 节点 4 的右边插入一个 节点，节点 4 的 平衡因子变成 1，节点 3 的 平衡因子变成 0，其他的节点不变

插入节点，会影响部分祖先节点的平衡因子

⭐（1）更新平衡因子

插入在左子树，平衡因子--

插入在右子树，平衡因子++

⭐（2）处理 平衡因子 的 几种情况：

是否继续往上更新祖先，要看 parent 所在子树的高度是否变化

🐵1、 parent 的平衡因子  bf == 0

说明 parent 的平衡因子更新前是 1 or -1，

插入节点插入矮的那边 parent 所在子树的高度不变，

说明刚好平衡，不需要继续往上更新

🐵2. parent 的平衡因子 bf == 1 or -1

说明 parent 的平衡因子更新前是 0：即两边高度一样，子树平衡

插入节点插入在任意一边 parent 所在的子树高度都会变化了

说明刚好打破平衡，继续向上更新

🐵3. parent 的平衡因子== 2 or -2

说明parent的平衡因子更新前是 1 or -1，插入节点插入在高的那边

进一步加剧了parent所在的子树的不平衡，已经违反违规了，

子树失衡，需要旋转处理


🐵4. 其他情况：都是不合理的，直接报错


 

注意看注释理解

// 更新平衡因子
while (parent) {// 插入在左边，父亲平衡因子 减减// 插入在右边，父亲平衡因子 加加if (cur == parent->_left) parent->_bf--;else if (cur == parent->_right) parent->_bf++;// 若 bf == 0：说明刚好平衡// 若 bf == 1 or -1：说明刚好打破平衡，但还算做平衡，继续向上更新// 若 bf == 2 or -2：说明失衡，旋转// 其他：其他情况都是不合理的，直接报错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) {// 旋转逻辑：// ...}else assert(false);
}

3.3 旋转逻辑

前面 3.2 节中提到，当 插入一个节点 parent 的平衡因子== 2 or -2 时，应该执行旋转

旋转有 四种类型：

RR 型、LL 型 、LR型、RL型

⭐RR 型旋转：左单旋

添加 节点 7 后：节点 3 的平衡因子变成 2

则要对 节点 3 执行旋转操作：因为 节点 5 是 右孩子，节点 6 也是 右孩子 

双 R，即 RR型，向左旋转一次

旋转逻辑 如图示：

动图演示 旋转：

（注：动图取材取自 B站up主：蓝不过海呀 （若侵权即删））

代码示例
// RR型：左单旋
void rotateRR(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;// 1、subRL 变成 parent 的右孩子parent->_right = subRL;if (subRL) subRL->_parent = parent;  // subRL 是有可能为 空的// 2、parent变成subR的左孩子subR->_left = parent;parent->_parent = subR;// 3、subR变成当前子树的根if (parentParent) {if (parent == parentParent->_right)parentParent->_right = subR;else parentParent->_left = subR;subR->_parent = parentParent;}// 如果 parentParent == nullptr：说明 parent 是该树的 _root，_root 的 parent 是空else {_root = subR;subR->_parent = nullptr;}// 单独处理 平衡因子subR->_bf = 0;parent->_bf = 0;
}

⭐LL 型旋转：右单旋

添加 节点 2 后：节点 5 的平衡因子变成 -2

节点 5 ：左子树高度 = 3 ，右子树高度 = 1 ，则节点 5 的平衡因子 = -2，需要旋转

旋转逻辑 如图示：

动图演示 旋转：

（注：动图取材取自 B站up主：蓝不过海呀 （若侵权即删））

代码示例

其实代码逻辑 和 上面的 RR型就是刚好 镜像相反

// LL型：右单旋
void rotateLL(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;// 1、subLR变成parent的左孩子parent->_left = subLR;if (subLR) subLR->_parent = parent;  // subRL 是有可能为 空的 // 2、parent变成subL的右孩子subL->_right = parent;parent->_parent = subL;// 3、subL变成当前子树的根if (parentParent) {if (parent == parentParent->_right)parentParent->_right = subL;else parentParent->_left = subL;subL->_parent = parentParent;}// 如果 parentParent == nullptr：说明 parent 是该树的 _root，_root 的 parent 是空else {_root = subL;subL->_parent = nullptr;}subL->_bf = 0;parent->_bf = 0;
}

⭐LR 型旋转：subL 先 左旋，parent 再 右旋（先 L 后 R）

旋转逻辑 如图示：

动图演示 旋转：

（注：动图取材取自 B站up主：蓝不过海呀 （若侵权即删））

代码示例

双旋，其实直接复用 前面两个单旋的函数即可，无需自己再实现

关于平衡因子的更新：因为单旋函数中，都是直接将 平衡因子置为 0

       而双旋的平衡因子会改变，因此需要 先旋转后，再添加处理平衡因子的逻辑

各个节点平衡因子的更新数值如何确定：这个直接看双旋后各个节点的平衡因子为多少即可，是固定值

// LR 型：subL 先 左旋， parent 右旋
void rotateLR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;rotateRR(parent->_left);rotateLL(parent);// 双旋后，各个节点平衡因子的更新if (bf == -1) {parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1) {parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0) {parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else assert(false);
}

⭐RL 型旋转：subR 先 右旋，parent 再 左旋（先 R 后 L）

这个原理也就是上面的 LR 型旋转 刚好镜像相反

动图演示 旋转：

（注：动图取材取自 B站up主：蓝不过海呀 （若侵权即删））

代码示例
// RL 型：subR 先 右旋， parent 左旋
void rotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;rotateLL(parent->_right);rotateRR(parent);// 双旋后，各个节点平衡因子的更新if (bf == -1) {parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1) {parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 0) {parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else assert(false);
}

⭐关于 双旋 中 平衡因子的更新逻辑

上面 LR 型旋转 和  RL 型旋转 在 复用单旋的函数后，还需要对 平衡因子进行处理更新

我们以 LR 型旋转为例，解释为什么 可以根据 subRL 的 平衡因子的数值 来区分几种情况

int bf = subLR->_bf;// 双旋后，各个节点平衡因子的更新
if (bf == -1) {parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;
}
else if (bf == 1) {parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;
}
else if (bf == 0) {parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;
}
else assert(false);

下面三种情况：

初始状态下，parent 和 subL 都是固定相同的，唯一不同的是 subLR 的，因此可以以 subLR 作为区分指标

情况一：bf == -1

情况二：bf == 1

情况三：bf == 0

3.4 AVL 树总代码：额外添加其他各种功能函数

额外添加：

Size ：求二叉树的节点个数

Height：获取该树的高度

IsBalanceTree：判断本树是否平衡

以及 基础函数：拷贝构造、赋值重载、析构函数

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;/*
1、先手搓一棵二叉搜索树
*/template<class K, class V>
struct AVLTreeNode 
{typedef AVLTreeNode<K, V> Node;pair<K, V> _kv;Node* _left;Node* _right;Node* _parent;int _bf; // 存平衡因子：balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};template<class K, class V>
class AVLTree
{
public:typedef AVLTreeNode<K, V> Node;AVLTree() = default;~AVLTree() {destory(_root);_root = nullptr;}// 拷贝构造AVLTree(const AVLTree<K, V>& t) {_root = CopyTree(t._root);}// 赋值重载AVLTree<K, V>& operator=(const AVLTree<K, V>& t) {AVLTree tmp(t);std::swap(_root, tmp._root);return *this;}// 查找bool find(const K& key) const {Node* cur = _root;while (cur) {if ((cur->_kv).first < key) {cur = cur->_right;}else if ((cur->_kv).first > key) {cur = cur->_left;}else return true;}return false;}// 插入Node* insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node(kv);return _root;}Node* cur = _root;Node* parent = cur;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;}}// 在 cur 的位置插入该节点cur = new Node(kv);if ((parent->_kv).first > kv.first) parent->_left = cur;else  parent->_right = cur;cur->_parent = parent; // 每个节点连接父节点// 更新平衡因子while (parent) {if (cur == parent->_left) parent->_bf--;else if (cur == parent->_right) parent->_bf++;// 若 bf == 0：说明刚好平衡// 若 bf == 1 or -1：说明刚好打破平衡，但还算做平衡，继续向上更新// 若 bf == 2 or -2：说明失衡，旋转// 其他：其他情况都是不合理的，直接报错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) {// 旋转：同号单旋，异号双旋// RR 型：左旋if (parent->_bf == 2 && cur->_bf == 1) rotateRR(parent);// LL 型：右旋if (parent->_bf == -2 && cur->_bf == -1) rotateLL(parent);// LR 型：subL 先 左旋， parent 右旋if (parent->_bf == -2 && cur->_bf == 1) {rotateLR(parent);}// RL 型：subR 先 右旋， parent 左旋if (parent->_bf == 2 && cur->_bf == -1) {rotateRL(parent);}break;  // 旋转完了就要 break 出去，否则会继续向上更新，导致 平衡因子出错}else assert(false);}return _root;}// RR型：左单旋void rotateRR(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;// 1、subRL 变成 parent 的右孩子parent->_right = subRL;if (subRL) subRL->_parent = parent;  // subRL 是有可能为 空的// 2、parent变成subR的左孩子subR->_left = parent;parent->_parent = subR;// 3、subR变成当前子树的根if (parentParent) {if (parent == parentParent->_right)parentParent->_right = subR;else parentParent->_left = subR;subR->_parent = parentParent;}// 如果 parentParent == nullptr：说明 parent 是该树的 _root，_root 的 parent 是空else {_root = subR;subR->_parent = nullptr;}// 单独处理 平衡因子subR->_bf = 0;parent->_bf = 0;}// LL型：右单旋void rotateLL(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;// 1、subLR变成parent的左孩子parent->_left = subLR;if (subLR) subLR->_parent = parent;  // subRL 是有可能为 空的 // 2、parent变成subL的右孩子subL->_right = parent;parent->_parent = subL;// 3、subL变成当前子树的根if (parentParent) {if (parent == parentParent->_right)parentParent->_right = subL;else parentParent->_left = subL;subL->_parent = parentParent;}// 如果 parentParent == nullptr：说明 parent 是该树的 _root，_root 的 parent 是空else {_root = subL;subL->_parent = nullptr;}subL->_bf = 0;parent->_bf = 0;}// LR 型：subL 先 左旋， parent 右旋void rotateLR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;rotateRR(parent->_left);rotateLL(parent);// 双旋后，各个节点平衡因子的更新if (bf == -1) {parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1) {parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0) {parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else assert(false);}// RL 型：subR 先 右旋， parent 左旋void rotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;rotateLL(parent->_right);rotateRR(parent);// 双旋后，各个节点平衡因子的更新if (bf == -1) {parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1) {parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 0) {parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else assert(false);}// 删除分三种情况// 1、节点没有孩子// 2、节点只有一个孩子：分是左孩子，还是右孩子// 3、节点有两个孩子// 删除默认删除中序遍历第一个和数值相等的节点Node* erase(const K& key) {if (_root == nullptr) {cout << "整棵树已被删除" << '\n';return _root;}// 看这个元素是否存在if (!find(key)) {cout << "节点不存在" << '\n';return _root;  // 我们这里删除操作失败，也返回 原树}// 查找操作Node* cur = _root;Node* parent = nullptr;while (cur) {if ((cur->_kv).first < key) {parent = cur;cur = cur->_right;}else if ((cur->_kv).first > key) {parent = cur;cur = cur->_left;}else break;}// 删除操作if (cur->_left == nullptr) {if (parent == nullptr) {_root = cur->_right;}else {if ((parent->_kv).first < key) {parent->_right = cur->_right;}else parent->_left = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr) {if (parent == nullptr) {_root = cur->_left;}else {if ((parent->_kv).first < key) {parent->_right = cur->_left;}else parent->_left = cur->_left;}delete cur;cur = nullptr;}else {// 取左子树最大值：即左子树的最右边的节点// 取右子树最小值：即右子树的最左边的节点// 我们这里采取第二种方法// 不断向左遍历Node* MinRight = cur->_right;Node* MinRight_parent = cur;while (MinRight->_left) {  // 这里很奇怪MinRight_parent = MinRight;MinRight = MinRight->_left;}if ((MinRight_parent->_kv).first < (MinRight->_kv).first) {MinRight_parent->_right = MinRight->_right;}else MinRight_parent->_left = MinRight->_right;(cur->_kv).first = (MinRight->_kv).first;delete MinRight;}return _root;}// 中序遍历void InOrder() {_InOrder(_root);cout << '\n';}// 获取根节点Node* GetRoot() {return _root;}// 获取该树的高度void Height() {return _Height(_root);}// 本树是否平衡bool IsBalanceTree() {return _IsBalanceTree(_root);}// 获取节点个数int Size() {return _Size(_root);}private:int _Size(Node* pRoot) {if (pRoot == nullptr) return 0;//if (pRoot->_left == nullptr && pRoot->_right == nullptr) return 1;return 1 + _Size(pRoot->_left) + _Size(pRoot->_right);}int _Height(Node* pRoot) {if (pRoot == nullptr)return 0;return 1 + max(_Height(pRoot->_left), _Height(pRoot->_right));}bool _IsBalanceTree(Node* pRoot){// 空树也是AVL树if (nullptr == pRoot) return true;// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(pRoot->_left);int rightHeight = _Height(pRoot->_right);int diff = rightHeight - leftHeight;// 这个判断平衡因子的方法 直接 帮我检查出 之前没写 break 导致平衡因子自己更新// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (diff != pRoot->_bf || (diff > 1 || diff < -1))return false;// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(pRoot->_left) && _IsBalanceTree(pRoot->_right);}// 销毁一棵树：后序遍历void destory(Node* root) {if (root == nullptr) {return;}destory(root->_left);destory(root->_right);delete root;}// 拷贝一棵树Node* CopyTree(const Node* root) {if (root == nullptr) {return nullptr;}Node* newRoot = new Node(root->_kv);newRoot->_left = CopyTree(root->_left);newRoot->_right = CopyTree(root->_right);return newRoot;}void _InOrder(const Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << (root->_kv).first  << " : " << (root->_kv).second << '\n';_InOrder(root->_right);}Node* _root = nullptr;
};

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

如何在算家云搭建ControlNext-SVD（视频生成） C++与现代开发实践第三课：多线程与并发编程 segformer的mmcv-full==1.2.7怎么装 带外管理交换机的小科普 Vue01 【C++算法】11.滑动窗口_最大连续1的个数lll