c# - 2-3（二-三）树插入方法c#

Question

我在 C# 中实现 2-3 树插入方法时遇到问题。我有工作 B 树的简单实现，在此基础上我需要为 2-3 树创建插入方法。我观看了 2-3 树如何工作的视频，但我不知道如何在代码中实现它。

任何人都可以帮助我编辑此代码并将其用于 2-3 树。

这是我拥有的 B-tree 的代码：

void Main()
{
BTree bTree = new BTree(4);

foreach (int key in new[] { 4, 6, 8, 3, 9, 1, 11, 12, 14, 17, 5, 20, 25})
{
    bTree.Insert(key);
}
}

public class BTree
{
private Node root;

private int minDegree;

private class Node
{
    int minDegree;

    public Node[] Children { get; set; }

    public int[] Keys { get; set; }

    public bool IsLeaf { get; set; }

    public int Size { get; set; }

    public Node(int degree)
    {
        minDegree = degree;
        Keys = new int[(2 * degree) - 1];
        Children = new Node[2 * degree];
    }
}

  public BTree(int minDegree)
{
    if (minDegree < 2)
    {
        throw new Exception("B tree degree must be at least 2");
    }

    this.minDegree = minDegree;
    root = new Node(minDegree);
    root.IsLeaf = true;
}

public void Insert(int value)
{
    InsertNode(root, value);
}

private void InsertNode(Node current, int value)
{
    Node temp = root;

    if (current.Size == (2 * minDegree) - 1)
    {
        Node newRoot = new Node(minDegree);
        root = newRoot;
        newRoot.IsLeaf = false;
        newRoot.Size = 0;
        newRoot.Children[0] = temp;
        SplitChild(newRoot, 0);
        InsertNonFull(newRoot, value);
    }
    else
    {
        InsertNonFull(current, value);
    }
}

private void InsertNonFull(Node current, int value)
{
    int i = current.Size - 1;

    if (current.IsLeaf)
    {
        while (i >= 0 && value < current.Keys[i])
        {
            current.Keys[i + 1] = current.Keys[i];
            i -= 1;
        }
        current.Keys[i + 1] = value;
        current.Size += 1;
    }
    else
    {
        while (i >= 0 && value < current.Keys[i])
        {
            i -= 1;
        }
        i += 1;

        if (current.Children[i].Size == (2 * minDegree) - 1)
        {
            SplitChild(current, i);
            if (value > current.Keys[i])
            {
                i += 1;
            }
        }
        InsertNonFull(current.Children[i], value);
    }
}

private void SplitChild(Node nonFullParent, int indexOfFullChild)
{
    Node newNode = new Node(minDegree);
    Node fullChild = nonFullParent.Children[indexOfFullChild];

    newNode.IsLeaf = fullChild.IsLeaf;
    newNode.Size = minDegree - 1;

    for (int i = 0; i < minDegree - 1; i++)
    {
        newNode.Keys[i] = fullChild.Keys[i + minDegree];
    }

    if (!fullChild.IsLeaf)
    {
        for (int i = 0; i < minDegree; i++)
        {
            newNode.Children[i] = fullChild.Children[i + minDegree];
        }
    }

    fullChild.Size = minDegree - 1;

    for (int i = nonFullParent.Size; i == indexOfFullChild + 1; i--)
    {
        nonFullParent.Children[i + 1] = nonFullParent.Children[i];
    }
    nonFullParent.Children[indexOfFullChild + 1] = newNode;

    for (int i = nonFullParent.Size; i == indexOfFullChild; i--)
    {
        nonFullParent.Keys[i + 1] = nonFullParent.Keys[i];
    }
    nonFullParent.Keys[indexOfFullChild] = fullChild.Keys[minDegree - 1];
    nonFullParent.Size = nonFullParent.Size + 1;
}

public bool Find(int value)
{
    Node result = FindNode(root, value);
    if (result != null)
    {
        return true;
    }
    return false;
}

private Node FindNode(Node current, int value)
{
    Node temp = current;

    int i = 0;

    while (i <= current.Size - 1 && value > current.Keys[i])
    {
        i++;
    }

    if (i <= current.Size - 1 && value == current.Keys[i])
    {
        return current;
    }
    else if (current.IsLeaf)
    {
        return null;
    }
    else
    {
        return FindNode(current.Children[i], value);
    }
}
}