`
chinamming
  • 浏览: 140686 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

平衡树（AVL）详解

 
阅读更多

1. 为什么平衡树？

在二叉搜索树（BST，Binary Search Tree）中提到，BST树可能会退化成一个链表（整棵树中只有左子树，或者只有右子树），这将大大影响二叉树的性能。

前苏联科学家G.M. Adelson-Velskii 和 E.M. Landis给出了答案。他们在1962年发表的一篇名为《An algorithm for the organization of information》的文章中提出了一种自平衡二叉查找树（self-balancing binary search tree）。这种二叉查找树在插入和删除操作中，可以通过一系列的旋转操作来保持平衡，从而保证了二叉查找树的查找效率。最终这种二叉查找树以他们的名字命名为“AVL-Tree”，它也被称为平衡二叉树（Balanced Binary Tree）。

2. 原理

在节点上设置一个平衡因子BF，代表左右子树的高度差，BF = { -1, 0, 1}。

3. 旋转

AVL的Insert/Delete操作可能会引起树的失衡，可以通过选择解决这个问题。

3.1 4种旋转

（1）LL

（2）RR

（3）LR

（4）RL

在下面的文章中有一个关于AVL选择的动画，大家不妨看看。

C#与数据结构--树论--平衡二叉树(AVL Tree)

3.2 旋转实现

在算法导论中给出旋转的伪代码：

[cpp] view plaincopyprint?
  1. LEFT-ROTATE(T,x)
  2. 1y←right[x]▹Sety.
  3. 2right[x]←left[y]▹Turny'sleftsubtreeintox'srightsubtree.
  4. 3p[left[y]]←x
  5. 4p[y]←p[x]▹Linkx'sparenttoy.
  6. 5ifp[x]=nil[T]
  7. 6thenroot[T]←y
  8. 7elseifx=left[p[x]]
  9. 8thenleft[p[x]]←y
  10. 9elseright[p[x]]←y
  11. 10left[y]←x▹Putxony'sleft.
  12. 11p[x]←y


[csharp] view plaincopyprint?
  1. //旋转以root为根的子树，当高度改变，则返回true；高度未变则返回false
  2. privateboolRotateSubTree(intbf)
  3. {
  4. booltallChange=true;
  5. Noderoot=path[p],newRoot=null;
  6. if(bf==2)//当平衡因子为2时需要进行旋转操作
  7. {
  8. intleftBF=root.Left.BF;
  9. if(leftBF==-1)//LR型旋转
  10. {
  11. newRoot=LR(root);
  12. }
  13. elseif(leftBF==1)
  14. {
  15. newRoot=LL(root);//LL型旋转
  16. }
  17. else//当旋转根左孩子的bf为0时，只有删除时才会出现
  18. {
  19. newRoot=LL(root);
  20. tallChange=false;
  21. }
  22. }
  23. if(bf==-2)//当平衡因子为-2时需要进行旋转操作
  24. {
  25. intrightBF=root.Right.BF;//获取旋转根右孩子的平衡因子
  26. if(rightBF==1)
  27. {
  28. newRoot=RL(root);//RL型旋转
  29. }
  30. elseif(rightBF==-1)
  31. {
  32. newRoot=RR(root);//RR型旋转
  33. }
  34. else//当旋转根左孩子的bf为0时，只有删除时才会出现
  35. {
  36. newRoot=RR(root);
  37. tallChange=false;
  38. }
  39. }
  40. //更改新的子树根
  41. if(p>0)
  42. {
  43. if(root.Data<path[p-1].Data)
  44. {
  45. path[p-1].Left=newRoot;
  46. }
  47. else
  48. {
  49. path[p-1].Right=newRoot;
  50. }
  51. }
  52. else
  53. {
  54. _head=newRoot;//如果旋转根为AVL树的根，则指定新AVL树根结点
  55. }
  56. returntallChange;
  57. }
  58. //root为旋转根，rootPrev为旋转根双亲结点
  59. privateNodeLL(Noderoot)//LL型旋转，返回旋转后的新子树根
  60. {
  61. NoderootNext=root.Left;
  62. root.Left=rootNext.Right;
  63. rootNext.Right=root;
  64. if(rootNext.BF==1)
  65. {
  66. root.BF=0;
  67. rootNext.BF=0;
  68. }
  69. else//rootNext.BF==0的情况，删除时用
  70. {
  71. root.BF=1;
  72. rootNext.BF=-1;
  73. }
  74. returnrootNext;//rootNext为新子树的根
  75. }
  76. privateNodeLR(Noderoot)//LR型旋转，返回旋转后的新子树根
  77. {
  78. NoderootNext=root.Left;
  79. NodenewRoot=rootNext.Right;
  80. root.Left=newRoot.Right;
  81. rootNext.Right=newRoot.Left;
  82. newRoot.Left=rootNext;
  83. newRoot.Right=root;
  84. switch(newRoot.BF)//改变平衡因子
  85. {
  86. case0:
  87. root.BF=0;
  88. rootNext.BF=0;
  89. break;
  90. case1:
  91. root.BF=-1;
  92. rootNext.BF=0;
  93. break;
  94. case-1:
  95. root.BF=0;
  96. rootNext.BF=1;
  97. break;
  98. }
  99. newRoot.BF=0;
  100. returnnewRoot;//newRoot为新子树的根
  101. }
  102. privateNodeRR(Noderoot)//RR型旋转，返回旋转后的新子树根
  103. {
  104. NoderootNext=root.Right;
  105. root.Right=rootNext.Left;
  106. rootNext.Left=root;
  107. if(rootNext.BF==-1)
  108. {
  109. root.BF=0;
  110. rootNext.BF=0;
  111. }
  112. else//rootNext.BF==0的情况，删除时用
  113. {
  114. root.BF=-1;
  115. rootNext.BF=1;
  116. }
  117. returnrootNext;//rootNext为新子树的根
  118. }
  119. privateNodeRL(Noderoot)//RL型旋转，返回旋转后的新子树根
  120. {
  121. NoderootNext=root.Right;
  122. NodenewRoot=rootNext.Left;
  123. root.Right=newRoot.Left;
  124. rootNext.Left=newRoot.Right;
  125. newRoot.Right=rootNext;
  126. newRoot.Left=root;
  127. switch(newRoot.BF)//改变平衡因子
  128. {
  129. case0:
  130. root.BF=0;
  131. rootNext.BF=0;
  132. break;
  133. case1:
  134. root.BF=0;
  135. rootNext.BF=-1;
  136. break;
  137. case-1:
  138. root.BF=1;
  139. rootNext.BF=0;
  140. break;
  141. }
  142. newRoot.BF=0;
  143. returnnewRoot;//newRoot为新子树的根
  144. }

4. 插入与删除

4.1 插入

[cpp] view plaincopyprint?
  1. publicboolAdd(intvalue)//添加一个元素
  2. {//如果是空树，则新结点成为二叉排序树的根
  3. if(_head==null)
  4. {
  5. _head=newNode(value);
  6. _head.BF=0;
  7. returntrue;
  8. }
  9. p=0;
  10. //prev为上一次访问的结点，current为当前访问结点
  11. Nodeprev=null,current=_head;
  12. while(current!=null)
  13. {
  14. path[p++]=current;//将路径上的结点插入数组
  15. //如果插入值已存在，则插入失败
  16. if(current.Data==value)
  17. {
  18. returnfalse;
  19. }
  20. prev=current;
  21. //当插入值小于当前结点，则继续访问左子树，否则访问右子树
  22. current=(value<prev.Data)?prev.Left:prev.Right;
  23. }
  24. current=newNode(value);//创建新结点
  25. current.BF=0;
  26. if(value<prev.Data)//如果插入值小于双亲结点的值
  27. {
  28. prev.Left=current;//成为左孩子
  29. }
  30. else//如果插入值大于双亲结点的值
  31. {
  32. prev.Right=current;//成为右孩子
  33. }
  34. path[p]=current;//将新元素插入数组path的最后
  35. //修改插入点至根结点路径上各结点的平衡因子
  36. intbf=0;
  37. while(p>0)
  38. {//bf表示平衡因子的改变量，当新结点插入左子树，则平衡因子+1
  39. //当新结点插入右子树，则平衡因子-1
  40. bf=(value<path[p-1].Data)?1:-1;
  41. path[--p].BF+=bf;//改变当父结点的平衡因子
  42. bf=path[p].BF;//获取当前结点的平衡因子
  43. //判断当前结点平衡因子，如果为0表示该子树已平衡，不需再回溯
  44. //而改变祖先结点平衡因子，此时添加成功，直接返回
  45. if(bf==0)
  46. {
  47. returntrue;
  48. }
  49. elseif(bf==2||bf==-2)//需要旋转的情况
  50. {
  51. RotateSubTree(bf);
  52. returntrue;
  53. }
  54. }
  55. returntrue;
  56. }


4.2 删除

[cpp] view plaincopyprint?
  1. privatevoidRemoveNode(Nodenode)
  2. {
  3. Nodetmp=null;
  4. //当被删除结点存在左右子树时
  5. if(node.Left!=null&&node.Right!=null)
  6. {
  7. tmp=node.Left;//获取左子树
  8. path[++p]=tmp;
  9. while(tmp.Right!=null)//获取node的中序遍历前驱结点，并存放于tmp中
  10. {//找到左子树中的最右下结点
  11. tmp=tmp.Right;
  12. path[++p]=tmp;
  13. }
  14. //用中序遍历前驱结点的值代替被删除结点的值
  15. node.Data=tmp.Data;
  16. if(path[p-1]==node)
  17. {
  18. path[p-1].Left=tmp.Left;
  19. }
  20. else
  21. {
  22. path[p-1].Right=tmp.Left;
  23. }
  24. }
  25. else//当只有左子树或右子树或为叶子结点时
  26. {//首先找到惟一的孩子结点
  27. tmp=node.Left;
  28. if(tmp==null)//如果只有右孩子或没孩子
  29. {
  30. tmp=node.Right;
  31. }
  32. if(p>0)
  33. {
  34. if(path[p-1].Left==node)
  35. {//如果被删结点是左孩子
  36. path[p-1].Left=tmp;
  37. }
  38. else
  39. {//如果被删结点是右孩子
  40. path[p-1].Right=tmp;
  41. }
  42. }
  43. else//当删除的是根结点时
  44. {
  45. _head=tmp;
  46. }
  47. }
  48. //删除完后进行旋转，现在p指向实际被删除的结点
  49. intdata=node.Data;
  50. while(p>0)
  51. {//bf表示平衡因子的改变量，当删除的是左子树中的结点时，平衡因子-1
  52. //当删除的是右子树的孩子时，平衡因子+1
  53. intbf=(data<=path[p-1].Data)?-1:1;
  54. path[--p].BF+=bf;//改变当父结点的平衡因子
  55. bf=path[p].BF;//获取当前结点的平衡因子
  56. if(bf!=0)//如果bf==0，表明高度降低，继续后上回溯
  57. {
  58. //如果bf为1或-1则说明高度未变，停止回溯，如果为2或-2，则进行旋转
  59. //当旋转后高度不变，则停止回溯
  60. if(bf==1||bf==-1||!RotateSubTree(bf))
  61. {
  62. break;
  63. }
  64. }
  65. }
  66. }

分享到：
| 【查找结构5】多路查找树/B~树/B+树
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    二叉平衡树(AVL) C实现

    严蔚敏数据结构中二叉平衡树的实现，教材中的有点小bug

    AVL_tree.zip_AVL树_avl_tree_avl树左右子树_平衡树_高度平衡树

    AVL平衡树数据结构，任意节点的左右子树高度差不超过1

    AVL二叉平衡树删除--标准版

    AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版

    红黑树及AVL树常见平衡树实现

    实现了红黑树、AVL树的基本功能增删改查。学习交流，共同进步

    AVL树数据结构平衡二叉查找树

    在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的...

    AVL树详细解释,AVL树详细解释

    AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树

    AVL平衡树及插入操作的C语言实现

    AVL平衡树及插入操作的C语言实现

    二叉搜索树，红黑树，AVL平衡树，B树

    完整实现二叉搜索树，红黑树，AVL平衡树，B树的搜索插入删除基本功能和其它功能。红黑树和B树参考自算法导论。

    数据结构之AVL树详解

    AVL树是最早提出的自平衡二叉树，在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。AVL树种查找、插入和删除在平均和最坏情况下...

    AVL平衡树的查询&插入&删除

    本程序实现了AVL平衡树的 查询 插入 删除，代码完整

    VB.net编写的AVL平衡树

    编写环境 VS2008 支持插入，旋转，平衡等功能。

    avl.rar_avl_平衡树

    avl平衡树做的电话号码系统！！！可支持查询，修改，删除等操作

    权重平衡树的python实现

    不同于AVL树（储存子树的高度）和红黑树（储存虚构的“颜色”位），加权平衡树储存记账信息的方式是对应用真正有用的属性：一棵树下元素的数量等于它的根的大小，然而这个根的大小是一个用来实现顺序统计树操作的...

    红黑树和AVL树的实现

    红黑树和AVL树的代码实现，并显示树的形状，同时红黑树还可以输出个路径以及黑高度

    平衡二叉树（AVL树）浅析

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

    平衡二叉树-AVL树的实现

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

    AVL tree AVL树

    AVL tree AVL树 完全平衡树基本操作

    AVL树的判定问题.rar

    AVL 树是一种平衡二叉搜索树，AVL 树有一个特点，所有节点的平衡因子不能大于 1，即所有节点的左子树与右子树的深度差只能为-1，0，1。根据这个概念，判断 AVL 树 就是去判断一棵二叉树是否是二叉搜索树，并且是否...

    完美的平衡二叉排序树（AVL树）

    自己用C++实现的完美的平衡二叉排序树（AVL树），插入删除都已经实现，dev C++和vc2010中测试完美通过

    C#，自平衡二叉查找树（AVL Tree）的算法与源代码

    自平衡二叉查找树（AVL Tree）中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. ...

Magicbox
Global site tag (gtag.js) - Google Analytics