首页 > 其它语言 > AVL树的定义和基本操作

AVL树的定义和基本操作

AVL树是带有平衡的二叉查找树!一颗AVL树的每一个结点的左子树和右子树的深度最多只有1的差距,这就保持了这颗二叉树的平衡!很大程度的提高了树的使用效率!

当我们对树进行一系列操作(插入、删除等)后,AVL树很可能就不能保持AVL的特性,所以在进行操作时,我们必须重新平衡这颗二叉树!

我们把必须重新平衡的结点叫做α(这样可以减少很多文字,又好理解),由于任意结点最多只有两个儿子,因此出现高度不平衡就需要α点的两个子结点高度差大于等于2。

如意看出,这种不平衡可能出现下面四种情况:

1、对α的左子树的左子树进行插入;

2、对α的左子树的右子树进行插入;

3、对α的右子树的右子树进行插入;

4、对α的右子树的左孩子进行插入。

 

1、3的情况是比较简单的,进行一次旋转就能完成平衡,而2、4的情况就比较复杂了,需要两次旋转!

 

我先定义一个AVL数的结点结构,只比查找树多一个属性:深度

 

[plain] 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. /*结点数据域类型定义*/
  5. typedef int ElemType;
  6. /*AVL树的结点声明*/
  7. typedef struct _AVLTNode
  8. {
  9.         ElemType data;
  10.         struct _AVLTNode * lchild;
  11.         struct _AVLTNode * rchild;
  12.         int height;     /*深度*/
  13. }AVLTNode,*AVLTree;

 

还需要一个辅助的函数,帮助获取这个深度

 

[plain]  
  1. /*获取树的高度*/
  2. static int Height(AVLTree T)
  3. {
  4.     if(!T)
  5.     {
  6.         return -1;
  7.     }
  8.     else
  9.     {
  10.         return T->height;
  11.     }
  12. }

 

 

这时候就对树进行插入操作,即创建二叉树,又可以插入!比较容易,就是几个函数的调用:

 

[plain]  
  1. /*AVL书中插入结点,插入完毕后树依然保持AVL特性*/
  2. AVLTree AVL_Insert(AVLTree * T, ElemType e)
  3. {
  4.     if (*T == NULL)         //如果空树,就构造一颗根结点
  5.     {
  6.         *T = (AVLTree)malloc(sizeof(AVLTNode));
  7.         if(!*T)
  8.         {
  9.             return NULL;
  10.         }
  11.         (*T)->data = e;
  12.         (*T)->lchild = NULL;
  13.         (*T)->rchild = NULL;
  14.         (*T)->height = 0;        //初始化深度为0;
  15.     }
  16.     else if(e < (*T)->data)           //左边
  17.     {
  18.         (*T)->lchild =AVL_Insert(&(*T)->lchild,e);            //递归左子树插入
  19.         if (Height((*T)->lchild) - Height((*T)->rchild) == 2)         //判断左子树和右子树的深度差为2 说明AVL特性被破坏,需要进行平衡
  20.         {
  21.             if (e < (*T)->lchild->data)                //属于 上面四种情况中的第一个,只需要一次旋转
  22.             {
  23.                 *T = SingleRotateLeft(*T);
  24.             }
  25.             else
  26.             {
  27.                 *T = DoubleRotateLeft(*T);      //第二个情况 双旋转
  28.             }
  29.         }
  30.     }
  31.     else if(e > (*T)->data)           //反之 右面,操作和左面相反而已
  32.     {
  33.         (*T)->rchild =AVL_Insert(&(*T)->rchild,e);
  34.         if (Height((*T)->rchild) - Height((*T)->lchild) == 2)
  35.         {
  36.             if (e > (*T)->rchild->data)
  37.             {
  38.                 *T = SingleRotateRight(*T);
  39.             }
  40.             else
  41.             {
  42.                 *T = DoubleRotateRight(*T);
  43.             }
  44.         }
  45.     }
  46.     (*T)->height = Max(Height((*T)->rchild),Height((*T)->lchild))+1;       //深度加1
  47.     return *T;
  48. }

然后我把四种情况的看书写出来:

 

 

[plain]  
  1. /*AVL树左单旋转*/
  2. static AVLTree SingleRotateLeft(AVLTree k1)
  3. {
  4.     AVLTree k2;
  5.     k2 = k1->lchild;
  6.     k1->lchild = k2->rchild;
  7.     k2->rchild = k1;
  8.     k1->height =  Max(Height(k1->rchild),Height(k1->lchild))+1;
  9.     k2->height =  Max(Height(k2->rchild),Height(k2->lchild))+1;
  10.     return k2;
  11. }
  12. /*AVL树右单旋转*/
  13. static AVLTree SingleRotateRight(AVLTree k1)
  14. {
  15.     AVLTree k2;
  16.     k2 = k1->rchild;
  17.     k1->rchild = k2->lchild;
  18.     k2->lchild = k1;
  19.     k1->height =  Max(Height(k1->rchild),Height(k1->lchild))+1;
  20.     k2->height =  Max(Height(k2->rchild),Height(k2->lchild))+1;
  21.     return k2;
  22. }
  23. /*AVL树左双旋转*/
  24. static AVLTree DoubleRotateLeft(AVLTree k1)
  25. {
  26.     k1 = SingleRotateRight(k1->lchild);
  27.     return SingleRotateLeft(k1);
  28. }
  29. /*AVL树右双旋转*/
  30. static AVLTree DoubleRotateRight(AVLTree k1)
  31. {
  32.     k1 = SingleRotateLeft(k1->rchild);
  33.     return SingleRotateRight(k1);
  34. }

其实就是几个指针之间的几个操作,比之前的链表的哪些操作简单多了,初学者最好的方法就是画图,根据图分析这四种情况,一目了然!

 

这里还需要了一个Max函数,我就不贴出来了,就是比较两个数,返回较大的数。写不出来去小学深造去吧!

 

我用前序遍历和中序遍历做一下测试,从1打到15,顺序输入,看看输出是什么情况:

 

[plain]  
  1. int main()
  2. {
  3.     AVLTree T = NULL;
  4.     int i=0;
  5.     for (i=1;i<16;i++)
  6.     {
  7.         AVL_Insert(&T,i);
  8.     }
  9.     PreOrderTraverse(T);
  10.     printf("\n\n");
  11.     InOrderTraverse(T);
  12.     getchar();
  13.     getchar();
  14.     return 0;
  15. }

结果如下:

 

第一排是前序遍历结果,第二排是中序遍历!!!!!刚好是一颗3层的满二叉树!

 

我再倒着15到1输入看看结果是不是一样:

 

[plain]

  1. int main()
  2. {
  3.     AVLTree T = NULL;
  4.     int i=0;
  5.     for (i=15;i>=1;i--)
  6.     {
  7.         AVL_Insert(&T,i);
  8.     }
  9.     PreOrderTraverse(T);
  10.     printf("\n\n");
  11.     InOrderTraverse(T);
  12.     getchar();
  13.     getchar();
  14.     return 0;
  15. }

结果一样:

 


本文固定链接: http://www.devba.com/index.php/archives/4402.html | 开发吧

报歉!评论已关闭.