AVL树的插入删除查找算法实现和分析-2（树高度法）

浅浅的花香味﹌ 2021-09-20 03:14 222阅读 0赞

在前一篇文章（[AVL树的插入删除查找算法实现和分析-1(平衡因子法）][AVL_-1]）中，介绍了如何用平衡因子记录左右子树的高度差的方法来实现AVL树的插入删除和查找的算法，并分析了这种方法的一些缺陷，这里，我将会使用另一种方法来实现这些算法，而且个人觉得比前一篇文章的所写实现更加简单，思路更加清晰。

在介绍这种方法之前，先说说怎么样求一棵二叉树的高度（或深度）。其代码和解释如下：

int BiTreeDepth(BiTree BT)
    {
        //求树的深度
        //从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1，
        //而根结点算第0层，高为0。
        if(BT == NULL)  //若为空树，则返回-1
            return -1;
        else
        {
            int nLDepth = BiTreeDepth(BT->LChild); //求左树的深度
            int nRDepth = BiTreeDepth(BT->RChild); //求右树的深度
            if(nLDepth >= nRDepth)
            {
                return nLDepth+1;
            }
            else
            {
                return nRDepth+1;
            }
        }
    }

明白了怎么求树高后，下面就开始AVL树的插入删除和查找算法的说解：

类型定义为：

typedef int BOOL;
    typedef char DataType;
    
    typedef struct AVLNode
    {
        DataType Data;      //数据值
        struct AVLNode *LChild; //指向左子树的指针
        struct AVLNode *RChild; //指向右子树的指针
        int Height; //记录以此结点为根的树的高度
    }AVLNode, *AVLTree;

其中还有一些要用到辅助函数，如下：

static int Max( int a, int b )
    {
        return (a > b ? a : b);
    }
    //----------------------------------------------------------------------------
    static int Height( AVLTree AT )
    {
        if(AT == NULL)
            return -1;
        return AT->Height;
    }
    
    //--------------------------------------------------------------------------
    AVLTree GetParent(AVLTree AT, DataType x)
    {
        //返回值为x的结点的双亲结点
        if(!AT || AT->Data == x)
            return NULL;
        if((AT->LChild && AT->LChild->Data == x) ||
                (AT->RChild && AT->RChild->Data == x))
            return AT;
        else if((AT->LChild && x < AT->LChild->Data))
            return GetParent(AT->LChild, x);
        else
            return GetParent(AT->RChild, x);
    }
    //--------------------------------------------------------------------------
    AVLNode* FindMin(AVLTree AT)
    {
        //查找最小结点
        if(AT)
        {
            while(AT->LChild)
            {
                AT = AT->LChild;
            }
        }
        return AT;
    }

其旋转的代码和解释如下：

static AVLTree SingleRotateWithRight(AVLTree AT)
    {
        //右单旋转
        if(!AT)
            return NULL;
        AVLTree x = AT->RChild;
        AT->RChild = x->LChild;
        x->LChild = AT;
    
    
        AT->Height = Max(Height(AT->LChild), Height(AT->RChild))+1;
        x->Height = Max(Height(x->RChild), AT->Height)+1;
        //返回新的树根
        return x;
    }
    
    //--------------------------------------------------------------------------
    static AVLTree SingleRotateWithLeft(AVLTree AT)
    {
        //左单旋转
        if(!AT)
            return NULL;
        AVLTree x = AT->LChild;
        AT->LChild = x->RChild;
        x->RChild = AT;
    
        AT->Height = Max(Height(AT->LChild), Height(AT->RChild))+1;
        x->Height = Max(Height(x->LChild), AT->Height) + 1;
        //返回新的树根
        return x;
    }
    //--------------------------------------------------------------------------------
    static AVLTree DoubleRotateWithRight(AVLTree AT)
    {
        //右双旋转，返回新的树根
        if(AT->LChild != NULL)
        {
            AT->LChild = SingleRotateWithLeft(AT->LChild);
            return SingleRotateWithRight(AT);
        }
    }
    //--------------------------------------------------------------------------
    static AVLTree DoubleRotateWithLeft(AVLTree AT)
    {
        //左双旋转，返回新的树根
        if(AT->RChild != NULL )
        {
            AT->RChild = SingleRotateWithRight(AT->RChild);
            return SingleRotateWithLeft(AT);
        }
    }

所有的准备功夫都都好了，下面就是我们的主题：插入、删除和查找了，其代码和解释如下：

AVLNode* InsertNode(AVLTree AT, DataType x)
    {
        //如果x不存在，则插入树中
        if(AT == NULL)
        {
            AT = (AVLTree)malloc(sizeof(AVLNode));
            if (AT == NULL)
            {
                //插入失败
                return NULL;
            }
            else
            {
                //初始化新结点
                AT->Data = x;
                AT->LChild = NULL;
                AT->RChild = NULL;
                AT->Height = 0;
            }
        }
        else
        {
            if (x < AT->Data)
            {
                //在左子树中进行插入
                AT->LChild = InsertNode(AT->LChild, x);
    
                if (Height(AT->LChild) - Height(AT->RChild) == 2)
                {
                    //若失去失衡
                    if (x < AT->LChild->Data)
                    {
                        //若插入在左子树，则进行单左旋转
                        AT = SingleRotateWithLeft(AT);
                    }
                    else
                    {
                        //若插入在右子树，则要进行双左旋转
                        AT = DoubleRotateWithLeft(AT);
                    }
                }
            }
            else if (x > AT->Data)
            {
                //在右子树中进行插入
                AT->RChild = InsertNode(AT->RChild, x);
    
                if (Height(AT->RChild) - Height(AT->LChild) == 2)
                {
                    //若失去失衡
                    if (x > AT->RChild->Data)
                    {
                        //若插入在右子树，则进行单右旋转
                        AT = SingleRotateWithRight(AT);
                    }
                    else
                    {
                        //若插入在左子树，则进行双右旋转
                        AT = DoubleRotateWithRight(AT);
                    }
                }
            }
        }
        //插入后，重新计算树高，并返回新的树的树根指针
        AT->Height = Max(Height(AT->LChild), Height(AT->RChild))+1 ;
        return AT;
    }
    //----------------------------------------------------------------------------------------
    AVLNode* DeleteNode(AVLTree AT, DataType x)
    {
        //若为空树，则返回空，否则返回被删除的结点所属的树根
        if (AT == NULL )
        {
            return NULL;
        }
    
        if(x == AT->Data)
        {
            //找到要删除的结点
            AVLTree Min = FindMin(AT->RChild);
            if(Min != NULL)
            {
                //右子树存在
                AT->Data = Min->Data;
                if(Min != AT->RChild)
                {
                    //AT->RChild存在左子树
                    AVLTree Parent = GetParent(AT->RChild, Min->Data);
                    Parent->LChild = Min->RChild;
                }
                else
                {
                    //AT->RChild不存在左子树
                    AT->RChild = Min->RChild;
                }
            }
            else
            {
                //右子树不存在
                Min = AT;
                AT = AT->LChild;
            }
            free(Min);
        }
        else if(x < AT->Data)
        {
            //在其左子树中进行删除
            AT->LChild = DeleteNode(AT->LChild, x);
            if(Height(AT->RChild) - Height(AT->LChild) == 2)
            {
                //删除后失去平衡
                if(AT->RChild)
                {
                    //若删除后，AT->RChild的左子树比右子树高，则进行左双旋转
                    if(Height(AT->RChild->LChild) > Height(AT->RChild->RChild))
                        AT = DoubleRotateWithLeft(AT);
                    else    //否则，进行左单旋转
                        AT = SingleRotateWithLeft(AT);
                }
            }
        }
    
        else if(x > AT->Data)
        {
            //在其右子树中进行删除
            AT->RChild = DeleteNode(AT->RChild, x);
            if(Height(AT->LChild) - Height(AT->RChild) == 2)
            {
                //删除后失去平衡
                if(AT->LChild)
                {
                    //若删除后，AT->LChild的右子树比左子树高，则进行右双旋转
                    if(Height(AT->LChild->RChild) > Height(AT->LChild->LChild))
                        AT = DoubleRotateWithRight(AT);
                    else    //否则，进行右单旋转
                        AT = SingleRotateWithRight(AT);
                }
            }
        }
        //重新计算AT的深度，并返回删除后的树的根指针
        if (AT != NULL)
        {
            AT->Height = Max(Height(AT->LChild), Height(AT->RChild))+1;
        }
        return AT;
    }
    
    //--------------------------------------------------------------------------------
    
    AVLTree FindATNode(AVLTree AT, DataType c)
    {
        if(!AT)
            return NULL;
        else if(AT->cData == c)//找到则返回其指针
            return AT;
        else if(c < AT->cData)
        {
            //在其左子树中查找
    
            return FindATNode(AT->LChild, c);
        }
        else
        {
            //在其右子树中查找
    
            return FindATNode(AT->RChild, c);
        }
    }

算法分析：

1、这个实现方法是本人觉得比较好的实现方法，其思路比较清晰，代码也比前一篇的容易理解。

2、这个实现方法在没用引用类型的情况下，这种方法如上一篇文章所说，也不需要使用双重指针，减少了出错的机会，也使代码更容易读懂。它改变指针变量的值是通过返回树根的指针并赋值给原来的指针变量来实现的。并且减少了上一篇的算法中大量出现的switch...case语句。

3、至于时间复杂度和空间复杂跟上一篇中的算法实现是一样的，所有的算法的时间复杂度都为log2N。

如算法有错误，还望各位读者指出！

[AVL_-1]: http://blog.csdn.net/ljianhui/article/details/9137177