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

AVL树的定义和基本操作

孤风一剑 1月 16, 2014 327 0

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>
  5. /*结点数据域类型定义*/
  6. typedef int ElemType;
  8. /*AVL树的结点声明*/
  9. typedef struct _AVLTNode
  10. {
  11.         ElemType data;
  12.         struct _AVLTNode * lchild;
  13.         struct _AVLTNode * rchild;
  14.         int height;     /*深度*/
  15. }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.         }
  12.         (*T)->data = e;
  13.         (*T)->lchild = NULL;
  14.         (*T)->rchild = NULL;
  15.         (*T)->height = 0;        //初始化深度为0；
  16.     }
  17.     else if(e < (*T)->data)           //左边
  18.     {
  19.         (*T)->lchild =AVL_Insert(&(*T)->lchild,e);            //递归左子树插入
  21.         if (Height((*T)->lchild) – Height((*T)->rchild) == 2)         //判断左子树和右子树的深度差为2 说明AVL特性被破坏，需要进行平衡
  22.         {
  23.             if (e < (*T)->lchild->data)                //属于 上面四种情况中的第一个，只需要一次旋转
  24.             {
  25.                 *T = SingleRotateLeft(*T);
  26.             }
  27.             else
  28.             {
  29.                 *T = DoubleRotateLeft(*T);      //第二个情况 双旋转
  30.             }
  31.         }
  32.     }
  33.     else if(e > (*T)->data)           //反之 右面，操作和左面相反而已
  34.     {
  35.         (*T)->rchild =AVL_Insert(&(*T)->rchild,e);
  36.         if (Height((*T)->rchild) – Height((*T)->lchild) == 2)
  37.         {
  38.             if (e > (*T)->rchild->data)
  39.             {
  40.                 *T = SingleRotateRight(*T);
  41.             }
  42.             else
  43.             {
  44.                 *T = DoubleRotateRight(*T);
  45.             }
  46.         }
  47.     }
  49.     (*T)->height = Max(Height((*T)->rchild),Height((*T)->lchild))+1;       //深度加1
  50.     return *T;
  51. }

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

 

 

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

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

 

这里还需要了一个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.     }
  10.     PreOrderTraverse(T);
  11.     printf(“\n\n”);
  12.     InOrderTraverse(T);
  13.     getchar();
  14.     getchar();
  15.     return 0;
  16. }

结果如下：

 

第一排是前序遍历结果，第二排是中序遍历！！！！！刚好是一颗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.     }
  10.     PreOrderTraverse(T);
  11.     printf(“\n\n”);
  12.     InOrderTraverse(T);
  13.     getchar();
  14.     getchar();
  15.     return 0;
  16. }

结果一样：

 

标签

相关推荐

标签

.NET (32) ActiveMQ (34) AJAX (29) android (463) android开发 (34) ASP.NET (58) C# (153) CSS (21) eclipse (50) Hadoop (23) Hibernate (51) HTML (30) html5 (29) IOS (48) JAVA (378) JavaScript (87) JQuery (85) js (53) json (26) jsp (28) Linux (70) ListView (28) mvc (28) myeclipse (25) MySQL (151) oracle (181) PHP (158) spring (84) SQL (62) SQL Server (28) string (20) Struts2 (39) Tomcat (39) Ubuntu (20) WEB (28) webservice (29) Windows (27) XML (36) 多线程 (21) 存储过程 (22) 实例 (24) 数据库 (89) 服务器 (31) 算法 (34) 设计模式 (23)

文章归档