欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

图解数据结构树之AVL树

程序员文章站 2022-10-09 12:02:35
AVL树(平衡二叉树): AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图: 平衡因子 ......

avl树(平衡二叉树):

avl树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在avl树中任何节点的两个子树的高度最大差别为一,所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图:

图解数据结构树之AVL树

平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1;

avl树的作用:

我们知道,对于一般的二叉搜索树(binary search tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(o(log2n))同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即o(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度。

例如:我们按顺序将一组数据1,2,3,4,5,6分别插入到一颗空二叉查找树和avl树中,插入的结果如下图:

图解数据结构树之AVL树

图解数据结构树之AVL树

由上图可知,同样的结点,由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下,会导致二叉树的高度是o(n),而avl树就不会出现这种情况,树的高度始终是o(lgn).高度越小,对树的一些基本操作的时间复杂度就会越小。这也就是我们引入avl树的原因

avl树的基本操作:

avl树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除!

我们知道,avl树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏avl树的平衡性。同理,在删除的时候也有可能会破坏树的平衡性,所以我们要做一些特殊的处理,包括:单旋转和双旋转!

avl树的插入,单旋转的第一种情况---右旋:

图解数据结构树之AVL树

由上图可知:在插入之前树是一颗avl树,而插入之后结点t的左右子树高度差的绝对值不再 < 1,此时avl树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点t的左结点的左子树上做了插入元素的操作,我们称这种情况为左左情况,我们应该进行右旋转(只需旋转一次,故是单旋转)。具体旋转步骤是:

t向右旋转成为l的右结点,同时,y放到t的左孩子上。这样即可得到一颗新的avl树,旋转过程图如下:

图解数据结构树之AVL树

左左情况的右旋举例:

图解数据结构树之AVL树

avl树的插入,单旋转的第一种情况---左旋:

图解数据结构树之AVL树

由上图可知:在插入之前树是一颗avl树,而插入之后结点t的左右子树高度差的绝对值不再 < 1,此时avl树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点t的右结点的右子树上做了插入元素的操作,我们称这种情况为右右情况,我们应该进行左旋转(只需旋转一次,故事单旋转)。具体旋转步骤是:

t向右旋转成为r的左结点,同时,y放到t的左孩子上。这样即可得到一颗新的avl树,旋转过程图如下:

图解数据结构树之AVL树

右右情况的左旋举例:
图解数据结构树之AVL树

以上就是插入操作时的单旋转情况!我们要注意的是:谁是t谁是l,谁是r还有谁是x,y,z!t始终是开始不平衡的左右子树的根节点。显然l是t的左结点,r是t的右节点。x、y、y是子树当然也可以为null.null归null,但不能破坏插入时我上面所说的左左情况或者右右情况。

avl树的插入,双旋转的第一种情况---左右(先左后右)旋:

图解数据结构树之AVL树

由  上图可知,我们在t结点的左结点的右子树上插入一个元素时,会使得根为t的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的右旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:

图解数据结构树之AVL树

左右情况的左右旋转实例:

图解数据结构树之AVL树

avl树的插入,双旋转的第二种情况---右左(先右后左)旋:

图解数据结构树之AVL树

由上图可知,我们在t结点的右结点的左子树上插入一个元素时,会使得根为t的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的左旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:

图解数据结构树之AVL树

右左情况的右左旋转实例:

图解数据结构树之AVL树

avl树的插入代码实现:(仅供参考)

懂了以上单旋转和双旋转的原理之后,那么代码写起来也就比较简单了,以下是我写的代码,如果有错还望大家不吝指正。(参考数据结构与算法分析-weiss著)

#include <iostream>
#include <stdlib.h>

using namespace std;

#define datatype int

/*
    定义avl树的结构体,链式
*/
typedef struct avlnode{
    datatype    data;
    avlnode    * m_pleft;
    avlnode    * m_pright;
    int height;
}*avltree,*position,avlnode;

//求两个数的最大值
int max(int a,int b)
{
    return a>b?a:b;
}
//求树的高度
int height( avltree t)
{
    if(null == t)
        return -1;
    else
        return t->height;
}

//单旋转右旋
avltree singlerotatewithright(avltree t)
{
    avltree l = t->m_pleft;
    t->m_pleft = l->m_pright;
    l->m_pright = t;
    t->height = max( height(t->m_pleft),height(t->m_pright) ) + 1;
    l->height = max( height(l->m_pleft),height(l->m_pright) ) + 1;
    return l;    //此时l成为根节点了(可参考avl的插入的左左情况的右旋图)
}
//单旋转左旋
avltree singlerotatewithleft(avltree t)
{
    avltree r = t->m_pright;
    t->m_pright = r->m_pleft;
    r->m_pleft = t;
    t->height = max( height(t->m_pleft),height(t->m_pright) ) + 1;
    r->height = max( height(r->m_pleft),height(r->m_pright) ) + 1;
    return r;    //此时r成为根节点了(可参考avl的插入的左左情况的左旋图)
}
//双旋转,先左后右
avltree doublerotatewithleft(avltree t)        //先左后右
{
    t->m_pleft = singlerotatewithleft(t->m_pleft);
    return singlerotatewithright(t);
}
//双旋转,先右后左
avltree doublerotatewithright(avltree t)    //先右后左
{
    t->m_pright = singlerotatewithright(t->m_pright);
    return singlerotatewithleft(t);
}
avltree avltreeinsert(avltree t, datatype x)
{
    if(t == null)    //如果树为空
    {
        t = (avlnode *)malloc(sizeof(struct avlnode));
        if(t)
        {
            t->data = x;
            t->m_pleft    = null;
            t->m_pright = null;
            t->height = 0;
        }
        else
        {
            cout << "空间不够" << endl;
            exit(0);
        }
    }
    else if( x < t->data)        //如果插入到t结点的左子树上
    {
        t->m_pleft = avltreeinsert(t->m_pleft,x);    //先插入,后旋转
        if(height(t->m_pleft) - height(t->m_pright) == 2) //只有可能是这个
        {
            if(x < t->m_pleft->data)        //左左情况,只需要右旋转
            {
                t = singlerotatewithright( t );
            }
            else                            //左右情况,双旋转,先左
            {
                t = doublerotatewithleft( t );
            }
        }
    }
    else if( x > t->data )
    {
        t->m_pright = avltreeinsert(t->m_pright,x);
        if(height(t->m_pright) - height(t->m_pleft) == 2)
        {
            if(x > t->m_pright->data)        //右右情况,进行左旋
            {
                t = singlerotatewithleft( t );
            }
            else                            //左右情况,双旋转,先右
            {
                t = doublerotatewithright( t );
            }
        }
    }
    //如果这个数已经存在,那么不进行插入
    t->height = max(height(t->m_pleft),height(t->m_pright)) + 1;
    return t;
}
//递归实现中序遍历
void inordervisituserecur(const avltree pcurrent)
{
    if(pcurrent)
    {
        inordervisituserecur(pcurrent->m_pleft);
        cout << pcurrent->data << " ";
        if(pcurrent->m_pleft)
            cout << " leftchild: "<<pcurrent->m_pleft->data;
        else
            cout << " leftchild: "<<"null" ;
        if(pcurrent->m_pright)
            cout << " rightchild: "<<pcurrent->m_pright->data;
        else
            cout << " rightchild: "<< "null";
        cout << endl;
        inordervisituserecur(pcurrent->m_pright);
    }
}
int main()
{
    avltree root = null;
    root = avltreeinsert(root,1);
    root = avltreeinsert(root,2);
    root = avltreeinsert(root,3);
    root = avltreeinsert(root,4);
    root = avltreeinsert(root,5);
    root = avltreeinsert(root,6);
    root = avltreeinsert(root,7);
    root = avltreeinsert(root,8);
    root = avltreeinsert(root,9);
    root = avltreeinsert(root,10);
    root = avltreeinsert(root,11);
    root = avltreeinsert(root,12);
    root = avltreeinsert(root,13);
    root = avltreeinsert(root,14);
    root = avltreeinsert(root,15);
    inordervisituserecur(root);
    return 0;
}