为何任意元素数量的AA-Tree非叶节点始终拥有两个子节点？

你提到的“每个非叶节点都有两个子节点”，其实是指逻辑层面的节点，而非单个物理节点——这正是AA树通过水平链接（兄弟节点）实现平衡的核心。

关键概念：水平链接与逻辑节点 #

AA树用水平链接（同一level的右向链接，对应红黑树的红色右节点）将多个物理节点组合成一个逻辑节点。规则里的“非叶节点”指的是这个逻辑节点，而非单独的物理节点：

• 每个逻辑非叶节点必然拥有两个子节点（左、右子节点均为更低level的逻辑节点或叶节点）
• 单个物理节点可能只有一个子节点，但它会通过水平链接与兄弟节点组成完整的逻辑节点，满足双子女要求

你的例子解析 #

以满3层（物理节点总数7）的AA树为例：

• 此时所有物理节点的level分别为3（根）、2（2个节点）、1（4个节点），每个物理节点的子节点都是更低一级的节点，无水平链接。

当添加第8个节点后，AA树会触发splitting（分裂）和skewing（倾斜）操作来维护规则：

1. 新节点会作为某个level1节点的子节点加入，导致该level1节点的level提升为2
2. 此时会出现两个同level的水平链接节点（原level2节点和新升级的level2节点）
3. 分裂操作会将其中一个level2节点提升为level3，原根节点的level降为2，形成新的水平链接逻辑节点

最终结构中：

• 新的根是一个由两个level2节点组成的逻辑节点，它的左、右子节点分别是level1的逻辑节点（或物理节点）
• 单个物理节点可能看起来只有一个子节点，但它属于某个逻辑节点，整个逻辑节点依然满足双子女规则

与红黑树问题的对应 #

你提到的红黑树问题，核心是红节点的子女规则；而AA树通过水平链接将多个物理节点打包成逻辑节点，本质上是用更严格的链接规则（仅允许右向水平链接）简化了红黑树的复杂约束，让“非叶节点双子女”的规则在逻辑层面始终成立——这也是为什么有些资料会将物理节点的右兄弟视为逻辑节点的一部分，而非独立的子节点。

内容的提问来源于stack exchange，提问作者CTMacUser