data-structures - 红黑树发明者 - 红黑树的应用




维基百科的一个不平衡的AVL树的例子是如何不平衡的? (3)

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

上面的图片来自维基百科指出的“维基百科在AVL树上的条目”不平衡。 这棵树如何不平衡已经? 这里有一篇文章的引用:

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

左边和右边的子树都有4的高度。左边的树的右边的子树的高度是3,仍然只有1小于4.有人可以解释我错过了什么吗?


直觉上,这是因为它不是尽可能小。 例如,12应该是9和14的父亲。因为它是9,没有左子树,所以它是不平衡的。 树是分层数据结构,因此像“平衡”这样的规则通常适用于每个节点而不仅仅是根节点。

你是正确的,根节点是平衡的,但不是树的所有节点。


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

  • 没有孩子,(是一个“叶”节点)
  • 有两个孩子。
  • 或者,如果只有一个孩子,那个孩子必须是一片叶子。

    在你张贴的图表中,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





avl-tree