平等步一步写平衡二叉树(AVL树)

一如既往步一步写平衡二叉树(AVL树)

作者:C小加 更新时间:2012-8-20

  平衡二叉树(Balanced Binary
Tree)是二叉查找树的一个进化体,也是首先独引入平衡概念的二叉树。1962年,G.M.
Adelson-Velsky 同 E.M.
Landis发明了当下棵树,所以她而为AVL树。平衡二叉树要求于各级一个节点的话,它的左右子树的莫大的差不可知跳1,如果插入或者去一个节点使得高度的异大于1,就假设开展节点内的团团转,将二叉树重新维持在一个平衡状态。这个方案特别好之化解了二叉查找树退化成链表的问题,把插入,查找,删除的时刻复杂度最好状态与最好特别情况都维持以O(logN)。但是频繁旋转会如插入和去牺牲掉O(logN)左右之日子,不过相对二叉查找树来说,时间及稳定了诸多。

图片 1

  平衡二叉树实现之大多数进程与二叉查找树是如出一辙的(学平衡二叉树之前一定要会二叉查找树),区别就是在于插入和去后要描绘一个转悠算法去维持平衡,维持平衡要依赖一个节点高度的属性。我参考了机械工业出版社的《数据结构与算法分析-C语言描述》写了一个C++版的代码。这按照开之AVLTree讲的酷好,不过并未生完整的夺讲述。我会一步一步之讲授如何勾勒平衡二叉树,重点是平衡二叉树的骨干组成部分,也就是转算法。

率先步:节点信息

  相对于二叉查找树的节点吧,我们需要用一个特性二叉树的万丈,目的是保安插入和去过程被的旋转算法。

代码如下:

//AVL树节点信息
template<class T>
class TreeNode
{
    public:
        TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}
        T data;//值
        int hgt;//以此节点为根的树的高度
        unsigned int freq;//频率
        TreeNode* lson;//指向左儿子的地址
        TreeNode* rson;//指向右儿子的地址
};

次步:平衡二叉树类的声明

  声明中之盘函数将当背后的步子中详解。

代码如下:

//AVL树类的属性和方法声明
template<class T>
class AVLTree
{
    private:
        TreeNode<T>* root;//根节点
        void insertpri(TreeNode<T>* &node,T x);//插入
        TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找
        void insubtree(TreeNode<T>* node);//中序遍历
        void Deletepri(TreeNode<T>* &node,T x);//删除
        int height(TreeNode<T>* node);//求树的高度
        void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转
        void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转
        void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转
        void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转
        int Max(int cmpa,int cmpb);//求最大值

    public:
        AVLTree():root(NULL){}
        void insert(T x);//插入接口
        TreeNode<T>* find(T x);//查找接口
        void Delete(T x);//删除接口
        void traversal();//遍历接口

};

老三步:两单援助方法

  旋转算法需要借助两只效益的佑助,一个凡是求树的高度,一个凡求少个惊人的绝老价值。这里规定,一棵空树的可观也-1,只发一个根节点的扶植的冲天为0,以后每多同叠高度加1。为了化解指针NULL这种状况,写了一个求高度的函数,这个函数还是老有必不可少之。

代码如下:

//计算以节点为根的树的高度
template<class T>
int AVLTree<T>::height(TreeNode<T>* node)
{
    if(node!=NULL)
        return node->hgt;
    return -1;
}
//求最大值
template<class T>
int AVLTree<T>::Max(int cmpa,int cmpb)
{
    return cmpa>cmpb?cmpa:cmpb;
}

第四步:旋转

  对于一个平衡的节点,由于自由节点最多来半点独儿子,因此高度不平衡时,此节点的简单粒子树的惊人不等2.善看,这种无平衡油然而生在底下四种状态:

图片 2

  1、6节碰之左子树3节点高度比较右子树7节点大2,左子树3节点的左子树1节点高度过右子树4节点,这种场面成为左左。

  2、6节触及的左子树2节点高度比右子树7节点大2,左子树2节沾之左子树1节点高度小于右子树4节点,这种状况成为左右。

  3、2节触及之左子树1节点高度比较右子树5节点小2,右子树5节点的左子树3节点高度过右子树6节点,这种情况成为右左。

  4、2节触及的左子树1节点高度比右子树4节点小2,右子树4节点的左子树3节点高度小于右子树6节点,这种场面成为右右。

  从图2中得以好看来,1和4简单栽状态是针对如的,这点儿种情景的转动算法是一模一样的,只需要经同不成盘就足以达到目标,我们叫单旋转。2及3零星种状况吧是指向如之,这简单栽情景的旋转算法为是相同的,需要开展有限次盘,我们誉为双转悠。

第五步:单旋转

  单旋转是对准于左左和右侧右这片栽状况的缓解方案,这简单种植状态是本着如之,只要解决了左左这种状况,右右就坏好惩治了。图3凡是不对左情况的化解方案,节点k2不饱平衡特性,因为其的左子树k1比右子树Z深2交汇,而且k1子树中,更怪的同样重叠的凡k1的左子树X子树,所以属于左左情况。

图片 3

  为使培训恢复平衡,我们将k1变成这棵树的一干二净节点,因为k2大于k1,把k2置于k1的右子树上,而本来在k1右子树的Y大于k1,小于k2,就将Y置于k2的左子树上,这样既满足了二叉查找树的属性,又满足了平衡二叉树的性能。

  这样的操作才待有的指南针改变,结果我们获得另外一粒二叉查找树,它是一棵AVL树,因为X向上一样移动了相同重叠,Y还栖息于原来的面上,Z向下走了同样层。整棵树的初高度和事先从未以左子树上插入的冲天一样,插入操作使得X高度长高了。因此,由于当下颗子树高度没有变化,所以往根节点的门路就是未需要继续旋转了。

代码如下:

//左左情况下的旋转
template<class T>
void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2)
{
    TreeNode<T>* k1;
    k1=k2->lson;
    k2->lson=k1->rson;
    k1->rson=k2;

    k2->hgt=Max(height(k2->lson),height(k2->rson))+1;
    k1->hgt=Max(height(k1->lson),k2->hgt)+1;
}
//右右情况下的旋转
template<class T>
void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2)
{
    TreeNode<T>* k1;
    k1=k2->rson;
    k2->rson=k1->lson;
    k1->lson=k2;

    k2->hgt=Max(height(k2->lson),height(k2->rson))+1;
    k1->hgt=Max(height(k1->rson),k2->hgt)+1;
}

第六步:双旋转

  对于左右同右手左立半种植情况,单旋转不能够如它达到一个平衡状态,要经简单次等盘。双盘是针对为即简单种植情景的化解方案,同样的,这样简单栽情况吗是本着如之,只要解决了左右这种状况,右左就特别好惩治了。图4是左右情况的解决方案,节点k3不饱平衡特性,因为她的左子树k1比右子树Z深2叠,而且k1子树中,更怪的等同层的凡k1的右子树k2子树,所以属于左右状况。

图片 4

   为使培训恢复平衡,我们要进行个别步,第一步,把k1作为根本,进行相同涂鸦右右旋转,旋转之后虽变成了左左情况,所以亚步再开展同样不成错误左旋转,最后获得了同样株以k2为清之抵二叉树树。

代码如下:

//左右情况的旋转
template<class T>
void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3)
{
    SingRotateRight(k3->lson);
    SingRotateLeft(k3);
}
//右左情况的旋转
template<class T>
void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3)
{
    SingRotateLeft(k3->rson);
    SingRotateRight(k3);
}

 第七步:插入

  插入的不二法门以及二叉查找树基本雷同,区别是,插入完成后待从插入的节点开始保护一个届根本节点的路子,每经一个节点都使保全树的平衡。维持树的抵要依据高度差之特性选择不同的旋算法。

代码如下:

//插入
template<class T>
void AVLTree<T>::insertpri(TreeNode<T>* &node,T x)
{
    if(node==NULL)//如果节点为空,就在此节点处加入x信息
    {
        node=new TreeNode<T>();
        node->data=x;
        return;
    }
    if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中插入x
    {
        insertpri(node->lson,x);
        if(2==height(node->lson)-height(node->rson))
            if(x<node->lson->data)
                SingRotateLeft(node);
            else
                DoubleRotateLR(node);
    }
    else if(node->data<x)//如果x大于节点的值,就继续在节点的右子树中插入x
    {
        insertpri(node->rson,x);
        if(2==height(node->rson)-height(node->lson))//如果高度之差为2的话就失去了平衡,需要旋转
            if(x>node->rson->data)
                SingRotateRight(node);
            else
                DoubleRotateRL(node);
    }
    else ++(node->freq);//如果相等,就把频率加1
    node->hgt=Max(height(node->lson),height(node->rson));
}
//插入接口
template<class T>
void AVLTree<T>::insert(T x)
{
    insertpri(root,x);
}

第八步:查找

及二叉查找树相比,查找方法没有变法,不过根据存储的特征,AVL树能保持于一个O(logN)的安居乐业的日,而二叉查找树则一定不安宁。

代码如下:

//查找
template<class T>
TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x)
{
    if(node==NULL)//如果节点为空说明没找到,返回NULL
    {
        return NULL;
    }
    if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中查找x
    {
        return findpri(node->lson,x);
    }
    else if(node->data<x)//如果x大于节点的值,就继续在节点的左子树中查找x
    {
        return findpri(node->rson,x);
    }
    else return node;//如果相等,就找到了此节点
}
//查找接口
template<class T>
TreeNode<T>* AVLTree<T>::find(T x)
{
    return findpri(root,x);
}

第九步:删除

  删除的方法吗同二叉查找树的均等,区别是,删除完成后,需要打去节点的生父开始上扬维护树的抵一直到根本节点。

代码如下:

//删除
template<class T>
void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x)
{
    if(node==NULL) return ;//没有找到值是x的节点
    if(x < node->data)
    {
         Deletepri(node->lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x
         if(2==height(node->rson)-height(node->lson))
            if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) )
                DoubleRotateRL(node);
            else
                SingRotateRight(node);
    }

    else if(x > node->data)
    {
         Deletepri(node->rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x
         if(2==height(node->lson)-height(node->rson))
            if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))
                DoubleRotateLR(node);
            else
                SingRotateLeft(node);
    }

    else//如果相等,此节点就是要删除的节点
    {
        if(node->lson&&node->rson)//此节点有两个儿子
        {
            TreeNode<T>* temp=node->rson;//temp指向节点的右儿子
            while(temp->lson!=NULL) temp=temp->lson;//找到右子树中值最小的节点
            //把右子树中最小节点的值赋值给本节点
            node->data=temp->data;
            node->freq=temp->freq;
            Deletepri(node->rson,temp->data);//删除右子树中最小值的节点
            if(2==height(node->lson)-height(node->rson))
            {
                if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))
                    DoubleRotateLR(node);
                else
                    SingRotateLeft(node);
            }
        }
        else//此节点有1个或0个儿子
        {
            TreeNode<T>* temp=node;
            if(node->lson==NULL)//有右儿子或者没有儿子
            node=node->rson;
            else if(node->rson==NULL)//有左儿子
            node=node->lson;
            delete(temp);
            temp=NULL;
        }
    }
    if(node==NULL) return;
    node->hgt=Max(height(node->lson),height(node->rson))+1;
    return;
}
//删除接口
template<class T>
void AVLTree<T>::Delete(T x)
{
    Deletepri(root,x);
}

第十步:中序遍历

代码如下:

//中序遍历函数
template<class T>
void AVLTree<T>::insubtree(TreeNode<T>* node)
{
    if(node==NULL) return;
    insubtree(node->lson);//先遍历左子树
    cout<<node->data<<" ";//输出根节点
    insubtree(node->rson);//再遍历右子树
}
//中序遍历接口
template<class T>
void AVLTree<T>::traversal()
{
    insubtree(root);
}

第十一步:关于效率

  此数据结构插入、查找和去的岁月复杂度均为O(logN),但是插入和去需要额外的团团转算法需要的时,有时转动过多呢会潜移默化效率。

  关于递归和非递归。我之所以之是递归的办法开展插队,查找和去,而未递归的主意一般的话要于递归的法门抢多,但是自己深感非递归的章程勾勒出来会比较艰难,所以自己还是选择了递归的法。

  还有平等种植效率的题材是关于高度信息的囤积,由于我们要之独自是惊人的不同,不欲了解就株树之莫大,所以就待使用有限单二进制位就得代表这差。这样可以避免平衡因子的重新计算,可以略的增速局部进度,不过代码也丧失了相对简明性和清晰度。如果运用递归写法的话,这种微加速就还显微不足道了。

 

  如果发什么不对的要无清晰的地方要指出,我会改并加以完善。

   附:整体代码

 

相关文章