当前位置:   article > 正文

数据结构(特殊二叉树-平衡二叉树)

数据结构(特殊二叉树-平衡二叉树)

平衡二叉树(AVL树)

  • 前提一定是搜索二叉树,对于根节点的左右子树的高度差不能超过1,并且所有子树都要循序这个要求

  • 如果一个搜索二叉树呈现或接近单支状,它的查找效率很低,很接近链表,因此如果能让它平衡时,查找效率最高

  • 由于节点的位置要受到相互之间值的影响,并且在往平衡二叉树中添加节点或者删除节点前,二叉树本身是平衡的,所以只可能在最后操作的节点附近不满足平衡条件,因此需要在该过程中对该节点进行判断并调整。

  • 因此一棵平衡二叉树因为添加操作导致不平衡的原因,总结就四种:

第一种:
            x                               y
          /   \                          /     \    
         y    t1                        z       x
       /   \                          /   \   /   \
      z    t2                        t3  t4   t2  t1
     / \
    t3 t4              以y为轴 右旋转
    
第二种:
           x                             y
         /   \                         /   \
        t1    y                       x     z
            /   \                    / \   / \
           t2    z                  t1 t2 t3 t4
                / \
               t3  t4  以y为轴 左旋转
              
              
第三种:
            x               x                z
          /   \            / \             /   \
         y    t1          z  t1           y     x 
       /   \             / \            /  \   /  \
      t2    z           y  t4          t2  t3 t4  t1   
           / \         / \ 
          t3 t4       t2 t3    
          先以z为轴左旋转          再以z为轴右旋转 达到平衡
          
第四种:
            x               x                z
          /   \            / \             /   \
         t1    y          t1  z           x     y 
             /   \           / \         /  \  /  \
            z    t2         t3  y       t1  t3 t4 t2   
           / \                 / \ 
          t3 t4               t4 t2    
          先以z为轴右旋转          再以z为轴左旋转 达到平衡
删除节点
  • 待删除的节点是叶子节点,直接删除

  • 待删除节点的左子树或者右子树为空,则使用非空节点替换

  • 待删除节点左右子树非空,则根据左右子树的高度,选择高的一边子树,如果是左子树高,选择左子树中的最大节点赋值给待删除节点,然后再左子树中继续删除该最大节点,相当于继续处理情况1或情况2;如果是右子树高,则在右子树选择最小值节点继续同样处理。

  • 删除后可能导致不平衡,需要重新调整平衡

平衡二叉树的优点:

避免了二叉搜索树呈现单支状,让其能以最佳的效率进行查找操作 O(log2n)

平衡二叉树的缺点:

在插入、删除操作时,为了达到平衡需要进行大量的左旋、右旋操作、计算高度,所以此时操作速度慢

因此AVL树适合在数据量大并且数据量比较稳定,没有太多的插入、删除操作,适合大量的查找操作。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. // 设计二叉树节点结构
  5. typedef struct TreeNode
  6. {
  7. int data;
  8. struct TreeNode* left;
  9. struct TreeNode* right;
  10. }TreeNode;
  11. // 创建节点
  12. TreeNode* create_tree_node(int data)
  13. {
  14. TreeNode* node = malloc(sizeof(TreeNode));
  15. node->data = data;
  16. node->left = NULL;
  17. node->right = NULL;
  18. return node;
  19. }
  20. // 求高度
  21. int high_tree(TreeNode* root)
  22. {
  23. if(NULL == root) return 0;
  24. int lh = high_tree(root->left);
  25. int rh = high_tree(root->right);
  26. return lh>rh ? lh+1 : rh+1;
  27. }
  28. // 计算左右子树高度差
  29. int def_high(TreeNode* root)
  30. {
  31. if(NULL == root) return 0;
  32. return high_tree(root->left) - high_tree(root->right);
  33. }
  34. // 左旋转
  35. TreeNode* left_rotate(TreeNode* x)
  36. {
  37. TreeNode* y = x->right;
  38. TreeNode* t2 = y->left;
  39. y->left = x;
  40. x->right = t2;
  41. return y;
  42. }
  43. // 右旋转
  44. TreeNode* right_rotate(TreeNode* x)
  45. {
  46. TreeNode* y = x->left;
  47. TreeNode* t2 = y->right;
  48. y->right = x;
  49. x->left = t2;
  50. return y;
  51. }
  52. // 自动调整平衡 并返回调整后的根节点
  53. TreeNode* auto_balance(TreeNode* x)
  54. {
  55. if(NULL == x) return NULL;
  56. int lh = high_tree(x->left);
  57. int rh = high_tree(x->right);
  58. // 左子树高于右子树 超过1
  59. if(lh - rh > 1)
  60. {
  61. // 情况1
  62. if(def_high(x->left) >= 0)
  63. {
  64. // 右旋转
  65. x = right_rotate(x);
  66. }
  67. // 情况3
  68. else
  69. {
  70. // 左旋转
  71. x->left = left_rotate(x->left);
  72. // 右旋转
  73. x = right_rotate(x);
  74. }
  75. }
  76. // 或者 右高于左 超过1
  77. else if(rh - lh > 1)
  78. {
  79. // 情况2
  80. if(def_high(x->right) <= 0)
  81. {
  82. // 左旋转
  83. x = left_rotate(x);
  84. }
  85. // 情况4
  86. else
  87. {
  88. // 右旋转
  89. x->right = right_rotate(x->right);
  90. // 左旋转
  91. x = left_rotate(x);
  92. }
  93. }
  94. return x;
  95. }
  96. // 添加 返回添加成功后的根节点
  97. TreeNode* insert_tree(TreeNode* root,int data)
  98. {
  99. if(NULL == root)
  100. return create_tree_node(data);
  101. // 节点添加到合适的位置中
  102. if(data < root->data)
  103. root->left = insert_tree(root->left,data);
  104. else
  105. root->right = insert_tree(root->right,data);
  106. // 有可能添加后该位置破坏平衡 需要调整
  107. root = auto_balance(root);
  108. return root;
  109. }
  110. // 找最大值
  111. TreeNode* max_tree_node(TreeNode* root)
  112. {
  113. if(NULL == root) return NULL;
  114. TreeNode* max = root;
  115. while(max->right) max = max->right;
  116. return max;
  117. }
  118. // 找最小值
  119. TreeNode* min_tree_node(TreeNode* root)
  120. {
  121. if(NULL == root) return NULL;
  122. TreeNode* min = root;
  123. while(min->left) min = min->left;
  124. return min;
  125. }
  126. TreeNode* delete_tree(TreeNode* root,int data)
  127. {
  128. if(NULL == root) return NULL;
  129. if(root->data == data)
  130. {
  131. // 左右皆空 直接删
  132. if(NULL == root->left && NULL == root->right)
  133. {
  134. free(root);
  135. return NULL;
  136. }
  137. // 左空 替换为右子树
  138. if(NULL == root->left)
  139. {
  140. TreeNode* temp = root->right;
  141. free(root);
  142. return temp;
  143. }
  144. // 右空 替换为左子树
  145. if(NULL == root->right)
  146. {
  147. TreeNode* temp = root->left;
  148. free(root);
  149. return temp;
  150. }
  151. // 左右都非空
  152. // 左边高
  153. if(def_high(root) >= 0)
  154. {
  155. TreeNode* max = max_tree_node(root->left);
  156. root->data = max->data;
  157. root->left = delete_tree(root->left,max->data);
  158. }
  159. // 右边高
  160. else
  161. {
  162. TreeNode* min = min_tree_node(root->right);
  163. root->data = min->data;
  164. root->right = delete_tree(root->right,min->data);
  165. }
  166. // 重新调整平衡
  167. root = auto_balance(root);
  168. return root;
  169. }
  170. if(data < root->data)
  171. root->left = delete_tree(root->left,data);
  172. else
  173. root->right = delete_tree(root->right,data);
  174. // 重新调整平衡
  175. root = auto_balance(root);
  176. return root;
  177. }
  178. // 遍历
  179. void dlr_show(TreeNode* root)
  180. {
  181. if(NULL == root) return;
  182. printf("%d ",root->data);
  183. dlr_show(root->left);
  184. dlr_show(root->right);
  185. }
  186. void ldr_show(TreeNode* root)
  187. {
  188. if(NULL == root) return;
  189. ldr_show(root->left);
  190. printf("%d ",root->data);
  191. ldr_show(root->right);
  192. }
  193. void lrd_show(TreeNode* root)
  194. {
  195. if(NULL == root) return;
  196. lrd_show(root->left);
  197. lrd_show(root->right);
  198. printf("%d ",root->data);
  199. }
  200. int main(int argc,const char* argv[])
  201. {
  202. TreeNode* root = NULL;
  203. for(int i=0; i<10; i++)
  204. {
  205. root = insert_tree(root,i+1);
  206. }
  207. root = insert_tree(root,20);
  208. root = delete_tree(root,4);
  209. dlr_show(root);
  210. printf("\n");
  211. ldr_show(root);
  212. printf("\n");
  213. lrd_show(root);
  214. printf("\n");
  215. }

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/875337
推荐阅读
相关标签
  

闽ICP备14008679号