小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

AVL树详解与实现

作者：小小林熬夜学编程 | 2024-04-30 05:11:00

踩

avl

对AVL树首先要弄清它的定义:AVL树是一棵高度平衡的二叉搜索树,它要么是一棵空树，要么是一棵左右子树均为AVL树,且左右子树高度差的绝对值不大于一的二叉搜索树

数据结构教科书介绍的AVL树平衡化旋转共有四种方式:LR左单旋转,RR右单旋转,LRR先左后右双旋转,RLR先右后左双旋转,LR和RR，LRR和RLR互为镜像,若不熟悉请参看数据结构教科书,下面要对保证AVL树插入删除操作正确性的原理进行简单的讨论。

当在AVL树中删除一个节点时，按对二叉搜索树执行删除节点操作时采用的方式找到待删除节点，但由二叉搜索树删除算法(请参看数据结构教科书)可知，待删除节点不一定是实际删除节点，在某些情况下待删除节点没有被实际删除，而是将非待删除节点的实际删除节点的数据域替换带删除节点的数据域，此后删除的是实际被删除的节点而不是带删除节点，当然在另一些情况下,待删除节点就是实际删除节点。这样每当按对二叉搜索树执行删除操作的方式成功删除(注意待删除节点未必被实际删除)AVL树中的待删除节点后,通过指针定位到实际被删除节点的父节点及该父节点的被实际删除节点的子树的根节点,设指向该父节点的指针为parent，指向实际被删除节点的该父节点的子树的根节点的指针为q(可能为NULL)，那么分别讨论可知,无论在AVL树中对待删除节点执行删除操作对应删除二叉搜索树中节点时可能出现的哪一种情形,以parent为根的子树总满足以下条件A：

1.以parent指向的节点为根节点的子树在执行删除操作前是AVL树(由AVL树定义)

2.以q指向的节点为根节点的子树在被删除一个节点后经过一系列或不经过平衡化旋转后,其高度相比删除前下降一,并且仍然为AVL树

以此为基础我们来寻找循环不变量

现假设存在一棵以parent指向的节点为根节点的二叉搜索树,在对它的子树执行删除操作前它是AVL树且该树是执行删除操作前原AVL树的一棵子树，

若在parent的左子树或右子树上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,左子树的高度相比于删除前下降一并且仍然为AVL树(即parent树满足条件A),q为指向此时该子树根节点的指针,则对parent树而言有如下几种情形:

情形A

以parent指向的节点为根节点的AVL树A在执行删除前根节点平衡因子为0,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为1,由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证这时parent树仍然为AVL树,当然其高度相比于删除前没有任何变化,于是从树A根节点到原AVL树根节点的路径上各节点(除树A根节点)的平衡因子仍然和删除前相同,即这些节点仍然平衡,于是按AVL树的定义从A的根节点的父节点到原树根节点逐层向上递推,最后即得以A根节点到原树父节点的路径上的节点为根节点的子树均为AVL树,当然原树仍然为AVL树，于是可以结束平衡化过程

情形A*

和情形A对称,分析是类似的,此时对树A不做任何平衡化旋转,原树已平衡,结束平衡化过程

情形B

以parent指向的节点为根节点的AVL树A在执行删除前根节点平衡因子为-1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为0，由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证这时parent树仍然为AVL树，且其高度相比于删除节点前下降一,此时不对A做任何平衡化旋转，这样就可以发现树A满足在树A上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,树A的高度相比于删除前下降一并且仍然为AVL树，注意到树A高度降一影响到其根节点父节点平衡因子有可能使其失衡，所以令parent为树A根节点的父节点,q为树A根节点回溯至上一层再按各种情形进行相应的处理。这样做是合理的，因为此时以parent为根的子树(q为parent左子树或右子树根节点)刚好满足条件A，这样就能就各种情形以相同的方式进行同样的处理

情形C

以parent指向的节点为根节点的AVL树A右子树根节点平衡因子为0，在执行删除前根节点平衡因子为1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为2,树A失衡于是对树A做左单旋转，由于作删除操作的AVL树A满足条件A，以此为依据根据AVL树定义不难验证左单旋转后的树A仍然为AVL树,且其高度相比于删除前没有任何变化，于是从树A根节点到原AVL树根节点的路径上各节点(除树A根节点)的平衡因子仍然和删除前相同,即这些节点仍然平衡,于是按AVL树的定义从A的根节点的父节点到原树根节点逐层向上递推,最后即得以A根节点到原树父节点的路径上的节点为根节点的子树均为AVL树,当然原树仍然为AVL树，这样就可以结束平衡化过程

情形C*

和情形C对称,分析是类似的,此时对树A做右单旋转,然后原树已平衡,结束平衡化过程

情形D

以parent指向的节点为根节点的AVL树A右子树根节点平衡因子为1，在执行删除前根节点平衡因子为1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为2，树A失衡于是对树A做左单旋转。由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证左单旋转后的树A仍然为AVL树，且其高度相比于删除节点前下降一,这样就可以发现树A满足在树A上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,树A的高度相比于删除前下降一并且仍然为AVL树，注意到树A高度降一影响到其根节点父节点平衡因子有可能使其失衡，所以令parent为树A根节点的父节点,q为树A根节点回溯至上一层再按各种情形进行相应的处理。这样做是合理的，因为此时以parent为根的子树(q为parent左子树或右子树根节点)刚好满足条件A，这样就能就各种情形以相同的方式进行同样的处理

情形D*

和情形D对称,分析是类似的,此时对树A做右单旋转,然后回溯至上一层继续平衡化

情形E

以parent指向的节点为根节点的AVL树A右子树根节点平衡因子为-1,在执行删除前根节点平衡因子为1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为2，树A失衡于是对树A做先右后左双旋转。由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证先右后左双旋转后的树A仍然为AVL树，且其高度相比于删除节点前下降一,这样就可以发现树A满足在树A上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,树A的高度相比于删除前下降一并且仍然为AVL树，注意到树A高度降一影响到其根节点父节点平衡因子有可能使其失衡，所以令parent为树A根节点的父节点,q为树A根节点回溯至上一层再按各种情形进行相应的处理。这样做是合理的，因为此时以parent为根的子树(q为parent左子树或右子树根节点)刚好满足条件A，这样就能就各种情形以相同的方式进行同样的处理

情形E*

和情形E对称,分析是类似的,此时对树A做先左后右双旋转,然后回溯至上一层继续平衡化

从以上讨论就可以看出循环不变量了,它就是parent子树满足的条件A,如果parent子树满足条件A且对应A,A* 两种情形，则不做平衡化旋转并结束平衡化,如果对应C,C*两种情形，则做单旋转并结束平衡化,如果对应B，B*两种情形则不做平衡化旋转并回溯至上一层平衡化(以parent父节点为根的子树满足条件A),若对应D,D*两种情形则做单旋转并回溯至上一层平衡化(以parent父节点为根的子树满足条件A)，若对应E，E*两种情形，则做双旋转并回溯至上一层平衡化(以parent父节点为根的子树满足条件A).由此可以总结出删除AVL树某节点过程中经历的平衡化过程如下：

从本文开头提及的最初的parent子树开始,该parent子树满足条件A,q为parent子树被删除节点的子树的根节点指针(可能为NULL).

AVL树删除算法(调整平衡因子的细节没有给出,请参考下方代码):

(1)在AVL树上执行二叉搜索树删除算法,之后令parent为实际被删除节点的父节点,q为实际被删节点所在的该父节点的子树的根节点的指针

(2) if(parent子树对应于A,A* C,C*情形)

A,A*情形,直接转3

C情形 parent子树左单旋转, 然后转3

C*情形 parent子树右单旋转, 然后转3

else

B,B*情形如果 parent为根节点转3 否则 q=parent parent=parent父节点转2

D情形 parent子树左单旋转随后如果 parent为根节点转3 否则q=parent parent=parent父节点转2

D*情形 parent子树右单旋转随后如果 parent为根节点转3 否则q=parent parent=parent父节点转2

E情形 parent子树先右后左双旋转随后如果 parent为根节点转3 否则q=parent parent=parent父节点转2

E*情形 parent子树先左后右双旋转随后如果 parent为根节点转3 否则q=parent parent=parent父节点转2

(3)结束

在这里发表一些个人看法,一些数据结构教科书上(如数据结构与算法分析:java语言描述)提到AVL树删除算法的正确编写有一定难度,实际上并非如此.从以上算法来看,编程实现时思路的推进完全是线性的，根本没有难度。非要说实现难度大，那也只能是琐碎的编码细节令人抓狂，事实上从

以上算法来看删除算法本质上非常简单,并不复杂,编写代码只需用心就能正确实现删除算法

下面讨论AVL树的插入

插入操作和删除相比更为简单,实现难度更低，分析插入操作还是要先寻找循环不变量

首先插入新节点后只有新节点父节点至根节点的路径上的节点的平衡因子受影响,以路径上各节点为根的子树的高度要么加一要么不变，即平衡因子要么加减一要么不变。因此路径上各节点的平衡因子在插入新节点后的范围在-2至2之间

按最一般情形考虑，插入新节点(在非空树中插入)后,令parent为新插入节点父节点,q为新插入节点。若插入后parent平衡因子(不是为+-1就是为0)为0,则根据定义不难验证原树已平衡为AVL树,这样就可以结束平衡化过程,若平衡因子为+-1(插入前parent为叶节点),则令q=parent,parent为其父节点,这样parent子树满足条件B:

q为AVL树插入前q平衡因子为0,插入后绝对值为1,q高度相比于插入前加一,且此时没有对q或其子树做平衡化旋转

这样设有一棵原AVL树的子树,根节点为parent,parent的按二叉搜索树插入方式插入节点的子树根节点为q,parent满足条件B。根据节点插入parent右子树或左子树加减parent平衡因子,调整parent平衡因子为插入后平衡因子。然后，

如果parent平衡因子为+-1,则插入前为0，且parent高度相比于插入前加一，插入后parent仍然为AVL树，此时不对parent进行平衡化旋转,由于parent插入后高度加一parent父节点的平衡因子受到影响,因此令q=parent,parent=parent父节点，回溯到上一层按所列各情形进行平衡化操作。这样做是合理的,因为根据上述分析回溯到上一层后parent子树满足条件B，所以完全可以按照各情形以相同方式进行相同处理

如果parent平衡因子为0,则插入前parent平衡因子绝对值为1,即新节点在较矮的子树上插入，插入后parent左右子树等高，不难看出插入后parent子树仍为AVL树且高度相比于插入前不变，于是沿从parent父节点到原AVL树根节点的路径层层向上递推即可验证插入后原树仍为AVL树，故此时可结束平衡化过程

若parent平衡因子绝对值为2,则有以下几种情形:

情形一：

插入后parent平衡因子为-2,q平衡因子为-1,即在q的左子树上插入,左子树在插入后高度加一,q为parent左子树，此时直接对parent做右单旋转，根据做平衡化旋转前的parent树满足条件B和AVL树定义可验证旋转后parent仍然为AVL树，且高度相比于插入前不变，这样原树已平衡，直接结束平衡化过程

情形一*

和情形一对称，插入后parent平衡因子为2,q平衡因子为1,即在q的右子树上插入,右子树在插入后高度加一，q为parent右子树,此时对parent做左单旋转并结束平衡化过程

情形二：

插入后parent平衡因子为-2,q平衡因子为1,即在q的右子树上插入,q为parent左子树，q的右子树插入后高度增一，故必有q的右子女p(树C的根)。由于是在子树p上插入,所以p一定为从最初的parent子树的根节点至q的回溯路径上的一个节点，因此插入后p的平衡因子为+-1,插入前为0，因此一定为在p的两棵等高子树之一上插入,插入后子树p的高度状况如上图所示，此时直接对parent做先左后右双旋转，根据做平衡化旋转前的parent树满足条件B和AVL树定义可验证旋转后parent仍然为AVL树，且高度相比于插入前不变，这样原树已平衡，直接结束平衡化过程

情形二*

和情形二对称，分析是类似的，插入后parent平衡因子为2,q平衡因子为-1,即在q的左子树上插入,q为parent右子树，q的左子树插入后高度增一，故必有q的左子女p(树C的根)。由于是在子树p上插入,所以p一定为从最初的parent子树的根节点至q的回溯路径上的一个节点，因此插入后p的平衡因子为+-1,插入前为0，因此一定为在p的两棵等高子树之一上插入,插入后子树p的高度状况如上图所示，此时直接对parent做先右后左双旋转，根据做平衡化旋转前的parent树满足条件B和AVL树定义可验证旋转后parent仍然为AVL树，且高度相比于插入前不变，这样原树已平衡，直接结束平衡化过程

由以上讨论可以看出循环不变量就是parent子树满足的条件B,如果parent子树满足条件B,那么若parent在插入后的平衡因子绝对值为1，则令q=parent parent=parent父节点回溯到上一层继续按文中列出的情形进行平衡化,若parent在插入后的平衡因子为0,则直接结束平衡化过程,若parent在插入后的平衡因子绝对值为2，此时若parent子树对应情形一则对parent子树执行右单旋转并结束平衡化过程,对应情形一*则对parent子树执行左单旋转并结束平衡化过程，对应情形二则对parent子树执行先左后右双旋转并结束平衡化过程，对应情形二*则对parent子树执行先右后左双旋转并结束平衡化过程。

根据上述分析按和分析删除操作类似的方式就可以总结出AVL树的插入算法，可以自行分析，这里就不赘述了。

下面是删除与插入操作的具体代码实现，代码中加入判断是否为AVL树的代码(非递归)以检验删除操作的正确性，也就是每次删除插入成功后用判断函数检验删除插入后的二叉树是否为AVL树，从而检验插入删除算法的正确性


#include <stack>
#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;
 
#define TYPE int
template <typename T>
struct AVLNode  //AVL树节点类
{
    int bf;  //节点平衡因子
    T data;  //节点数据域
    AVLNode* left;
    AVLNode* right;
    AVLNode(int b, T d) :bf(b), data(d), left(nullptr), right(nullptr) {}
};
 
template <typename T>
void RotateLR(AVLNode<T>*& ptr)  //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针
{
    AVLNode<T>* p = ptr->left;
    AVLNode<T>* q = p->right;
    p->right = q->left;
    q->left = p;
    ptr->left = q->right;
    q->right = ptr;
    if (q->bf == 0)
    {
        p->bf = ptr->bf = 0;
    }
    else
    {
        if (q->bf == -1)
        {
            p->bf = 0;
            ptr->bf = 1;
        }
        else
        {
            p->bf = -1;
            ptr->bf = 0;
        }
        q->bf = 0;
    }
    ptr = q;
}
 
template <typename T>
void RotateRL(AVLNode<T>*& ptr)  //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针
{
    AVLNode<T>* p = ptr->right;
    AVLNode<T>* q = p->left;
    p->left = q->right;
    q->right = p;
    ptr->right = q->left;
    q->left = ptr;
    if (q->bf == 0)
    {
        p->bf = ptr->bf = 0;
    }
    else
    {
        if (q->bf == -1)
        {
            p->bf = 1;
            ptr->bf = 0;
        }
        else
        {
            p->bf = 0;
            ptr->bf = -1;
        }
        q->bf = 0;
    }
    ptr = q;
}
 
template <typename T>
void RotateR(AVLNode<T>*& ptr)  //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针
{
    AVLNode<T>* p = ptr->left;
    ptr->left = p->right;
    p->right = ptr;
    if (p->bf == -1)
    {
        p->bf = ptr->bf = 0;
    }
    else
    {
        p->bf = 1;
    }
    ptr = p;
}
 
template <typename T>
void RotateL(AVLNode<T>*& ptr)  //对以ptr为根的子树执行左单旋转, ptr成为旋转后新树根节点指针
{
    AVLNode<T>*p = ptr->right;
    ptr->right = p->left;
    p->left = ptr;
    if (p->bf == 0)
    {
        p->bf = -1;
        ptr->bf = 1;
    }
    else
    {
        ptr->bf = p->bf = 0;
    }
    ptr = p;
}
 
template <typename T>
int Searchd(AVLNode<T>* ptr, int d)
{
    if (d == 2)
        return 0;
    else
    {
        if (d == 1)
        {
            if (ptr->right == nullptr)
                return 0;
            else
                return 2;
        }
        else
        {
            if (ptr->left != nullptr)
                return 1;
            else
            {
                if (ptr->right != nullptr)
                    return 2;
                else
                    return 0;
            }
        }
    }
}
 
template <typename T>
bool isAVL(AVLNode<T>* root)  //判断以root为根节点的二叉树是否为AVL树
{
    struct memory
    {
        AVLNode<T>* p;
        int direction;
        T lmin;
        int lh = 0;   //节点左子树高度
        memory(AVLNode<T>* p, int d) :p(p), direction(d) {}
    };
    T rmin;
    T rmax;
    T lmax;
    int rh;
    int d = 0;
    AVLNode<T>* ptr = root;
    AVLNode<T>* const dest = ptr;
    stack<memory> arrange;
    bool TF = false;
    while (true)
    {
        if (Searchd(ptr, d) == 0)
        {
            if (ptr == dest)
            {
                if (d == 0)
                    return true;
            }
 
            if (d == 0)
            {
                if (arrange.top().direction == 1)
                {
                    arrange.top().lh = 1;
                    arrange.top().lmin = ptr->data;
                    lmax = ptr->data;
                }
                else
                {
                    rh = 1;
                    rmin = ptr->data;
                    rmax = ptr->data;
                }
            }
            else
            {
                if (d == 1)
                {
                    if (lmax >= ptr->data)
                    {
                        cout << "当前树非二叉搜索树,也非AVL树" << endl;
                        return false;
                    }
 
                    if (arrange.top().lh > 1)
                    {
                        cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
                        return false;
                    }
 
                    if (ptr == dest)
                        return true;
 
                    T lmin = arrange.top().lmin;
                    int lh = arrange.top().lh;
                    arrange.pop();
                    if (arrange.top().direction == 1)
                    {
                        arrange.top().lmin = lmin;
                        arrange.top().lh = lh + 1;
                        lmax = ptr->data;
                    }
                    else
                    {
                        rmin = lmin;
                        rmax = ptr->data;
                        rh = lh + 1;
                    }
 
                }
                else
                {
                    if (rmin <= ptr->data)
                    {
                        cout << "当前树非二叉搜索树,也非AVL树" << endl;
                        return false;
                    }
 
                    if (abs(rh - arrange.top().lh) > 1)
                    {
                        cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
                        return false;
                    }
 
                    if (ptr == dest)
                        return true;
 
                    if (ptr->left == nullptr)
                    {
                        arrange.pop();
                        if (arrange.top().direction == 1)
                        {
                            arrange.top().lmin = ptr->data;
                            lmax = rmax;
                            arrange.top().lh = rh + 1;
                        }
                        else
                        {
                            rmin = ptr->data;
                            ++rh;
                        }
                    }
                    else
                    {
                        T lmin = arrange.top().lmin;
                        int lh = arrange.top().lh;
                        arrange.pop();
                        if (arrange.top().direction == 1)
                        {
                            arrange.top().lmin = lmin;
                            arrange.top().lh = max(lh, rh) + 1;
                            lmax = rmax;
                        }
                        else
                        {
                            rmin = lmin;
                            rh = max(lh, rh) + 1;
                        }
                    }
                }
            }
            ptr = arrange.top().p;
            d = arrange.top().direction;
        }
        else
        {
            AVLNode<T>* interval = nullptr;
            if (d == 0)
            {
                arrange.push(memory(ptr, Searchd(ptr, d)));
                if (arrange.top().direction == 1)
                    ptr = ptr->left;
                else
                    ptr = ptr->right;
            }
            else
            {
                if (ptr->data <= lmax)
                {
                    cout << "当前树非二叉搜索树,也非AVL树" << endl;
                    return false;
                }
                arrange.top().direction = 2;
                ptr = ptr->right;
            }
            d = 0;
        }
    }
}
 
template <typename T>
void linkWithUpper(AVLNode<T>* parent, AVLNode<T>* original, AVLNode<T>* _new)
{
    if (original == parent->left)
    {
        parent->left = _new;
    }
    else
    {
        parent->right = _new;
    }
}
 
template <typename T>
bool executeDelete(AVLNode<T>*& parent, AVLNode<T>*& q, AVLNode<T>* p, AVLNode<T>* left_or_right, stack<AVLNode<T>*>& stackforflashback)
{
    if (stackforflashback.empty())  //被删节点有父节点
    {
        parent = left_or_right;
        delete p;         //删除被删节点后原AVL树恢复平衡,parent为根节点结束
        return true;
    }
 
    parent = stackforflashback.top();
    stackforflashback.pop();
    if (parent->left == p)
        parent->left = left_or_right;                    //将被删节点左子树或右子树链接至被删节点父节点相应链指针，并删除被删节点
    else
        parent->right = left_or_right;
    q = left_or_right;     //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树或右子树根节点指针
    delete p;
    return false;
}
 
 
template <typename T>
void executeDelete(AVLNode<T>*& q, AVLNode<T>* p, AVLNode<T>*& left_or_right)
{
    left_or_right = q->right;  //left_o_right为parent->left时用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针,随后删除该节点
    p->data = q->data;        //left_o_right为p->right时用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针,并删除右子女
    delete q;
    q = left_or_right; //left_o_right为parent->left时parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针
}
 
template <typename T>
AVLNode<T>* DelAVL(AVLNode<T>* root, T key)  //在以root为根节点的AVL树中删除关键码key
{
    //AVL树的删除
    AVLNode<T>* p = root;
    stack<AVLNode<T>*> stackforflashback;
    while (p != nullptr)         //搜索被删除节点,同时将回溯路径记录在栈中
    {
        if (p->data == key)
            break;
        else
        {
            stackforflashback.push(p);
            if (key < p->data)
            {
                p = p->left;
            }
            else
            {
                p = p->right;
            }
        }
    }
 
    if (p != nullptr)  //被删除节点存在,被p指向
    {
        AVLNode<T>* parent = nullptr;
        AVLNode<T>* q = nullptr;
        if (p->left != nullptr && p->right != nullptr)   //被删节点左右子树均存在
        {
            q = p->right;
            parent = p;
            if (q->left != nullptr)   //被删节点右子树根节点有左子树
            {
                while (q->left != nullptr)  //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径
                {
                    stackforflashback.push(parent);
                    parent = q;
                    q = q->left;
                }
                executeDelete(q, p, parent->left);
            }
            else
                executeDelete(q, p, p->right);
        }
        else
        {
            if (p->left != nullptr)  //被删节点左子树不空,右子树空
            {
                if (executeDelete(parent, q, p, p->left, stackforflashback))
                    return parent;
            }
            else if (p->right != nullptr)  //处理过程和以上情形完全对称
            {
                if (executeDelete(parent, q, p, p->right, stackforflashback))
                    return parent;
            }
            else        //被删节点为叶节点
            {
                if (executeDelete(parent, q, p, static_cast<AVLNode<T>*>(nullptr), stackforflashback))
                    return parent;
            }
        }
        bool TF = false;
        if (parent->right == nullptr && parent->left == nullptr)
        {
            parent->bf = 0;
            if (stackforflashback.empty())
                return root;
            q = parent;
            parent = stackforflashback.top();
            stackforflashback.pop();
 
        }
        bool before;
        do
        {
            if (TF == true)
            {
                if (!before)
                {
                    linkWithUpper(stackforflashback.top(), q, parent);
                    if (parent->bf != 0)
                        return root;
                }
                q = parent;
                parent = stackforflashback.top();
                stackforflashback.pop();
            }
            else
            {
                TF = true;
            }
 
            bool l = parent->left == q;
            if (parent->bf == 0)
            {
                if (l)
                    parent->bf = 1;   //情形a
                else
                    parent->bf = -1; //情形a*
                return root;
            }  
 
            if (l ? parent->bf == 1 : parent->bf == -1)
            {
                q = parent;
                if (l)
                {
                    p = parent->right;
                    if (p->bf != -1)
                        RotateL(parent);    //对以parent为根的子树执行左单旋转 //情形c     //情形d   //对以parent为根的子树执行左单旋转
                    else            //情形e
                        RotateRL(parent);//对以parent为根的子树执行先右后左双旋转
                }
                else
                {
                    p = parent->left;
                    if (p->bf != 1)          //情形c*
                        RotateR(parent);//对以parent为根的子树执行右单旋转  //情形d*     //对以parent为根的子树执行右单旋转
                    else    //情形e*
                        RotateLR(parent);//对以parent为根的子树执行先左后右双旋转
                }
                before = false;
            }
            else
            {
                before = true;
            }
 
            if (before)
                parent->bf = 0;
        } while (stackforflashback.empty() == false);
        return parent;   //原AVL树已恢复平衡,返回根节点
    }
    else
    {
        cout << "AVL树中不存在要删除的数据元素,删除失败" << endl;
        return nullptr;
    }
}
 
template <typename T>
AVLNode<T>* InsertAVL(AVLNode<T>* root, T key)
{
    //AVL树的插入
    if (root == nullptr)
        return new AVLNode<T>(0, key);
    else
    {
        stack<AVLNode<T>*> stackforflashback;
        AVLNode<T>* p = root;
        while (p != nullptr)   //搜索插入位置
        {
            stackforflashback.push(p);
            if (key < p->data)
                p = p->left;
            else if (key > p->data)
                p = p->right;
            else
            {
                cout << "要插入的关键字在AVL树中已存在,插入失败" << endl;
                return nullptr;
            }
        }
 
        p = new AVLNode<T>(0, key);
        if (key < stackforflashback.top()->data)
        {
            stackforflashback.top()->left = p;   //新节点插入并调整父节点平衡因子
        }
        else
        {
            stackforflashback.top()->right = p;
        }
 
        AVLNode<T>* parent = nullptr;
        while (stackforflashback.empty() == false)
        {
            parent = stackforflashback.top();
            stackforflashback.pop();
 
            if (parent->left == p)
                --parent->bf;
            else
                ++parent->bf;
 
            if (parent->bf == 0)
                return root;   //已平衡,返回根节点
            else if (parent->bf == -1 || parent->bf == 1)
                p = parent;  //以parent为根的子树已平衡其高度加一回溯至父节点
            else
            {
                AVLNode<T>* q = parent;
                if (parent->bf == -2)
                {
                    if (p->bf == 1)
                        RotateLR(parent);//对parent为根的子树执行先左后右双旋转 //已平衡
 
                    else
                        RotateR(parent);//对以parent为根子树执行右单旋转 //已平衡
                }
                else
                {
                    if (p->bf == -1)
                    {
                        RotateRL(parent);//对parent为根的子树执行先右后左双旋转 //已平衡
                    }
                    else
                    {
                        RotateL(parent);//对以parent为根的子树执行左单旋转 //已平衡
                    }
                }
                if (stackforflashback.empty() == false)
                {
                    linkWithUpper(stackforflashback.top(), q, parent);
                    return root;               //返回恢复平衡的AVL树根节点
                }
                return parent;
            }
        }
        return p;   //原AVL树已平衡,返回根节点
    }
}
 
template <typename T>
struct memory
{
    AVLNode<T>* p;
    int direction;
    int last;
    memory(AVLNode<T>* p, int d, int l) :p(p), direction(d), last(l) {}
};
 
template <typename T>
void set(stack<memory<T>>& arrange)
{
    if (arrange.top().last == 0)
    {
        if (arrange.top().direction == 1)
        {
            arrange.top().last = 1;
        }
        else
        {
            cout << " ,";
            arrange.top().last = 2;
        }
    }
    else
    {
        cout << ",";
        arrange.top().last = 2;
    }
}
 
template <typename T>
void output(AVLNode<T>* ptr)  //输出以ptr为根的AVL树对应的广义表形式
{
    int d = 0;
    AVLNode<T>* const dest = ptr;
    stack<memory<T>> arrange;
    while (true)
    {
        if (Searchd(ptr, d) == 0)
        {
            if (ptr == dest)
            {
                if (d == 0)
                    cout << ptr->data << "(";
                else
                {
                    if (arrange.top().last == 1)
                        cout << ", ";
                }
                cout << ")";
                break;
            }
            else
            {
                if (d == 0)
                {
                    set(arrange);
                    cout << ptr->data;
                }
                else
                {
                    if (arrange.top().last != 2)
                        cout << ", ";
                    cout << ")";
                    arrange.pop();
                }
                ptr = arrange.top().p;
                d = arrange.top().direction;
            }
        }
        else
        {
            AVLNode<T>* interval = nullptr;
            if (d == 0)
            {
                if (arrange.empty() == false)
                    set(arrange);
                cout << ptr->data << "(";
                arrange.push(memory<T>(ptr, Searchd(ptr, d), 0));
                if (arrange.top().direction == 1)
                    ptr = ptr->left;
                else
                    ptr = ptr->right;
            }
            else
            {
                arrange.top().direction = 2;
                ptr = ptr->right;
            }
            d = 0;
        }
    }
}
 
void printNULL(size_t num)
{
    for (size_t o = 1; o <= num; ++o)
        cout << " ";
    cout << "NULL" << endl;
}
 
template <typename T>
void printAVLTree(AVLNode<T>* root, size_t offset)
{
    if (root == nullptr)
        cout << "NULL空树" << endl;;
    for (int i = 1; i <= offset; ++i)
        cout << " ";
    string s = to_string(root->data);
    offset += s.size() + 4;
    cout << s << ":" << "bf=";
 
    if (root->bf == -1)
    {
        cout << "-1";
        offset += 2;
    }
    else if (root->bf == 1)
    {
        cout << "+1";
        offset += 2;
    }
 
    else
    {
        cout << "0";
        offset += 1;
    }
 
    cout << endl;
    if (root->left == nullptr)
    {
        if (root->right != nullptr)
        {
            printNULL(offset);
            printAVLTree(root->right, offset);
        }
    }
    else
    {
        printAVLTree(root->left, offset);
        if (root->right == nullptr)
        {
            printNULL(offset);
        }
        else
            printAVLTree(root->right, offset);
 
    }
}
 
int main()
{
    const int N = 2000;
    //vector<TYPE> insertvalue{ 13, 5, 3, 2, 1, 4, 10, 8, 7, 6, 9, 11, 12, 16, 14, 15, 18, 17, 20, 19 };
    vector<TYPE> insertvalue;
    for (int i = 1; i <= N; ++i)
    {
        insertvalue.push_back(i);
    }
 
    shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine());
    AVLNode<TYPE>* root = nullptr;
    for (vector<TYPE>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p)
    {
        cout << "插入节点" << *p << endl;
        root = InsertAVL(root, *p);
        //output(root);
        cout << endl;
        if (isAVL(root) == true)
        {
            cout << "当前树是AVL树";
            cout << endl;
        }
        else
        {
            cerr << "错误当前树不是AVL树!" << endl;
            exit(0);
        }
    }
    cout << endl;
    //cout << "插入完成后删除前AVL树为:" << endl;
    //printAVLTree(root, 0);
    //cout << "插入完成后删除前AVL树对应的广义表形式为:" << endl;
    //output(root);
    cout << endl;
    cout << endl;
    for (vector<TYPE>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p)
    {
        cout << "删除节点" << *p << endl;
        root = DelAVL(root, *p);
        if (root != nullptr)
        {
            //printAVLTree(root, 0);
            cout << endl;
            if (isAVL(root) == true)
            {
                cout << "当前树是AVL树";
                cout << endl;
            }
            else
            {
                cerr << "错误当前树不是AVL树!" << endl;
                exit(0);
            }
        }
        else
            cout << "NULL";
        cout << endl;
    }
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/511559