2

我的任务是创建一个 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;

如果有人可以帮助指导我如何以不同的方式思考这个问题，我将不胜感激。我收到的输出要么是我的孩子的顺序不正确，要么是我在某个地方覆盖了一些孩子，或者两者兼而有之。

4

1 回答 1

0

Robert Sedgwich在Balanced Search Trees of Algorithms中讨论了使用四个节点来帮助进行拆分的技术。

于 2013-06-06T00:35:58.693 回答