在我的2-3树中插入一个值时，我得不到一个期望值

Question

我目前正在创建一个2-3树，但我遇到了一个问题。我在网上到处寻找关于如何在我的2-3树中插入一个值的例子，但我仍然遇到了问题。我收到的错误是它期望的值是9，但它是0。我不明白为什么它一开始不插入9，因为9是要插入到树中的第一个值，在我的insert方法中，我将：

 if (root == null) {
        root = new Node(x);
        return true;
 }

它不是只需要创建一个值为9的新节点，它就能正常工作吗？

下面是我的节点类：

import java.util.ArrayList;

public class Node {

private Node parent;
private Node leftChild;
private Node middleChild;
private Node rightChild;
private Node fourthChild;
int smallKey;
int largeKey;
// creates nodes
ArrayList<Node> children = new ArrayList<Node>();
// creates list of numbers to insert into node
ArrayList<Integer> nodeData = new ArrayList<Integer>();

public Node(int x) {
    parent = null;
    nodeData.add(x);
}

public Node(int x, Node leftChild, Node middleChild, Node rightChild, Node fourthChild)
{
    parent = null;
    nodeData.add(x);
    leftChild = children.get(0);
    middleChild = children.get(1);
    rightChild = children.get(2);
    fourthChild = children.get(3);
    smallKey = nodeData.get(0);
    largeKey = nodeData.get(2);
}

public void addChild(Node newNode) {
    newNode.parent = this;
    this.children.add(newNode);
}

public boolean isLeaf() {
    return children.isEmpty();
}

public String toString() {
    if (this.nodeData.size() >= 2) {
        return Integer.toString(this.smallKey) + " " + 
        Integer.toString(this.largeKey);
    } else {
        return Integer.toString(this.smallKey);
    }
}

public Node addData(Node node, int x) {
    if(x < node.smallKey)
    {
        node.leftChild = addData(node.leftChild, x); 
    }
    else if(x > node.largeKey)
    {
        node.rightChild = addData(node.rightChild, x);
    }
    else
    {
        node.middleChild = addData(node.middleChild, x);
    }
    return node;
}

Node findNode(Node currentNode, int x) {
    if (currentNode.isLeaf()) {
        return currentNode;
    }
    if (x < currentNode.smallKey) {
        return findNode(currentNode.leftChild, x);
    } else if (x > currentNode.largeKey) {
        return findNode(currentNode.rightChild, x);
    } else {
        return findNode(currentNode.middleChild, x);
    }
}
}

我的2-3班级：

public class TwoThreeTree {
Node root;

public TwoThreeTree() {
    root = null;
}

public boolean insert(int x) {
    if (root == null) {
        root = new Node(x);
        return true;
    }
    Node insertNode = root.findNode(root, x);
    insertNode.addData(root, x);
    if (insertNode.nodeData.size() == 3) {
        insertNode.addData(root, x);
        root.split(insertNode);
    }
    return true;
}

public String search(int x) {
    Node searchNode = root.findNode(root, x);
    return searchNode.toString();
    }
}

下面是我的测试用例：

public class TwoThreeTreeGivenTests
{
  @Test
  public void singleNodeTree()
  {
  TwoThreeTree t = new TwoThreeTree();
  int val = 9;
  t.insert(val);
  String expected = "9";

  assertEquals(expected, t.search(val));
  val = 8;
  assertEquals(expected, t.search(val));
  val = 10;
  assertEquals(expected, t.search(val));


  val = 15;
  t.insert(val);
  expected = "9 15";
  val = 9;
  assertEquals(expected, t.search(val));
  val = 8;
  assertEquals(expected, t.search(val));

  t = new TwoThreeTree();
  val = 15;
  t.insert(val);
  val = 9;
  t.insert(val);
  val = 9;
  assertEquals(expected, t.search(val));
  val = 8;
  assertEquals(expected, t.search(val));
  }

Answer 1

Node.toString() (由TwoThreeTree.search()调用)返回一个包含smallKey或smallKey和largeKey的字符串，但这两个变量从未设置过(默认为0)。

关于构造函数

public Node(int x, Node leftChild, Node middleChild, Node rightChild, Node fourthChild)

这将设置smallKey和largeKey有几个问题：

1. 如果要调用它，它永远不会调用
2. ，它将失败并出现异常，因为它试图从children和nodeData中检索项，这两个项是在ArrayList调用时分别包含0和1项的get()项可以检索到它们被设置为局部变量/参数leftChild，<代码>d19ArrayList>，...而不是成员变量。

为了确保设置了成员变量，这里必须以this.作为前缀，以避免遮蔽。第三点不适用于smallKey和largeKey，因为它们不受本地variables/parameters.的影响