2-3-4 树 · 插入后的根

2-3-4 树 · 插入后的根

按输入顺序把若干互不相同的整数插入一棵初始为空的 2-3-4 树，使用「自顶向下、边走边裂」策略，最后输出根节点的键。

自顶向下插入的要点：

1. 若根是 4-节点（已有 3 个键），先裂根：中键升为新根，树长高一层。
2. 从根下行找插入位置；路上遇到 4-节点的孩子，先裂开它（中键提到父亲），再继续下行——这样父亲永远有空位，绝不连环爆。
3. 到达叶子，把值有序插入。

这正是 COMP2521 21T3 Q3 那类「插入后根变成谁」的题。请补全 splitChild 和 insert。

输入

• 第 1 行：整数 n（个数，可能为 0）。
• 第 2 行：n 个互不相同的整数，按此顺序插入。

输出

• 一行：最终根节点的键，升序，每个值后跟一个空格。n = 0 时输出空行。

示例：输入 7 / 10 20 30 40 50 60 70 → 输出 20 40 （建树过程中发生多次裂变，最终根是 3-节点 [20 40]）。