【C++实现AVL树】

news/2025/1/11 3:48:33/

文章目录

  • 一、AVL树概念
  • 二、AVL树节点的定义
  • 三、AVL树的插入
  • 四、AVL树的旋转
  • 五、AVL树的验证
  • 六、AVL树的性能
  • 七、总结

一、AVL树概念

AVL树出现在二叉搜索树之后，弥补了二叉搜索树的一些缺点。

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

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

但是，AVL树不一定都有平衡因子，因为平衡因子只是用来检测平衡的方式，如果有其他检测的方法，也可以将平衡因子弃之不用。

例：
在这里插入图片描述

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 log2n，搜索时间复杂度O(log2n)。

二、AVL树节点的定义

一个AVL树的节点和二叉搜索树类似，不同的是AVL树采用三叉链的结构更方便控制(即子节点也有一个指向父节点的指针)。但这个和平衡因子一样，不是必须要求的，也可采用其他方法，只要能完成相同的操作即可(本篇文章采用三叉链进行讲解)。
另外，对AVL树中存储的数据，这里采用pair<K,V>的方式，可以适用于更多的场景。

代码如下：

template <class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//左孩子AVLTreeNode<K, V>* _right;//右孩子AVLTreeNode<K, V>* _parent;//双亲pair<K, V> _kv;//存储的数据int _bf;//平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)//初始时，该节点没有左右孩子，平衡因子为0, _kv(kv){}
};

AVL树类模板初始如下：

template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree():_root(nullptr){}
private:Node* _root;
};

三、AVL树的插入

AVL树的插入分为三步：

  1. 像二叉搜索树一样按照左孩子小于父节点，右孩子大于父节点的规则插入节点
  2. 检查每一个节点的平衡因子绝对值是否小于2
  3. 若平衡因子绝对值大于1，则进行旋转

插入节点：

若树为空树，直接将新增节点作为根节点。否则再依次向下比较节点key值的大小，以确定正确的插入位置。若已有相同key值的节点存在，则插入失败。不要忘记维护好三个节点指针的指向。

如下：
在这里插入图片描述
代码实现如下：

bool Insert(const pair<K, V>& kv){if (_root == nullptr){//根节点为空，直接将新增节点作为根节点_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){//比较新增节点和当前节点的key值，确定将其放在左/右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;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}
}

但是，就上图而言，很明显已经不是一棵AVL树了，因为它的节点中出现了平衡因子不小于2的情况。所以为了保证每插入一个节点之后，AVL树结构不被破坏，就需要检查节点的平衡因子。
本篇文章中的平衡因子为右子树高度-左子树高度

又因为一个节点的平衡因子与左右子树有关，所以新增一个节点之后，只会影响新增节点的祖先节点的平衡因子,也就是说，只需要检测新增节点到根节点所在路径中的节点平衡因子。

更新平衡因子的详细步骤：

  • 首先更新新增节点的父节点平衡因子

如果新增节点为父节点的左孩子，则父节点平衡因子-1；若为右孩子，则父节点的平衡因子+1。

  • 然后向上更新父节点的祖先节点的平衡因子

这里有三种情况：
①插入新增节点后，父节点平衡因子为0。则说明插入之前父节点已经有一个孩子，插入后只是新增一个孩子，以父节点为根的子树高度不变，也就不会影响祖先的平衡因子，则更新结束。

②插入新增节点后，父节点平衡因子为1或-1。则说明更新前父节点平衡因子为0，更新后，父节点的左右子树其中之一的高度+1。这时必定会影响到父节点的祖先节点的平衡因子，所以需要继续向上更新。

③插入新增节点后，父节点平衡因子为2或-2，这时父节点为根的子树已经不平衡了，需要进行旋转(下文讲解)。

上面三种情况如图：
在这里插入图片描述
注意，这里最坏情况下，会一直更新到根节点。

代码实现如下：

while (parent)
{if (cur == parent->_left)parent->_bf--;elseparent->_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){// 旋转处理}else{// 说明插入更新平衡因子之前，树中平衡因子就有问题了assert(false);}
}

四、AVL树的旋转

当一棵树中某一棵子树的根节点的平衡因子绝对值大于1时，为了保证AVL树结构，就必须进行旋转操作。而旋转又分为四种----左单旋、右单旋、左右双旋和右左双旋。下面一 一介绍：
右单旋：

当某一个节点的平衡因子为-2且子节点平衡因子为-1时，表示左子树的高度比右子树大2，为了平衡，就必须进行右单旋，如下：
在这里插入图片描述
这样既保证了平衡因子满足要求，又保证了搜索树的特性，而且这棵树的高度完成了-1。
注意，需要调整的不一定是整棵树，也可能是某一棵子树，这种情况下，调整子树不会破坏整棵树的平衡。

代码如下：

if (parent->_bf == -2 && cur->_bf == -1)
{RotateR(parent);
}
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)//不能将空节点的父节点赋值subLR->_parent = parent;//记录父节点的父节点，方便为后续subL的父节点赋值Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){//父节点为根，则subL变为新的根_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}//别忘了调整subL和parent的平衡因子subL->_bf = parent->_bf = 0;
}

左单旋：

类比右单旋，左单旋就是一个节点的平衡因子为2且子节点平衡因子为1的情况，如图：
在这里插入图片描述

这里就不粘贴代码了，在文章最后会给出完整代码。

双旋(左右/右左)：

当一棵树的子树的左子树的高度大于右子树，且这棵子树的子树的右子树高度大于左子树时(相反情况也适用)，就需要用到双旋，如图：
在这里插入图片描述
这种情况就需要用到左右双旋，直接复用左单旋和右单旋即可。

void RotateLR(Node* parent)
{RotateL(parent->_left);RotateR(parent);
}

至于右左双旋类比即可。
但这样还不够，因为在某些场景下，有些节点的平衡因子会出错，这种情况下文再详谈。

五、AVL树的验证

上文中，我们已经实现了AVL树的插入，那么该怎么验证这个插入的过程没有错误呢？

答：需要对整棵树计算出左子树和右子树的高度，判断它们的差的绝对值是否小于2。
注意，这里计算的过程应该包含每一棵子树。不用平衡因子检测是因为平衡因子本身可能出错。

代码如下：

bool IsBalance()
{return _IsBalance(_root);
}int Height(Node* root)
{if (root == NULL)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}bool _IsBalance(Node* root)
{if (root == NULL)return true;// 对当前树进行检查int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){//检查平衡因子是否有误cout << root->_kv.first << "现在是:" << root->_bf << endl;cout << root->_kv.first << "应该是:" << rightHeight - leftHeight << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}

事实是上面的实现AVL树的代码确实会导致一些情况下，某些平衡因子出错的情况。
而且错误是出现在双旋的过程中的，该过程中需要控制平衡因子。在双旋中，把一些节点的平衡因子置0，但经过两次旋转后，它们的平衡因子可能并不为0。
例：
在这里插入图片描述
可以看到，这里双旋之后，3的平衡因子为-1，但原代码处理后，3的平衡因子为0，因为3在第一次左旋的时候，已经将其平衡因子置零了。

上面这种情况是左右双旋，而当右左双旋时，结果就会是右边的节点的平衡因子变为1。
当h=0，6为新增节点时，双旋后平衡因子都为0(具体过程可以通过画图观察一下)。

那么怎么区分这三种情况，并做出改正呢？

可以看到，这三种情况跟旋转前的6的平衡因子有关(6的平衡因子为1、-1和0的情况)。所以，在旋转之前记录6的平衡因子，再对旋转后的6的左/右节点的平衡因子进行改正即可。

这里只给出左右双旋的图示，右左双旋可以类比，总结如下：

  • 旋转前 sunLR：-1；旋转后 parent：1，subL：0，subLR：0

在这里插入图片描述

  • 旋转前 subLR：1；旋转后 parent：0，subL：-1，subLR：0

在这里插入图片描述

  • 旋转前 subLR：0；旋转后 parent：0，subL：0，subLR：0

在这里插入图片描述

下面给出完整的代码：

template <class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//左孩子AVLTreeNode<K, V>* _right;//右孩子AVLTreeNode<K, V>* _parent;//双亲pair<K, V> _kv;//存储的数据int _bf;//平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)//初始时，该节点没有左右孩子，平衡因子为0, _kv(kv){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree():_root(nullptr){}bool Insert(const pair<K, V>& kv){if (_root == nullptr){//根节点为空，直接将新增节点作为根节点_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){//比较新增节点和当前节点的key值，确定将其放在左/右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;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 控制平衡// 1、更新平衡因子 -- 新增节点到根节点的祖先路径// 2、出现异常平衡因子，那么需要旋转平衡处理while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_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 RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}subR->_bf = parent->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)//不能将空节点的父节点赋值subLR->_parent = parent;//记录父节点的父节点，方便为后续subL的父节点赋值Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){//父节点为根，则subL变为新的根_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}//别忘了调整subL和parent的平衡因子subL->_bf = 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){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_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){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);}}bool IsBalance(){return _IsBalance(_root);}int Height(Node* root){if (root == NULL)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBalance(Node* root){if (root == NULL)return true;// 对当前树进行检查int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "现在是:" << root->_bf << endl;cout << root->_kv.first << "应该是:" << rightHeight - leftHeight << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}
private:Node* _root;
};

六、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log2N 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：
插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

七、总结

本篇文章主要是介绍了AVL树的插入，对其中的四种旋转方法做了详解。
重中之重要注意区分什么时候该用哪一种合适的旋转方法(根据节点的平衡因子判断)，以及双旋之后该对哪些节点的平衡因子做出调整(不需要死记硬背，记住其中一种双旋结果，另外的就可以类比了)。

此外，本篇文章中并没有少搜索、修改以及删除的方法。因为搜索和修改比较简单，类比搜索树即可。而删除操作还是需要进行平衡因子的检查以及相应的旋转操作，可以类比插入。

另外，本篇文章中AVL树中的数据是pair<int,int>型的，可以适用于更多场景。读者可以根据自身需要，将数据类型改为int等。

本篇完，青山不改，绿水长流！


http://www.ppmy.cn/news/22735.html

相关文章

Vue基础11之TodoList案例第一篇

Vue基础11之TodoList案例第一篇

Vue基础11TodoList案例组件拆分静态组件代码目录结构App.vueHeader.vueList.vueItem.vueFooter.vue初始化列表List.vueItem.vue添加功能使用nanoid作为每项的id值安装nanoid使用nanoid兄弟组件之间的传值App.vueHeader.vueList.vue勾选App.vueList.vueItem.vue使用v-model也能实…
阅读更多...
Java特性之设计模式【观察者模式】

Java特性之设计模式【观察者模式】

一、观察者模式 概述 当对象间存在一对多关系时&#xff0c;则使用观察者模式&#xff08;Observer Pattern&#xff09; 观察者模式是一种对象行为模式。它定义对象间的一种一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知…
阅读更多...
路由器连接WIFI组网

路由器连接WIFI组网

白驹过隙&#xff0c;逝者如斯。经过断断续续几个月的更新&#xff0c;关于无线路由器和Wi-Fi的介绍终于告一段落。 其实&#xff0c;这个话题下还有很多很多的内容没有涉及到&#xff0c;然生有涯而知无涯&#xff0c;只能在此暂且搁笔&#xff0c;后续缘起再续。 下面&…
阅读更多...
第九章（14）：STL之常用拷贝和替换算法

第九章（14）：STL之常用拷贝和替换算法

文章目录前情回顾常用拷贝算法copy常用替换算法replacereplac_ifswap下一座石碑&#x1f389;welcome&#x1f389; ✒️博主介绍&#xff1a;一名大一的智能制造专业学生&#xff0c;在学习C/C的路上会越走越远&#xff0c;后面不定期更新有关C/C语法&#xff0c;数据结构&…
阅读更多...
JVM入门知识总结

JVM入门知识总结

在学习虚拟机之前我们要知道为什么要学习虚拟机呢?首先就是增加自己的知识,其次就是面试的需要,其实不懂 JVM 也可以照样写出优质的代码&#xff0c;但是不懂 JVM 有可能别被面试官虐得体无完肤.一.虚拟机的概述虚拟机&#xff08;Virtual Machine&#xff09;&#xff0c;就是…
阅读更多...
8 个很棒的 Vue 开发技巧

8 个很棒的 Vue 开发技巧

1.路由参数解耦通常在组件中使用路由参数&#xff0c;大多数人会做以下事情。export default {methods: {getParamsId() {return this.$route.params.id}} }在组件中使用 $route 会导致与其相应路由的高度耦合&#xff0c;通过将其限制为某些 URL 来限制组件的灵活性。正确的做…
阅读更多...
MySQl学习（从入门到精通 1.5）

MySQl学习（从入门到精通 1.5）

MySQl学习&#xff08;从入门到精通 1.5&#xff09;第 08 章_聚合函数1. 聚合函数介绍1. 1 AVG和SUM函数1. 2 MIN和MAX函数1. 3 COUNT函数2. 1 基本使用2. 2 使用多个列分组2. 3 GROUP BY中使用WITH ROLLUP3. HAVING3. 1 基本使用3. 2 WHERE和HAVING的对比4. SELECT的执行过程…
阅读更多...
我的网站上线了！

我的网站上线了！

最近有段时间没有写原创文章了&#xff0c;恰好这两天正在翻阅历史文章的时候&#xff0c;发现文章中的图片竟然裂了&#xff1f;顿时冒了一身冷汗&#xff0c;因为每逢遇到这种情况&#xff0c;动辄需要花费一周的时间迁移图片。。。。。。 当我直接访问图片 url 的时候&#…
阅读更多...
最新文章

Copyright @ 2022~2023