2-3树-分裂困难

Question

我的任务是创建2-3棵树。我已经完成了所需的所有必要的类和方法，但我的拆分方法有困难。我可能想得太多了，我的头脑在旋转，我似乎无法摆脱我已经陷入的思路。

如果只要求我拆分一个叶节点，我就不会有问题。在我的头脑似乎被卡住的地方，我必须分裂一个叶节点，然后分裂上面的父节点。据我所知，孩子们的分离，然后分裂，然后孩子们的联系，都会因孩子最初被分裂的不同而不同。

也就是说，如果我有下面的树，我的第一个分裂发生在叶节点(比如根的第二个子节点的第三个子节点，13 \14)。这个拆分过程与根的第三个子进程的第一个子进程不同(19 \ 20)。

                                            9 |18
           3 |  6                          12 | 15                          21 | 24
 1 |  2    4 |  5    7 |  8      10 | 11   13 | 14   16 | 17      19 | 20   22 | 23   25 |26

我的拆分方法中，我有问题的部分是：

    if (upperRight != null)
    {
        if (childIndex == 0)
        {
            parent.connectChild(1, newRight);
            newRight.connectChild(0, child1);
            newRight.connectChild(1, child2);
        }
        else if (childIndex == 1)
        {
            upperRight.connectChild(0, newRight);
        }
        else if (childIndex == 2)
        {
            upperRight.connectChild(0, newRight);
        }
    }
    else
    {
        Node temp = parent.disconnectChild(1);
        parent.connectChild(1, newRight);
        parent.connectChild(2, temp);

        if (childIndex == 0)
        {
            temp = newRight.disconnectChild(0);
            newRight.connectChild(0, child1);
            newRight.connectChild(1, child2);
            newRight.connectChild(2, temp);
        }
        else if (childIndex == 1)
        {
            thisNode.connectChild(1, child1);
            newRight.connectChild(1, child2);
        }
        else if (childIndex == 2)
        {
            temp = newRight.disconnectChild(0);
            thisNode.connectChild(1, child1);
            newRight.connectChild(0, child2);
            newRight.connectChild(1, temp);
        }
    }
    return newRight;

如果有人能帮助指导我如何以不同的方式看待这件事，我将不胜感激。我收到的输出要么是我的孩子的顺序不正确，要么是我正在覆盖一些孩子，或者两者兼而有之。

Answer 1

在Robert的平衡搜索树 of Algorithms中，讨论了利用四个节点来实现分裂的技术。