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

Question

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

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

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

Answer 1

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

Answer 2

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

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

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

  在您发布的图表中,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创建了一个很酷的在线图表)