`

AVL 平衡二叉树 转载

c 
阅读更多

转自http://blog.chinaunix.net/uid-24948645-id-3913917.html

平衡二叉树——AVL树的实现

分类: 数据结构  48人阅读 评论(0) 收藏 举报

AVL树是最先发明的自平衡二叉查找算法,是平衡二叉树的一种。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它又被成为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来平衡这棵树。

假设把AVL树构造过程中需要重新平衡的节点叫做α。由于任意节点最多有两个儿子,因此高度不平衡时,α点的两颗子树的高度差2。这种不平衡可能出现在下面这四种情况:

1)  对α的左儿子的左子树进行一次插入(左旋)

其中D是新插入的节点,红色节点K2是失去平衡的节点。需要对K1和K2进行左旋调整即将K1作为根,将K2作为K1的左子树,K1的右子树调整为K2的左子树。如下图所示

进行左旋变换   

代码如下:

  1. static Position SingleRotateWithLeft(Position K2)  
  2. {  
  3.     Position K1;  
  4.   
  5.     K1 = K2->Left;  
  6.     K2->Left = K1->Right;  
  7.     K1->Right = K2;  
  8.     //更新节点的高度  
  9.     return K1;  
  10. }  

2)对α的左儿子的右子树进行一次插入(左右双旋)

左右双旋这里的左右指的是对α的左儿子的右子树进行插入时需要旋转。先对K1和K2进行右旋(跟第四种情况类似),然后再对K3和K2进行左旋,最终实现平衡。如下图所示

进行一次右旋进行一次左旋

代码如下:

  1. static Position DoubleRotateWithLeft(Position K3)  
  2. {  
  3.     K3->Left = SingleRotateWithRight(K3->Left);  
  4.     return SingleRotateWithLeft(K3);  
  5. }  

3)对α的右儿子的左子树进行一次插入(右左双旋)

右左双旋:先对K1和K2进行左旋,然后在对K2和K3进行右旋,最终实现平衡。如下图所示

进行一次左旋进行一次右旋

代码如下:

  1. static Position DoubleRotateWithRight(Position K3)  
  2. {  
  3.     K3->Right = SingleRotateWithLeft(K3->Right);  
  4.     return SingleRotateWithRight(K3);  
  5. }  

4)对α的右儿子的右子树进行一次插入(右旋)

将K2的右子树更改为K1的左子树,K1的左子树更改为K2即完成的右旋,如下图所示

进行右旋

代码如下:

  1. static Position SingleRotateWithRight(Position K2)  
  2. {  
  3.     Position K1;  
  4.   
  5.     K1 = K2->Right;  
  6.     K2->Right = K1->Left;  
  7.     K1->Left = K2;  
  8.     //更新节点高度  
  9.     return K1;  
  10. }  
上面讲述了AVL树四种旋转情况,下面来实现一下AVL树。AVL树的实现跟上一章讲的二叉查找树相似,区别在于在插入和删除节点是需要对树进行调整以满足平衡条件。

avltree.h给出函数声明

  1. typedef int ElementType;  
  2.   
  3. #ifndef AVLTREE_H  
  4. #define AVLTREE_H  
  5.   
  6. struct TreeNode  
  7. {  
  8.     ElementType Element;  
  9.     int Height;  
  10.     struct TreeNode *Left;  
  11.     struct TreeNode *Right;  
  12. };  
  13.   
  14. typedef struct TreeNode *AvlTree;  
  15. typedef struct TreeNode *Position;  
  16.   
  17. AvlTree MakeEmpty(AvlTree T);  
  18. AvlTree Insert(ElementType X, AvlTree T);  
  19. Position Find(ElementType X ,AvlTree T);  
  20. Position FindMax(AvlTree T);  
  21. Position FindMin(AvlTree T);  
  22.   
  23. #endif  
avltree.c函数实现
  1. #include "fatal.h"  
  2. #include "avltree.h"  
  3.   
  4. AvlTree MakeEmpty(AvlTree T)  
  5. {  
  6.     if(T != NULL)  
  7.     {  
  8.         MakeEmpty(T->Left);  
  9.         MakeEmpty(T->Right);  
  10.         free(T);  
  11.     }  
  12.     return NULL;  
  13. }  
  14.   
  15. static int Height(Position P)  
  16. {  
  17.     if(P == NULL)  
  18.         return -1;  
  19.     else  
  20.         return P->Height;  
  21. }  
  22.   
  23. static int Max(int Lhs, int Rhs)  
  24. {  
  25.     return Lhs > Rhs ? Lhs : Rhs;  
  26. }  
  27.   
  28. static Position SingleRotateWithLeft(Position K2)  
  29. {  
  30.     Position K1;  
  31.   
  32.     K1 = K2->Left;  
  33.     K2->Left = K1->Right;  
  34.     K1->Right = K2;  
  35.   
  36.     K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;  
  37.     K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;  
  38.   
  39.     return K1;  
  40. }  
  41.   
  42. static Position SingleRotateWithRight(Position K2)  
  43. {  
  44.     Position K1;  
  45.   
  46.     K1 = K2->Right;  
  47.     K2->Right = K1->Left;  
  48.     K1->Left = K2;  
  49.   
  50.     K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;  
  51.     K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;  
  52.   
  53.     return K1;  
  54. }  
  55.   
  56. static Position DoubleRotateWithLeft(Position K3)  
  57. {  
  58.     K3->Left = SingleRotateWithRight(K3->Left);  
  59.     return SingleRotateWithLeft(K3);  
  60. }  
  61.   
  62. static Position DoubleRotateWithRight(Position K3)  
  63. {  
  64.     K3->Right = SingleRotateWithLeft(K3->Right);  
  65.     return SingleRotateWithRight(K3);  
  66. }  
  67.   
  68. AvlTree Insert(ElementType X, AvlTree T)  
  69. {  
  70.     if(T == NULL)  
  71.     {  
  72.         T = (Position)malloc(sizeof(struct TreeNode));  
  73.         if(T == NULL)  
  74.             FatalError("Out of space");  
  75.         T->Element = X;  
  76.         T->Height = 0;  
  77.         T->Left = T->Right = NULL;  
  78.     }  
  79.     else if(X < T->Element)//左子树插入新节点  
  80.     {  
  81.         T->Left = Insert(X, T->Left);  
  82.         if(Height(T->Left) - Height(T->Right) == 2)//左子树插入节点所以高度是左子树高于右子树  
  83.         {  
  84.             if(X < T->Left->Element)//对α的左儿子的左子树进行一次插入,需要左旋  
  85.                 T = SingleRotateWithLeft(T);  
  86.             else //对α的左儿子的右子树进行一次插入,需要双旋  
  87.                 T = DoubleRotateWithLeft(T);  
  88.         }  
  89.     }  
  90.     else if(X > T->Element)//右子树插入新节点  
  91.     {  
  92.         T->Right = Insert(X, T->Right);  
  93.         if(Height(T->Right) - Height(T->Left) == 2)//因为是右子树插入新节点,所以高度是右子树高于左子树  
  94.         {  
  95.             if(X > T->Right->Element)//对α的右儿子的右子树进行一次插入,需要右旋  
  96.                 T = SingleRotateWithRight(T);  
  97.             else//对α的右儿子的左子树进行一次插入,需要双旋  
  98.                 T = DoubleRotateWithRight(T);  
  99.         }  
  100.     }  
  101.     T->Height = Max(Height(T->Left), Height(T->Right)) + 1;  
  102.     return T;  
  103. }  
  104.   
  105. Position Find(ElementType X, AvlTree T)  
  106. {  
  107.     if(T == NULL)  
  108.         return NULL;  
  109.     if(X < T->Element)  
  110.         return Find(X, T->Left);  
  111.     else if(X > T->Element)  
  112.         return Find(X, T->Right);  
  113.     else  
  114.         return T;  
  115. }  
  116.   
  117. Position FindMin(AvlTree T)  
  118. {  
  119.     if(T == NULL)  
  120.         return NULL;  
  121.     else if(T->Left == NULL)  
  122.         return T;  
  123.     else  
  124.         return FindMin(T->Left);   
  125. }  
  126.   
  127. Position FindMax(AvlTree T)  
  128. {  
  129.     if(T == NULL)  
  130.         return NULL;  
  131.     else if(T->Right == NULL)  
  132.         return T;  
  133.     else  
  134.         return FindMax(T->Right);  
  135. }  

testavl.c测试AVL树的实现

  1. #include "avltree.h"  
  2. #include   
  3. #include   
  4.   
  5. void InOrder(AvlTree T)  
  6. {  
  7.     if(T != NULL)  
  8.     {  
  9.         InOrder(T->Left);  
  10.         printf("%d ", T->Element);  
  11.         InOrder(T->Right);  
  12.     }  
  13. }  
  14.   
  15. void PreOrder(AvlTree T)  
  16. {  
  17.     if(T != NULL)  
  18.     {  
  19.         printf("%d ", T->Element);  
  20.         PreOrder(T->Left);  
  21.         PreOrder(T->Right);  
  22.     }  
  23. }  
  24.   
  25. int main(void)  
  26. {  
  27.     AvlTree T;  
  28.     Position P;  
  29.     int i;  
  30.   
  31.     T = MakeEmpty(NULL);  
  32.     for(i = 1; i <= 7; i++)  
  33.         T = Insert(i, T);  
  34.     for(i = 16; i >= 10; i--)  
  35.         T = Insert(i, T);  
  36.     T = Insert(8, T);  
  37.     T = Insert(9, T);  
  38.     printf("Root: %d\n", T->Element);  
  39.     printf("InOrder:  ");  
  40.     InOrder(T);  
  41.     printf("\nPreOrder: ");  
  42.     PreOrder(T);  
  43.     putchar('\n');  
  44.     system("Pause");  
  45.   
  46.     return 0;  
  47. }  

测试:首先插入1到7,然后插入16到10,最后插入8和9。AVL树的应该为下图所示

测试结果如下图所示

分享到:
评论

相关推荐

    Avl平衡二叉树 linux32 SDK V2.0

    3 Avl二叉树SDK技术特点 支持以下功能: 1、 支持自定义键值比较函数 2、 支持删除节点回调函数 3、 支持插入节点 4、 支持根据键值进行精确查询节点 5、 支持根据键值进行精确删除节点 6、 支持从头到尾(从尾到头...

    Avl平衡二叉树 win32 SDK V1.0

    3 Avl二叉树SDK技术特点 支持以下功能: 1、 支持自定义键值比较函数 2、 支持删除节点回调函数 3、 支持插入节点 4、 支持根据键值进行精确查询节点 5、 支持根据键值进行精确删除节点 6、 支持从头到尾(从尾到头...

    C语言实现的AVL平衡二叉树

    用C语言实现了AVL平衡二叉树。主要包括创建新二叉树,插入节点,删除节点,平衡旋转,复制树结构,求并集(union),求交集(intersection),遍历和打印二叉树以及清理内存等。

    Java中AVL平衡二叉树实现Map_(仿照TreeMap和TreeSet)1

    Java中AVL平衡二叉树实现Map_(仿照TreeMap和TreeSet)1

    AVLtree_c_avl_平衡二叉树_avltree_

    将平衡二叉树的增删改查集成到了一起,提供友好的界面。

    AVL,平衡二叉树模板

    二叉树模板

    avl树(平衡二叉树)-c语言版

    自己用c语言实现的平衡二叉树,可以实现插入,删除,查找,效率很高,分享给大家.

    AVLTree 平衡二叉树c++实现

    c++平衡二叉树的实现 带内存分配,非常全面 ,有错误欢迎留言

    AVL搜索二叉树C语言源代码

    用C语言实现AVL搜索二叉树,并且实现了一些基本的操作,比如判断树是否为空、获得节点数、获得树的高度、查找、中序遍历、层序遍历、AVL搜索二叉树节点的插入、节点的删除等等。并且附上详细的注释

    平衡二叉树

    传统的二叉树是一种应用广泛的数据结构,适合于组织在内存中的较小索引...提出了多值结点平衡二叉树,它的主要特点是在每个MAVL树的结点都存储有多个关键字项,而其他信息仍与AVL树一样,即一个平衡因子和两个指针项。

    03平衡二叉树_AVLTree.rar_03平衡二叉树_AVLTree_大话数据结构_平衡二叉树

    查找算法,平衡二叉树,大话数据结构里面的。

    AVLTree自平衡二叉树C++模板类实现

    使用C++实现的AVLTree自平衡二叉树,支持动态插入与删除操作,供C++数据结构课程学习与交流使用。

    AVL tree 平衡二叉树

    AVL tree的数据结构例程,参考《数据结构与算法分析——C语言版》,书上代码整理成为一个可运行C程序文件

    算法实验4-平衡二叉树

    实现平衡二叉树(AVL树)基本操作(初始化、删除、插入)

    平衡二叉树-AVL树的实现

    首先实现BST二叉搜索树,在BST的基础上做出AVL树,有插入、删除、查询、调整平衡的功能,而且可以和BST比较的过程。By Michael Zhou

    平衡二叉树 AVL的应用事例

    AVL管理数据 struct branch{ unsigned int data; /* actual data */ struct branch * l_chld, * r_chld; /* left & right child */ short bc; /* balance coefficient */ }; #define avl_entry (T, P, M) (T *)...

    平衡二叉树c++实现

    平衡二叉树,AVL算法,c++实现..................

    平衡二叉树(纯C++实现)

    包含AVL树的创建,删除,查找等等功能,我使用的是VS2010的编译器,可能用版本低的编译器无法打开

    平衡二叉树(AVL树)浅析

    关于平衡二叉树的学习笔记,并提供二叉树平衡、插入及删除的代码、提供一个简单的打印二叉树结构的函数(打印对齐不是很好),方便代码调试。

    c语言平衡二叉树代码示例

    平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),它具有以下性质: 1. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。 2. 左右两个子树都是一棵平衡二叉树。 平衡二叉树大部分操作和...

Global site tag (gtag.js) - Google Analytics