上面的图片来自"维基百科在AVL树上的条目",维基百科表示这是不平衡的.这棵树怎么还没有平衡?这是文章的引用:
节点的平衡因子是其右子树的高度减去其左子树的高度,并且具有平衡因子1,0或-1的节点被认为是平衡的.具有任何其他平衡因子的节点被视为不平衡,需要重新平衡树.平衡因子或者直接存储在每个节点上,或者从子树的高度计算出来.
左右子树的高度均为4.左侧树的右子树的高度为3,仍然只有1小于4.有人可以解释我缺少的东西吗?
例如,节点76是不平衡的,因为其右子树的高度为0,左侧的高度为3.
为了平衡,树中的每个节点都必须,
没有孩子,(做一个"叶子"节点)
有两个孩子.
或者,如果它只有一个孩子,那个孩子必须是一片叶子.
在您发布的图表中,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创建了一个很酷的在线图表)