当前位置:  开发笔记 > 编程语言 > 正文

维基百科的不平衡AVL树的例子如何真正失衡?

如何解决《维基百科的不平衡AVL树的例子如何真正失衡?》经验,为你挑选了2个好方法。

替代文字

上面的图片来自"维基百科在AVL树上的条目",维基百科表示这是不平衡的.这棵树怎么还没有平衡?这是文章的引用:

节点的平衡因子是其右子树的高度减去其左子树的高度,并且具有平衡因子1,0或-1的节点被认为是平衡的.具有任何其他平衡因子的节点被视为不平衡,需要重新平衡树.平衡因子或者直接存储在每个节点上,或者从子树的高度计算出来.

左右子树的高度均为4.左侧树的右子树的高度为3,仍然只有1小于4.有人可以解释我缺少的东西吗?



1> JesperE..:

例如,节点76是不平衡的,因为其右子树的高度为0,左侧的高度为3.



2> James Curran..:

为了平衡,树中的每个节点都必须,

没有孩子,(做一个"叶子"节点)

有两个孩子.

或者,如果它只有一个孩子,那个孩子必须是一片叶子.

在您发布的图表中,9,54和76违反了最后一条规则.

适当平衡,树看起来像:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

更新:(差不多9年后,我在draw.io创建了一个很酷的在线图表)在此输入图像描述

推荐阅读
勤奋的瞌睡猪_715
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有