对于任意总元素计数，AA 树如何在每个非叶节点始终有 2 个子节点？

Question

我一直在阅读 AA 树。它们的不变量之一是每个非叶节点都有两个子节点。当元素总数不小于 2 的幂时，这怎么能起作用？

例如，满的三层 AA 树总共有 7 个节点（第 1 层有 4 个节点，第 2 层有 2 个节点，第 3 层有 1 个节点）。如果我们添加了第八个节点，那么新的叶级别必须有七个空白，其中三个（新的）2 级节点具有零个子节点，其中一个仅具有一个子节点。兄弟/水平节点是关键吗？在考虑每个非叶节点两个子节点的规则时，我使用的至少一个参考文献没有区分实际子节点右节点和“兄弟”右节点。

是的，这个问题类似于“

红黑树中红色节点只能有 1 个黑色子节点吗？”，但针对的是 AA 树而不是红黑树。

Answer 1

它们的不变量之一是每个非叶节点都有两个子节点。

在 AA 树的文本中，“叶子”有两种不同的定义。一种是具有传统含义的地方，另一种是所有具有级别 1 的节点称为叶子的地方。请注意，后一个定义更广泛，并且还包括具有红色子节点（也是叶子）的节点。

使用后一个定义的来源通常会按照您引用的方式表述不变量。

坚持叶子的传统定义的来源（因为

绝对没有子节点，甚至不是红色），所述不变量用以下方式表示：级别大于1的每个节点都有两个子节点。

例如，这是一个有效的 AA 树：

             4
            / \
           2   6--7

节点 2、6 和 7 的级别为 1。两个孩子的要求仅适用于节点 4，因为它是唯一级别大于 1 的节点。

我希望这能澄清这一点。