tree - 这个 RBT 如何被认为是平衡的？

Question

我一直在玩 RBT 可视化工具，但不明白如何将以下内容视为高度平衡。维基百科文章声称，如果满足 RBT 属性，则最远叶子的高度不大于最近叶子高度的两倍。根据我的理解，即使满足 RBT 属性（深度 1 为 1，深度 6 为 3），以下内容也会违反此属性。我的逻辑在哪里有缺陷？

Answer 1

来自维基百科的文章：

红黑树的叶节点（图 1 中的 NIL）不包含键或数据。这些“叶子”不需要是计算机内存中的显式个体：NULL 指针可以——就像在所有二叉树数据结构中一样——编码这样一个事实，即在（父）节点的这个位置没有子节点。然而，根据它们在树中的位置，这些对象与其他节点相关......</p>

您在问题中包含的图表省略了这些NIL节点，但它们与确定平衡有关。使用您描述的规则（“从根到最远叶子的路径不超过从根到最近叶子的路径的两倍”），从根到最近叶子的路径距离为2（不是一个），从根到最远的叶子的路径有四个（不是三个）的距离。

由于四不超过二的两倍，因此这棵树符合“平衡”规则。