Chinaunix首页 | 论坛 | 博客
  • 博客访问: 64168
  • 博文数量: 25
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 0
  • 用 户 组: 普通用户
  • 注册时间: 2014-12-19 10:42
文章分类

全部博文(25)

文章存档

2020年(1)

2018年(1)

2015年(21)

2014年(2)

我的朋友

分类: C/C++

2015-11-10 22:31:07

原文地址:数据结构之AVL树 作者:g_programming

数据结构之AVL

1 .基本概念

AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂,但要把它用代码实现出来还真的有点费脑筋。下面我们来看看:

1.1  AVL树是什么?

AVL树本质上还是一棵二叉搜索树(因此读者可以看到我后面的代码是继承自二叉搜索树的),它的特点是:

1. 本身首先是一棵二叉搜索树。 

2. 带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。 

例如:

     5              5

    /            / \

   2   6          2   6

  /          / \

 1   4   7      1   4

    /              /

   3              3

上图中,左边的是AVL树,而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1,而右边的树由于结点6没有子树,导致根结点5的平衡因子为2。

1.2  为什么要用AVL树?

有人也许要问:为什么要有AVL树呢?它有什么作用呢?

我们先来看看二叉搜索树吧(因为AVL树本质上是一棵二叉搜索树),假设有这么一种极端的情况:二叉搜索树的结点为1、2、3、4、5,也就是:

 1

  \

   2

    \

     3

      \

       4

        \

         5

聪明的你是不是发现什么了呢?呵呵,显而易见——这棵二叉搜索树其实等同于一个链表了,也就是说,它在查找上的优势已经全无了——在这种情况下,查找一个结点的时间复杂度是O(N)!

好,那么假如是AVL树(别忘了AVL树还是二叉搜索树),则会是:

   2

  / \

 1   4

    / \

   3   5

可以看出,AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)。也就是说,在大量的随机数据中AVL树的表现要好得多。

1.3  旋转

假设有一个结点的平衡因子为2(在AVL树中,最大就是2,因为结点是一个一个地插入到树中的,一旦出现不平衡的状态就会立即进行调整,因此平衡因子最大不可能超过2),那么就需要进行调整。由于任意一个结点最多只有两个儿子,所以当高度不平衡时,只可能是以下四种情况造成的:

1. 对该结点的左儿子的左子树进行了一次插入。 

2. 对该结点的左儿子的右子树进行了一次插入。 

3. 对该结点的右儿子的左子树进行了一次插入。 

4. 对该结点的右儿子的右子树进行了一次插入。 

情况1和4是关于该点的镜像对称,同样,情况2和3也是一对镜像对称。因此,理论上只有两种情况,当然了,从编程的角度来看还是四种情况。

第一种情况是插入发生在“外边”的情况(即左-左的情况或右-右的情况),该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况(即左-右的情况或右-左的情况),该情况要通过稍微复杂些的双旋转来处理。

1.31  旋转

情况1对该结点的左儿子的左子树进行了一次插入。

左边为调整前得节点,我们可以看出k2的左右子树已不再满足AVL平衡条件,调整后的为右图。

我们可以看出,解决办法是将x上移一层,并将z下移一层,由于在原树中k2 > k1,所以k2成为k1的右子树,而y是小于k2的,所以成为k2的左子树。

为了设计算法,我们这里来看一个更易理解的:插入的是节点“6

算法设计:由于是情形1对该结点的左儿子的左子树进行了一次插入,该节点是“8”,首先我们不考虑其父节点的情况,因为我们创建节点是递归创建的,可以不用考虑其父节点与其的连接,这在后面递归创建的时候会说到,由于“8”的右孩子将不会发生变化,但是其左孩子设为“7”的右孩子,将7的右孩子设为“8”及其子树,然后返回“7”节点的指针。

实现代码:

//情形

AVLTree SingleRotateWithLeft(PAVLNode k2)

{

 PAVLNode k1;

   k1 = k2->l;

     k2->l = k1->r;

     k1->r = k2;

     k2->h = MAX( Height( k2->l ), Height( k2->r ) ) + 1;

     k1->h = MAX( Height( k1->l ), k2->h ) + 1;

     return k1;  /* New root */

}

情况4:对该结点的右儿子的右子树进行了一次插入。 

左边为调整前得节点,我们可以看出k1的左右子树已不再满足AVL平衡条件,调整后的为右图。

我们可以看出,解决办法是将z上移一层,并将x下移一层,由于在原树中k2 > k1,所以k1成为k2的左子树,而y是大于k1的,所以成为k1的右子树。

为了设计算法,我们这里来看一个更易理解的:插入的是节点“6

算法设计:由于是情形1对该结点的右儿子的右子树进行了一次插入,该节点为“4”,我们同第一种情形类似。

实现代码:

//情形4

AVLTree SingleRotateWithRight(PAVLNode k1)

{

PAVLNode k2;

  k2 = k1->r;

    k1->r = k2->l;

    k2->l = k1;

    k1->h = MAX( Height( k1->l ), Height( k1->r ) ) + 1;

    k2->h = MAX( Height( k2->r ), k1->h ) + 1;

    return k2;  /* New root */

}

1.32  旋转

情况2:对该结点的左儿子的右子树进行了一次插入。 

这种情况是单旋转调整不回来的,如下图:

图(1

--右双旋转如下:

图(2

这里我们将图(1)的Y子树看成如图(2),以k2为子树根节点的树,我们将其子树分成比D,这里我我先对k3的左子树进行一次情形四的右旋转,然后在进行一次情形1的左旋转,详细步骤如下:(红色框里面的即是要进行单旋转的)

实现代码:

//情形2

AVLTree DoubleRotateWithLeft( PAVLNode k3 )

{

            /* Rotate between K1 and K2 */

            k3->l = SingleRotateWithRight( k3->l );

            /* Rotate between K3 and K2 */

            return SingleRotateWithLeft(k3);

}

情况3对该结点的右儿子的左子树进行了一次插入。

左双旋转如下:

我们先对k1的右子树进行一次左旋转(情形1,然后再对k1进行一次右旋转(情形4)。

实现代码:

//情形3

AVLTree DoubleRotateWithRight( PAVLNode k1 )

{

            /* Rotate between K3 and K2 */

            k1->r = SingleRotateWithLeft( k1->r );

            /* Rotate between K1 and K2 */

            return SingleRotateWithRight( k1 );

}

1.3  插入操作

插入的核心思路是通过递归找到合适的位置,插入新结点,然后看新结点是否平衡(平衡因子是否为2),如果不平衡的话,就分成种大情况以及两种小情况:

1. 在结点的左儿子(X < T->item) 

在左儿子的左子树 (X < T->l-> item),“外边”,要做单旋转。 

在左儿子的右子树 (X > T->l-> item),“内部”,要做双旋转。 

2. 在结点的右儿子(X > T->item) 

在右儿子的左子树(X < T->r-> item),“内部”,要做双旋转。 

在右儿子的右子树(X > T->r-> item),“外边”,要做单旋转。 

3. (X == T->item) ,对该节点的计数进行更新。

当进行了旋转之后,必定会有结点的“父结点”是需要更新的,例如:

   2

  / \

 1   4

    / \

   3   5

        \

         6

上图是调整前的,下图是调整后的:

     4

    / \

   2   5

  /   \

 1   3   6

可以看出,根结点2不平衡,是由于它的右儿子的右子树插入了新的结点6造成的。因此,这属于“外边”的情况,要进行一次单旋转。于是我们就把结点4调整上来作为根结点,再把结点2作为4的左儿子,最后把结点2的右儿子修改为原来的结点4的左儿子。

实现代码:

AVLTree Insert(Item X, AVLTree T )

 {

            if( T == NULL )

            {

                /* Create and return a one-node tree */

                T = (PAVLNode)malloc( sizeof(AVLNode ) );

                if( T == NULL )

                    perror("malloc failed");

                else

                {

                    T->item = X; 

T->h = 0;

                    T->l = T->r = NULL;

                    T->count = 1;

                }

            }

            else if(compare(&X,&T->item) == -1)//插入情况1

            {

                T->l = Insert( X, T->l );

                if( Height( T->l ) - Height( T->r ) == 2 )

                    if(compare(&X, &T->l->item ) == -1)//左边左子树 单旋转 

                        T = SingleRotateWithLeft( T );

                    else

                        T = DoubleRotateWithLeft( T );//左边右子树 

            }

            else if( compare(&X,&T->item) == 1 ) //插入情况2

            {

                T->r = Insert( X, T->r );

                if( Height( T->r ) - Height( T->l ) == 2 )

                    if(compare(&X , &T->r->item) == 1)//右边右子树 单旋转

                        T = SingleRotateWithRight( T );

                    else

                        T = DoubleRotateWithRight( T );//右边左子树 

            }

            else//插入情况3

             T->count++;

            /* Else X is in the tree already; we'll do nothing */

            T->h = MAX( Height( T->l ), Height( T->r ) ) + 1;

            return T;

}

阅读(1367) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~