devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡二叉树结点的插入和调整_平衡二叉树结点数的递推公式

作者：盐析白兔 | 2024-06-28 15:07:32

赞

踩

平衡二叉树结点数的递推公式

首先要说明为什么要引进平衡二叉树

【例】搜索树结点按照不同的插入次序，将导致不同的深度和平均查找长度（ASL），例如下图


第二种比较“均匀”，最平衡的方式是左右结点树相同，但是这个条件比较苛刻，可是适当放宽这个条件，因此引进了平衡二叉树

“平衡因子”（Balance Factor，简称BF）：BF(T)=hL-hR，其中hL和hR分别为T的左、右子树的高度

平衡二叉树（Balanced Binary Tree）（AVL树）是空树，或者

对于任一结点左、右子树高度差的绝对值不超过1，即|BF(T)|<=1

如果一棵高度为h的二叉平衡树最少的结点数是n，那么满足递推公式nh=nh-1+nh-2+1，与斐波那契数列有如下对应关系


数学上可以证明，给定结点数为n的AVL树的最大高度为O(log2n)!

下面介绍二叉树的调整

1. 插入操作

       在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是： 旋转 。 下面我们归纳一下平衡旋转的4中情况

1) 绕某元素左旋转  

                                 80                                    90  

                                 /  \             左旋               /    \

                               60 90          ---- ->         80     120

                                    /  \                               /  \       /

                                  85 120                    60  85 100

                                        /

                                      100     

                               a)  BST树                              b ) AVL树

     分析一下：在插入数据100之前，a图的B ST树只有80节点的平衡因子是-1(左高-右高)，但整棵树还是平衡的。加入100之后，80节点的平衡因子就成为了-2，此时平衡被破坏。需要左旋转成b 图。

     当树中节点X的右孩子的右孩子上插入新元素，且平衡因子从-1变成-2后，就需要绕节点X进行左旋转。


 

2) 绕某元素右旋转  

                                100                                   85

                                 /  \               右旋              /    \

                              85  120         ------ ->     60    100  

                              /  \                                      \      /   \

                            60 90                                 80  90 120

                              \

                              80

                             a) B ST树                                b) AVL树

     当树中节点X的左孩子的左孩子上插入新元素，且平衡因子从1变成2后，就需要绕节点X进行右旋转。

 

3) 绕某元素的左子节点左旋转，接着再绕该元素自己右旋转。 此情况下就是左旋与右旋 的结合，具体操作时可以分 解成这两种操作，只是围绕点不一样而已。

                                                      

                            100                             100                                90

                             /  \             左旋            /  \              右旋           /    \

                          80  120       ------>      90  120        ------>     80   100  

                          / \                                  /                                    /  \      \

                       60 90                            80                              60  85  120

                            /                               / \

                          85                            60 85 

      当树中节点X的左孩子的右孩子上插入新元素，且 平衡因子从1变成2后，就需要 先绕X的左子节点Y左旋转，接着再绕X右旋转



4) 绕某元素的右子节点右旋转，接着再绕该元素自己左旋转。 此情况下就是 右旋与左旋 的结合，具体操作时可以分解 成这两种操作，只是围绕点不一样而已 。

 

                               80                               80                                       85  

                               /   \             右 旋          /  \                 左 旋             /  \     

                            60  100      ------>      60 85            ------->          80 100

                                   /  \                                 \                                   /     /   \       

                                85  120                        100                           60    90 120

                                   \                                   /  \

                                   90                           90  120

       当树中节点X的右孩子的左孩子上插入新元素，且 平衡因子从-1变成-2后，就需要 先绕X的右子节点Y右旋转，接着再绕X左旋转



以上一段文字引自 http://hxraid.iteye.com/blog/609949 

  1. #include "stdio.h"    
  2. #include "stdlib.h"
  3.  
  4. typedef int ElementType;
  5. typedef struct AVLNode *Position;
  6. typedef Position AVLTree; /* AVL树类型 */
  7. struct AVLNode{
  8.     ElementType Data; /* 结点数据 */
  9.     AVLTree Left;     /* 指向左子树 */
  10.     AVLTree Right;    /* 指向右子树 */
  11.     int Height;       /* 树高 */
  12. };
  13.  
  14. int Max ( int a, int b )
  15. {
  16.     return a > b ? a : b;
  17. }
  18.  
  19. //树的建立    
  20. AVLTree createTree();  
  21. //先序遍历      
  22. void preOrder(AVLTree t);  
  23. //中序遍历      
  24. void intOrder(AVLTree t);  
  25. //后序遍历     
  26. void postOrder(AVLTree t);    
  27. //二叉树的遍历  
  28. void Print(AVLTree t);  
  29.  
  30.  
  31. //求出树的高度
  32. int GetHeight(AVLTree A){  
  33.      int HL,HR,MaxH;  
  34.      if(A){  
  35. 		 HL= GetHeight(A->Left);  
  36. 		 HR= GetHeight(A->Right);  
  37.          MaxH=(HL>HR)?HL:HR;  
  38.          return (MaxH+1);  
  39.      }  
  40.      else return 0;  
  41.  }; 
  42.  
  43. //左单旋(LL旋转)
  44. AVLTree SingleLeftRotation ( AVLTree A )
  45. { /* 注意：A必须有一个左子结点B */
  46.   /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */     
  47.  
  48.     AVLTree B = A->Left;
  49.     A->Left = B->Right;
  50.     B->Right = A;
  51.     A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
  52.     B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
  53.   
  54.     return B;
  55. }
  56.  
  57. //右单旋
  58. AVLTree SingleRightRotation ( AVLTree A )
  59. { /* 注意：A必须有一个右子结点B */
  60.   /* 将A与B做右单旋，更新A与B的高度，返回新的根结点B */     
  61.  
  62.     AVLTree B = A->Right;
  63.     A->Right = B->Left;
  64.     B->Left = A;
  65.     A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
  66.     B->Height = Max( GetHeight(B->Right), A->Height ) + 1;
  67.   
  68.     return B;
  69. }
  70.  
  71. AVLTree DoubleLeftRightRotation ( AVLTree A )
  72. { /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
  73.   /* 将A、B与C做两次单旋，返回新的根结点C */
  74.      
  75.     /* 将B与C做右单旋，C被返回 */
  76.     A->Left = SingleRightRotation(A->Left);
  77.     /* 将A与C做左单旋，C被返回 */
  78.     return SingleLeftRotation(A);
  79. }
  80.  
  81. AVLTree DoubleRightLeftRotation ( AVLTree A )
  82. { /* 注意：A必须有一个右子结点B，且B必须有一个左子结点C */
  83.   /* 将A、B与C做两次单旋，返回新的根结点C */
  84.      
  85.     /* 将B与C做左单旋，C被返回 */
  86.     A->Right = SingleLeftRotation(A->Right);
  87.     /* 将A与C做右单旋，C被返回 */
  88.     return SingleRightRotation(A);
  89. }
  90.  
  91. AVLTree Insert( AVLTree &T, ElementType X )
  92. { /* 将X插入AVL树T中，并且返回调整后的AVL树 */
  93.     if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
  94. 		AVLTree TT;
  95.         TT = (AVLTree)malloc(sizeof(struct AVLNode));
  96.         TT->Data = X;
  97.         TT->Height = 0;
  98.         TT->Left = TT->Right = NULL;
  99. 		T=TT;
  100.     } /* if (插入空树) 结束 */
  101.  
  102.     else if ( X < T->Data ) {
  103.         /* 插入T的左子树 */
  104.         T->Left = Insert( T->Left, X);
  105.         /* 如果需要左旋 */
  106.         if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
  107.             if ( X < T->Left->Data ) 
  108.                T = SingleLeftRotation(T);      /* 左单旋 */
  109.             else 
  110.                T = DoubleLeftRightRotation(T); /* 左-右双旋 */
  111.     } /* else if (插入左子树) 结束 */
  112.      
  113.     else if ( X > T->Data ) {
  114.         /* 插入T的右子树 */
  115.         T->Right = Insert( T->Right, X );
  116.         /* 如果需要右旋 */
  117.         if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
  118.             if ( X > T->Right->Data ) 
  119.                T = SingleRightRotation(T);     /* 右单旋 */
  120.             else 
  121.                T = DoubleRightLeftRotation(T); /* 右-左双旋 */
  122.     } /* else if (插入右子树) 结束 */
  123.  
  124.     /* else X == T->Data，无须插入 */
  125.  
  126.     /* 别忘了更新树高 */
  127.     T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
  128.      
  129.     return T;
  130. }
  131.  
  132. int main()
  133. {
  134. 	AVLTree t= NULL;
  135. 	Insert(t,30);
  136. 	Insert(t,33);  
  137.         Insert(t,50);  
  138.         Insert(t,35);  
  139.         Insert(t,40);  
  140.         Insert(t,52);  
  141.  
  142. 	Print(t);
  143. 	system("pause");  
  144. }
  145.  
  146.  
  147. AVLTree createTree()   //树的建立    
  148.  {      
  149.      ElementType ch;  
  150.      AVLTree t;  
  151.        
  152.      scanf("%d",&ch);//输入二叉树数据  
  153.      if(ch==-1)  //判断二叉树是否为空    
  154.          t=NULL;  
  155.      else     
  156.      {    
  157.          t=(struct AVLNode *)malloc(sizeof(struct AVLNode));  //二叉树的生成    
  158.          t->Data=ch;      
  159.          t->Left=createTree();      
  160.          t->Right=createTree();      
  161.      }
  162. 	  t->Height = Max( GetHeight(t->Left), GetHeight(t->Right) ) + 1;
  163.      return t;      
  164.  }      
  165.  
  166.  
  167.  void preOrder(AVLTree t)  //先序遍历     
  168.  {      
  169.      if(t)      
  170.      {        
  171.          printf("%d ",t->Data);      
  172.          preOrder(t->Left);      
  173.          preOrder(t->Right);      
  174.      }      
  175.  };  
  176.      
  177.  void intOrder(AVLTree t)  //中序遍历      
  178. {      
  179.     if(t)      
  180.      {      
  181.         intOrder(t->Left);      
  182.         printf("%d ",t->Data);      
  183.         intOrder(t->Right);      
  184.      }      
  185.  };  
  186.   
  187.  void postOrder(AVLTree t)  //后序遍历      
  188.  {      
  189.      if(t)      
  190.      {         
  191.          postOrder(t->Left);      
  192.          postOrder(t->Right);     
  193.          printf("%d ",t->Data);      
  194.      }      
  195.  };  
  196.   
  197.  //二叉树的遍历  
  198.  void Print(AVLTree t){  
  199.    printf("前序遍历：");    
  200.    preOrder(t) ;    
  201.    printf("\n");    
  202.    printf("中序遍历：");    
  203.    intOrder(t);    
  204.    printf("\n");    
  205.    printf("后序遍历：");      
  206.    postOrder(t);      
  207.    printf("\n");  
  208.    printf("\n");  
  209.  };

举个例子哈，如果依次插入30,33,50,35,40,52

那么在插入50的时候有一次RR旋转，插入40的时候有一次LR旋转，插入52的时候又有一次RR插入

结果如下


后面还有平衡二叉树的删除和红黑树，待我日后写哈哈哈

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/766356
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号