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

这篇具有很好参考价值的文章主要介绍了『 C++ 』AVL树详解 ( 万字 )。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🦈STL容器类型

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

在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是一个适配器,提供了优先队列的操作,通常用于实现优先级队列。

🦈键值对

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

在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;

其成员变量只有两个分别为firstsecond从而能够使该容器具有keyvalue一对一的关系;


🦈AVL树概念

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

🦈AVL树的节点结构

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

在实现容器或数据结构的过程中可以尽量的使用模板来保证其泛型;对于一棵简单的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树的结构定义

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

从上文可知,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树的插入操作

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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


🐡节点插入逻辑

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

新节点所插入的位置必是为空节点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.first
                return 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树的规则

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

判断树是否符合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);
            }

🐡旋转操作

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

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

  • 左单旋操作

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

  • 右单旋操作

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

  • 左右双旋操作

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

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

  • 右左双旋操作

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

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

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

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

🦭右单旋操作

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

具象图及变化操作:

  • h0

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

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

  • h1

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

  • h2

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

    以最单纯的抽象图为例:

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,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;
        }
    

🦭左单旋操作

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

当右子树高度高于左子树且平衡因子等于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;
        }
    
    

🦭左右双旋操作

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

  • 抽象图

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

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

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

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

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

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

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

  • 当树的高度h0

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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


  • 当树的高度h1

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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


  • 当树的高度h2

    当树的高度h2时,将会有多种情况;

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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

    『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

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


  • 代码段

    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;
            }
        }
    

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

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


🦭右左双旋操作

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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

  • 具象图情况

    1. 当树的高度h0

      『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法


    2. 当树的高度h1

      『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

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


    3. 当树的高度h2

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

  • 代码段

    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树的规则

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法

  • 当插入结束后如何判断所插入的数据以及树的结构是否符合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);
        }
    
    

🦈最终代码

『 C++ 』AVL树详解 ( 万字 ),C++,二叉树,数据结构,c++,开发语言,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-792526.html

#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;
};

到了这里,关于『 C++ 』AVL树详解 ( 万字 )的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(52)
  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(47)
  • 数据结构07:查找[C++][平衡二叉排序树AVL]

    图源:文心一言 考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_2 平衡二叉树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月11日
    浏览(48)
  • 数据结构:二叉树详解

    目录 概念(在做习题中常用的概念) 两种特殊的二叉树 二叉树的性质 二叉树的遍历(重点) 如上图: 二叉树的构建(代码表示一颗二叉树和一些操作二叉树的方法) 二叉树的oj习题讲解(重点) 1. 检查两棵树是否相同 力扣 2. 另一颗树的子树   力扣 3. 反转二叉树    

    2024年02月10日
    浏览(31)
  • C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

    本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O ( n ) ,所以我们要在“平衡”方面做一些约束,以防

    2024年02月13日
    浏览(38)
  • 【数据结构】二叉树详解(2)

    ✨ 往期文章链接:二叉树的概念性质 上一篇我们讲了二叉树的结构定义,以及 前序/中序/后序 的递归遍历,还有一些二叉树的接口实现,本篇我们补充一个二叉树的接口 BinaryTreeDepth 。✨上一篇文章链接:二叉树详解(1) 前篇: BinaryTreeDepth 实现: BinaryTreeDepth 递归流程图:

    2024年02月16日
    浏览(36)
  • 【数据结构】二叉树详解(1)

    ✨ 二叉树的概念性质 结构定义: ⭕️ 二叉树的遍历 按照规则,二叉树的遍历分为: 前序/中序/后序的递归遍历。 前序遍历(PreOrder Traversal):访问根节点的操作发生在遍历其左右子树之前。 根 - 左子树 - 右子树 中序遍历(InOrder Traversal):访问根节点的操作发生在遍历左右子

    2024年02月17日
    浏览(52)
  • 【数据结构】搜索二叉树(C++实现)

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 上一篇博客:【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译 二叉搜索树又称二叉排序树,它或者是一棵空

    2024年02月07日
    浏览(52)
  • 【数据结构】AVL树(万字超详细 附动图)

    一、前言 二、AVL树的性质 三、AVL树节点的定义 四、AVL树的插入 五、AVL树的平衡调整 六、AVL树的验证 6.1 验证有序 6.2 验证平衡 七、AVL树的删除 八、AVL树的性能和代码 还没有学习过二叉搜索树的同学可以移步 【数据结构】二叉搜索树-CSDN博客 https://blog.csdn.net/Eristic0618/arti

    2024年04月25日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包