【C++的剃刀】我不允许你还不会AVL树

循环渐进Forward 2024-08-21 09:35:01 阅读 54


db43723fcefb47a09b575a7812877e29.png


 学习编程就得循环渐进,扎实基础,勿在浮沙筑高台  

 循环渐进Forward-CSDN博客


Hello,这里是kiki,今天继续更新C++部分,我们继续来扩充我们的知识面,我希望能努力把抽象繁多的知识讲的生动又通俗易懂,今天要讲的是C++AVL树~


目录

 循环渐进Forward-CSDN博客

AVL树的概念

AVL树节点的定义

AVL树的插入

AVL树的旋转

AVL树的验证 

AVL树的删除(了解)

AVL树的性能


AVL树的概念

二叉搜索树虽可以缩短查找的效率,但

如果数据有序或接近有序二叉搜索树将退化为单支树,查

找元素相当于在顺序表中搜索元素,效率低下

因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法:

当向二叉搜索树中插入新结点后,如果能保证每个结点的左右

子树高度之差的绝对值不超过

1(

需要对树中的结点进行调整

),即可降低树的高度,从而减少平均搜索长度。

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

它的左右子树都是

AVL

左右子树高度之差

(

简称平衡因子

)

的绝对值不超过

1(-1/0/1)

bc35a9db963a447db98d2ec34110f2a3.png

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

AVL

树。如果它有

n

个结点,其高度可保持在

eq?%24O%28log_2%20n%29%24

,搜索时间复杂度

eq?%24O%28log_2%20n%29%24


AVL树节点的定义

<code>template<class T>

struct AVLTreeNode

{

AVLTreeNode(const T& data)

    : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)

, _data(data), _bf(0)

{}

AVLTreeNode<T>* _pLeft;   // 该节点的左孩子

AVLTreeNode<T>* _pRight;  // 该节点的右孩子

AVLTreeNode<T>* _pParent; // 该节点的双亲

T _data;

int _bf;                  // 该节点的平衡因子

};


AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么

AVL树的插入过程可以分为两步:

1.

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

2.

调整节点的平衡因子

bool Insert(const T& data)

{

while (pParent)

{

       // 更新双亲的平衡因子

if (pCur == pParent->_pLeft)

pParent->_bf--;

else

pParent->_bf++;

// 更新后检测双亲的平衡因子

if (0 == pParent->_bf)

      {    

           break;

      }

else if (1 == pParent->_bf || -1 == pParent->_bf)

{

             // 插入前双亲的平衡因子是0,插入后双亲的平衡因为为1 或者 -1 ,说明以双亲

为根的二叉树

             // 的高度增加了一层,因此需要继续向上调整

pCur = pParent;

pParent = pCur->_pParent;

}

else

{

 if(2 == pParent->_bf)

            {

                 // ...

            }

             else

            {

                 // ...

            }

}

}

return true;

}


AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,

使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:

1.

新节点插入较高左子树的左侧

---

左左:右单旋

244858438a414b5aae9534a411d816ce.png


2.

新节点插入较高右子树的右侧

---

右右:左单旋

a3eede8e12d040768e6d8567cbe8bfbc.png


3.

新节点插入较高左子树的右侧

---左右:先左单旋再右单旋        

296f4acc277645a1a2147ccd7fb6fb78.png


将双旋变成单旋后再旋转,即:

先对

30

进行左单旋,然后再对

90

进行右单旋,旋转完成后再

考虑平衡因子的更新。

<code>// 旋转之前,60的平衡因子可能是-1/0/1,旋转完成之后,根据情况对其他节点的平衡因子进

行调整

void _RotateLR(PNode pParent)

{

PNode pSubL = pParent->_pLeft;

PNode pSubLR = pSubL->_pRight;

   

   // 旋转之前,保存pSubLR的平衡因子,旋转完成之后,需要根据该平衡因子来调整其他节

点的平衡因子

int bf = pSubLR->_bf;

   

   // 先对30进行左单旋

_RotateL(pParent->_pLeft);

   

   // 再对90进行右单旋

_RotateR(pParent);

if(1 == bf)

pSubL->_bf = -1;

else if(-1 == bf)

pParent->_bf = 1;

}

4.

新节点插入较高右子树的左侧

---

右左:先右单旋再左单旋

4bb4ebc6225943e89a7979c7d795f111.png

参考右左双旋。

总结:

假如以pParent为根的子树不平衡,即pParent的平衡因子为2或者-2,分以下情况考虑

1. pParent的平衡因子为2,说明pParent的右子树高,设pParent的右子树的根为pSubR

       1、当pSubR的平衡因子为1时,执行左单旋

        2、当pSubR的平衡因子为-1时,执行右左双旋

2. pParent的平衡因子为-2,说明pParent的左子树高,设pParent的左子树的根为pSubL

        1、当pSubL的平衡因子为-1是,执行右单旋

        2、当pSubL的平衡因子为1时,执行左右双旋

旋转完成后,原pParent为根的子树个高度降低,已经平衡,不需要再向上更新。


AVL树的验证 

AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:

1.

验证其为二叉搜索树

        1、如果中序遍历可得到一个有序的序列,就说明为二叉搜索树

2.

验证其为平衡树

        1、每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

        2、节点的平衡因子是否计算正确

<code>int _Height(PNode pRoot);

bool _IsBalanceTree(PNode pRoot)

{

// 空树也是AVL树

if (nullptr == pRoot) return true;

   

// 计算pRoot节点的平衡因子:即pRoot左右子树的高度差

int leftHeight = _Height(pRoot->_pLeft);

int rightHeight = _Height(pRoot->_pRight);

int diff = rightHeight - leftHeight;

// 如果计算出的平衡因子与pRoot的平衡因子不相等,或者

// pRoot平衡因子的绝对值超过1,则一定不是AVL树

if (diff != pRoot->_bf || (diff > 1 || diff < -1))

return false;

// pRoot的左和右如果都是AVL树,则该树一定是AVL树

return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot-

>_pRight);

}


AVL树的删除(了解)

因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。


AVL树的性能

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


 学习编程就得循环渐进,扎实基础,勿在浮沙筑高台




声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。