『 C++ 』AVL树详解 ( 万字 )

🦈STL容器类型

在STL的容器中,分为几种容器:

1. 序列式容器（Sequence Containers）:
   • 这些容器以线性顺序存储元素，保留了元素的插入顺序。
   • 支持随机访问，因此可以使用索引或迭代器快速访问任何位置的元素。
   • 主要的序列式容器包括vector、list、deque、array和forward_list。
2. 关联式容器（Associative Containers）:
   • 这些容器不保留元素的插入顺序，而是根据元素的键进行排序和组织。
   • 元素以键值对的形式存储，键通常用于快速查找元素。
   • 主要的关联式容器包括set、multiset、map和multimap。
3. 无序关联容器（Unordered Associative Containers）:
   • 这些容器也是键值对容器，但与关联式容器不同，它们不维护元素的排序顺序。
   • 使用哈希表（hash table）来组织元素，以便快速查找。
   • 主要的无序关联容器包括unordered_set、unordered_multiset、unordered_map和unordered_multimap。
4. 容器适配器（Container Adapters）:
   • 容器适配器是一种特殊类型的容器，它们提供了一种不同于传统容器的接口，通常用于特定的数据结构需求。
   • stack是一个适配器，提供了栈（后进先出）的操作。
   • queue是一个适配器，提供了队列（先进先出）的操作。
   • priority_queue是一个适配器，提供了优先队列的操作，通常用于实现优先级队列。

---

🦈键值对

键值对,顾名思义其用来表示具有一一对应的关系的一种结构,该结构中一般只包含两个成员变量,即Key与Value;

在STL中存在一种这样的容器template <class T1, class T2> struct pair;;

这个容器是一个类模板,其源码中的底层构造大致为:

template <class T1, class T2>
struct pair {typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()) {}pair(const T1& a, const T2& b) : first(a), second(b) {}
};

可以看到模板参数共有两个分别为T1与T2;

其成员变量只有两个分别为first与second从而能够使该容器具有key与value一对一的关系;

---

🦈AVL树概念

AVL树(Adelson-Velsky and Landis Tree)它是一种自平衡的二叉搜索树,由苏联的数学家Georgy Adelson-Velsky和Evgenii Landis于1962年首次提出;

AVL树又被称为高度平衡搜索二叉树,它是基于搜索二叉树的基础上的高度平衡搜索二叉树,其性质主要为:

• 它可能是一棵空树(空树可以被看作是一棵AVL树)
• 若该树的左子树不为空,则左子树的所有节点的值都小于根节点的值;若该树的右子树不为空时,该右子树的所有节点都大于根节点的值(搜索二叉树的条件);
• 其左子树与右子树的高度差不超过1;
• AVL树的左右子树也一样为AVL树,意思是每棵’AVL树中的所有子树都应该符合该条件;

以该图为例,该图即为一棵AVL树,其每个节点的左右子树高度差都不超过1;

那么在AVL树的结构中就有几个需要注意的点:

• 如何判断左右子树高度差?
• 如何在插入过程中判断AVL树在插入之后其树的结构是否符合AVL树的规则?
• 当AVL树出现不平衡的状态应该如何调整致使树从不平衡变回AVL树?

---

🦈AVL树的节点结构

在实现容器或数据结构的过程中可以尽量的使用模板来保证其泛型;对于一棵简单的AVL实现可以根据需要(key模型 或 是key,value模型)来确定实现该数据结构的模板参数个数;

而该篇文章的AVL树实现将针对后者,即key,value模型来进行实现;

AVL树中的节点一般为三叉链结构,即节点内存在三个指针来控制指向,分别为:

• _left节点,指向节点的左子树;
• _right节点,指向节点的右子树;
• _parent节点,指向节点的父亲节点;

设定义一个变量使用pair<T1,T2>容器来存放插入的数据,其中pair<T1,T2>中的T1对应着key,value模型中的key,T2对应着模型中的value数据;

同时可以设置一个平衡因子变量,以平衡因子的变化来判断该树是否要进行调整,当该树不平衡时则使用某种方式将该树调整回平衡状态,使其结构恢复为AVL树;

template<class K,class V>
struct AVLTreeNode{pair<K, V> _kv;//AVLTreeNode<K, V> *_left;//指向左子树AVLTreeNode<K, V> *_right;//指向右子树AVLTreeNode<K, V> *_parent;//指向其父亲节点int _bf ;//平衡因子AVLTreeNode(const pair<K,V> &kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

---

🦈AVL树的结构定义

从上文可知,AVL树可以看作是一棵搜索二叉树,其为基于搜索二叉树在此基础上对树做了平衡的操作使其在结构上变得平衡不至于在极端情况下出现"歪脖子树"的情况;

AVL树的定义与平衡搜索二叉树的结构上呈现类似;

template<class K,class V>
class AVLTree{typedef AVLTreeNode<K,V> Node;//将节点进行typedef
public:bool Insert(const K& key);
protected:
private:Node *_root = nullptr;//节点指针
};

该篇文章中重点实现AVL树中的插入操作;

---

🦈AVL树的插入操作

AVL树的插入操作与搜索二叉树的插入操作类似,唯独不同的是AVL树在进行插入操作时需要对树的结构进行判断,即判断插入过后该树是否还符合AVL树的规则(节点的左右子树高度差不超过1);

当树的结构规则被破坏时则需要采用一些特定的方式对树的结构进行调整;

---

🐡节点插入逻辑

新节点所插入的位置必是为空节点nullprtr,判断所插入数据pair<K,V>中的key值是否大于当前节点;

• 大于当前节点

  当所插入数据的key值大于当前节点数据说明需要插入在该节点的右子树区域;

• 小于当前节点

  当所插入数据的key值小于当前节点数据说明需要插入在该节点的左子树区域;

• 等于当前节点

  当所插入数据的key值等于当前节点中的数据时,根据搜索二叉树的定义即数据的唯一性,该数据的值已经存在于该树中,该新节点不予插入,返回false;

bool Insert(const std::pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node *parent = nullptr;Node *cur = _root;//while (cur){/*当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{//cur->_kv.first == kv.firstreturn false;}}/*与所插入的叶子节点进行链接*/cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;/*更新平衡因子...判断树的结构规则是否符合AVL树的规则1.符合 不影响下一个节点的插入2.不符合 使用旋转的方式对树进行调整*/return true;}//Insert函数反括号

---

🐡判断树是否符合AVL树的规则

判断树是否符合AVL树的规则有两种:

• 创建子函数

  每当插入一个数据时调用子函数来判断树的整体结构是否符合节点的左右子树高度差不超过1;

• 使用平衡因子

  使用平衡因子的方式即将AVL树节点的结构中加入一个变量来判断节点的平衡因子;

  当平衡因子为0时表示该节点左右子树高度差为0;

  当平衡因子为1或-1时表示该节点的左右子树高度差为1;

  当平衡因子为2或-2时表示该节点的左右子树高度差为2,已经不平衡,需要进行特定操作使其恢复AVL树的平衡状态;

在本文中所使用的方式为方式二,即采用平衡因子的方式来对树的节点进行判断;

在上文中提到了对与新节点的插入;

若是搜索二叉树对新节点进行插入时则不需要再对树的结构进行判断,但是在AVL树中则要对AVL树的结构进行判断;

当然再判断树的平衡因子前首先应该在插入节点之后对各个节点的平衡因子进行更新;

对于平衡因子的更新有三种情况:

• 新插入节点的平衡因子

  新插入节点的平衡因子必定为0,因为其左右子树都为空节点nullptr;

• 新节点在节点的左子树中

  当新节点在节点(新节点的祖先节点)的左子树中时,节点(新节点的祖先节点)的平衡因子需要进行--;

• 新节点在节点的右子树中

  当新节点在节点(新节点的祖先节点)的右子树中时,节点(新节点的祖先节点)的平衡因子需要进行++;

一般平衡因子的更新与平衡因子的检查(树结构的检查)是同一时间的,检查的情况也会出现四种情况:

• 平衡因子更新后为0

  当平衡因子在更新过后为0时则表示这次的插入对树(子树)的平衡状态反而起到了使其平衡的作用;

  在该次判断后可以直接跳出循环结束插入;

• 平衡因子更新后为1

  当平衡因子更新过后为1时表示这次的插入对树(子树)的平衡状态从完全平衡(左右高度差为0)变成了高度平衡(左右高度差为1),这个变化可能影响到了这个节点的其他的祖先节点,所以应该继续往上进行更新,判断其它的祖先节点是否被影响成非高度平衡状态(左右子树高度差为2);

• 平衡因子更新后为2

  当平衡因子更新过为2时表示可以不用再继续向上遍历判断,因为该树(子树)已经不平衡,需要对该树(子树)进行处理;

  当处理结束之后可直接跳出循环结束插入操作;

• 平衡因子完全错乱

  这种情况是避免平衡因子完全错乱;

  当上面的三个条件都不满足时则表示平衡因子很可能已经混乱,整棵树的结构获取都变得不平衡,需要直接退出程序并对程序进行检查;

 while (parent){if (cur == parent->_left){//新节点为其parent->_bf--;}else // if (cur == parent->_right){parent->_bf++;}/*判断树的结构是否符合AVL树的规则*/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){/*子树不平衡需要进行旋转操作对树进行调整*/break;}else{/*平衡因子出现问题,对程序断死防止错误插入导致的更大问题*/assert(false);}

---

🐡旋转操作

AVL树中当其平衡因子的绝对值等于2时表示该节点左右子树的高度差为2,这时候表示这棵AVL树已经不平衡,需要对其进行调整;

那么当AVL树不平衡时如何对树进行操作?

• 采用旋转操作将树的结构进行调整使其变回高度平衡搜索二叉树(AVL树);

对于旋转操作中分为四种操作:

• 左单旋操作

  以树(子树)中的某个指定节点作为轴点,对这棵树进行左单旋操作;

• 右单旋操作

  以树(子树)中的某个指定节点作为轴点,对这棵树进行右单旋操作;

• 左右双旋操作

  以树(子树)中的某个指定节点作为轴点,对这棵树进行左单旋操作;

  再以该树(子树)中的另一个指定节点作为轴点,对这棵树进右单旋操作;

• 右左双旋操作

  以树(子树)中的某个指定节点作为轴点,对这棵树进行左单旋操作;

  再以该树(子树)中的另一个指定节点作为轴点,对这棵树进右单旋操作;

当一棵树(子树)中节点的平衡因子的绝对值为2时将会出现几种情况:

该图分别对应着几种需要进行旋转操作的情况;

那么如何理解几种旋转操作?

• 将以抽象图与实际图结合解释;

---

🦭右单旋操作

从上文可知,右单旋操作即为以树(子树)中的某个指定节点作为轴点,对这棵树进行右单旋操作;

该图为需要进行右单旋操作树(子树)的抽象图;

当子树a的高度由h变为h+1时由于60节点的左子树高于右子树,其平衡因子由-1变为-2;

a子树的高度变化影响到了其祖先节点;

具象图及变化操作:

• h为0时

  

  当h高度为0时,其红色节点即为新增节点,在该处节点新增时将会触发右单旋操作的情况;

  只需将cur节点所指向的右子树节点变成parent节点的左子树;

  parent节点变为cur节点的右子树;

  在该操作之后在h高度为0的情况下三个节点的平衡因子都将转化为0,使树的结构恢复为AVL树的结构;

• h为1时

  

  当h高度为1时,两个红色节点的任意一个节点为新增节点时都将触发右单旋操作的情况;

  再该中情况中,只需要将cur节点的右子树curright节点变为parent节点的左子树,再将parent节点变为cur节点的右子树即可;

  再该操作之后在h高度为1的情况下parent节点与cur的平衡因子将变为0;

• h为2时

  相较上面两种场景当中,当h为2时其的情况将会变得更多;

  以最单纯的抽象图为例:

  

  当h为2时,a子树的情况必定为情况①(只有当a子树为情况①时对a处进行新增节点才会触发右单旋操作);

  b子树与c子树的情况为①②③情况的其中一种;

  

  以该图为例,其旋转操作不再进行赘述;

  ---

• 代码片段

  void RotateR(Node *parent){ //左高右旋Node *cur = parent->_left;Node *curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node *ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){/*该树若是不为子树其cur节点将更新为根节点*/_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}
  

---

🦭左单旋操作

左单旋与右单旋的操作相反,其几种情况与右单旋的几种情况相同,只不过节点(子树)位置不同;

此处只对左单旋情况中的抽象图进行解析;

该图为例,该图即为需要对左单旋进行操作的情况;

当右子树高度高于左子树且平衡因子等于2时则需要对子树进行旋转操作;

旋转结束之后其cur节点与parent节点的平衡因子将恢复为0;

其结构整体恢复为AVL树的结构状态;

• 代码片段

  void RotateL(Node* parent){//右高左旋Node *cur = parent->_right;Node *curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node *ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}

---

🦭左右双旋操作

左右双旋操作,顾名思义在这种情况种需要用到两种单旋的方式使树的结构恢复为以往的AVL树的状态;

• 抽象图

  

  该图即为左右双旋操作的抽象图;

  当这种情况时b子树或者c子树的高度由h转变为h+1时都将破坏该AVL树的结构;

  当出现这种情况时即需要使用双旋操作来完成对树结构的恢复;

• 为什么当这种情况不能使用单旋操作对树的结构进行恢复?

  

  以该抽象图为例,该抽象图中的c子树的高度由h-1变为了h;

  对应的左子树的高度高于右子树,若是用单旋的话需要进行一个右单旋操作;

  而再该种情况下若是使用右单旋操作,最终的结果还是一个不平衡的状态;

  故在这种情况中不能使用单旋操作来解决AVL树中的不平衡状态;

根据上文所提,在该种情况中只能使用两种单旋操作的方式组合成双旋操作使得最终使得树的结构恢复为平衡状态;

该图即为左右双旋操作的大致操作流程;

从上面的抽象图中也可以衍生几个例子以加深对双旋操作的理解;

• 当树的高度h为0

  

  当红色节点为新增节点时需要触发左右双旋操作;

  ---

• 当树的高度h为1

  

  当红色节点或绿色节点为新增节点时需要触发左右双旋操作;

  该处旋转演示为绿色节点;

  ---

• 当树的高度h为2

  当树的高度h为2时,将会有多种情况;

  

  其中a子树与d子树分别为①②③中的任意一种;

  下图为树的高度h为2时的其中一种情况以及旋转方式;

  

  当绿色节点与红色节点其中一个节点为新增节点时需要进行左右双旋操作;

  此处旋转操作演示以绿色节点为例;

  ---

• 代码段

  void RotateLR(Node *parent){Node *cur = parent->_left;Node *curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);/*对平衡因子重新进行调整*/if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}}
  

  对于双旋操作来说,该操作只需要去调用单旋操作的接口即可;

  但除此之外还需要对其中的平衡因子进行调整(在单旋中的平衡因子调整并不是双旋操作所期望的结果,故需要在最后对平衡因子进行调整);

---

🦭右左双旋操作

右左双旋操作与左右双旋操作相同,只不过调用左单旋接口与右单旋接口的顺序不同,其对应的平衡因子调整也与之不同;

该处直接对几种情况的具象图对右左双旋操作进行解析;

• 具象图情况

  1. 当树的高度h为0

     

     ---

  2. 当树的高度h为1

     

     此处演示了其中的两种情况;

     ---

  3. 当树的高度h为2

     该处可以类比于左右双旋操作,对此不再进行赘述;

• 代码段

  void RotateRL(Node *parent){Node *cur = parent->_right;Node *curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);/*对平衡因子重新进行调整*/if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}
  

至此插入函数的逻辑到此结束;

---

🦈检查AVL树是否符合AVL树的规则

• 当插入结束后如何判断所插入的数据以及树的结构是否符合AVL树的性质?

如上题,如何在插入过后对AVL树的结构进行检查,确保在数据插入后能检查此AVL树的实现是否存在问题;

从该问题中可以以上文了解到AVL树的性质规则:

1. 左右子树的高度差不超过1;

2. 符合搜索二叉树的规则;

左右子树的高度差的判断可以使用两种方法,即采用递归的方式判断该树是否符合AVL树的规则;

由于该树是基于搜索二叉树的规则进行设置,故对于树的存储规则可以不用过分追究;

同时由于树节点的结构中存储了平衡因子,为了防止特殊情况的平衡因子异常导致的树的结构紊乱,应该在检查过程中添加对于平衡因子检查的控制,即一个节点的左右子树的高度差是否符合该节点的平衡因子;

• 代码段

   bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node *root){if(root == nullptr){return true;}int leftH = getHeight(root->_left); // the leftH is subtree height for left;int rightH = getHeight(root->_right);if(rightH - leftH != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}//return abs(rightH - leftH) < 2 && IsBalance(root->_left) && IsBalance(root->_right);}

---

🦈最终代码

#pragma once#include<iostream>#include<assert.h>using namespace std;template<class K,class V>
struct AVLTreeNode{pair<K, V> _kv;AVLTreeNode<K, V> *_left;AVLTreeNode<K, V> *_right;AVLTreeNode<K, V> *_parent;int _bf ;AVLTreeNode(const pair<K,V> &kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<class K,class V>
class AVLTree{typedef AVLTreeNode<K,V> Node;public:bool Insert(const std::pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node *parent = nullptr;Node *cur = _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;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// ... 控制平衡// 更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else // if (cur == parent->_right){parent->_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){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}//Insert函数反括号bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node *root){if(root == nullptr){return true;}int leftH = getHeight(root->_left); // the leftH is subtree height for left;int rightH = getHeight(root->_right);if(rightH - leftH != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}//return abs(rightH - leftH) < 2 && IsBalance(root->_left) && IsBalance(root->_right);}void InOrder(){_InOrder(_root);}protected:int getHeight(){return getHeight(_root);}int getHeight(Node *root){if(root == nullptr){return 0;}int left = getHeight(root->_left);int right = getHeight(root->_right);return left>right?left+1:right+1;}void RotateL(Node* parent){//右高左旋Node *cur = parent->_right;Node *curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node *ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateR(Node *parent){ //左高右旋Node *cur = parent->_left;Node *curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node *ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateLR(Node *parent){Node *cur = parent->_left;Node *curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}}void RotateRL(Node *parent){Node *cur = parent->_right;Node *curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}void _InOrder(const Node *root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_kv.first << " : " << root->_kv.second << std::endl;_InOrder(root->_right);}private:Node *_root = nullptr;
};