java - 234-树插入方法问题

Question

我在添加值时遇到问题，这些值会在我的 234 树中创建一个超出第一层的新层。我的方法在根对象上创建子节点，但无法为任何其他节点创建子节点。我能够创建和插入给定数量的数据对象，只要它们不填充导致它创建子节点的节点......我已经认真梳理了好几天。

我的问题基本上是基于我的代码。我的方法(特别是插入方法)是否允许在根目录下创建子节点？

树类

public class Tree234 {

    public Node root = new Node();  // make root node

    public int find(String key) {
        Node focus = root;
        int childNumber;
        while (true) {
            if ((childNumber = focus.findItem(key)) != -1) {
                return childNumber;               // found it
            } else if (focus.isLeaf()) {
                return -1;                        // can't find it
            } else // search deeper
            {
                focus = getNextChild(focus, key);
            }
        }  // end while
    }
    // insert a DataItem

    public void insert(String dWord) {  // Performs the splits
    // in a top-down (root -----> leaf) fashion.
        Node focus = root;

        DataItem tempItem = new DataItem(dWord);

        while (true) {

            if (focus.isFull()) { // if node full
                System.out.println("Need to split!");
                split(focus);   // split it
                System.out.println("Splint done?");                
                focus = focus.getParent();      // back up
                // search once
                focus = getNextChild(focus, dWord);
            } // end if (node is full)
            else if (focus.isLeaf()) {  // if node is leaf  
                break;                  // jump to insert
            } else {    // node is not full, not a leaf; so go to lower level 
                focus = getNextChild(focus, dWord);
            }

        }  // end while

        // insert new DataItem
        focus.insertItem(tempItem);

    }    // end insert

    public void split(Node thisNode) { // split the node

        // assumes node is full
        DataItem itemB, itemC;
        Node parent, child2, child3;
        int itemIndex;

        // two right most items are removed from the node and stored
        itemC = thisNode.removeItem();  // remove items from
        itemB = thisNode.removeItem();  // this node
        child2 = thisNode.disconnectChild(2);   // remove children
        child3 = thisNode.disconnectChild(3);   // from this node

        // make new node, goes to the right of the node being split
        Node newRight = new Node();

        if (thisNode == root) { // if this is the root
            // make new root
            root = new Node();
            // root is our parent
            parent = root;
            // connect to parent
            root.connectChild(0, thisNode);
        } else {// this node not the root get parent
            parent = thisNode.getParent();
        }
        // deal with parent

        // item B is inserted in the parent node
        itemIndex = parent.insertItem(itemB); // deal with parent
        // total items?
        int n = parent.getNumItems();

        // move parent's connections
        // one child to the right
        for (int j = n - 1; j < itemIndex; j--) {
            Node temp = parent.disconnectChild(j);
            parent.connectChild(j + 1, temp);
        }
        // connect newRight to parent
        parent.connectChild(itemIndex + 1, newRight);

        // deal with newRight
        newRight.insertItem(itemC);             // item C to newRight
        newRight.connectChild(0, child2);       // connect to 0 and 1
        newRight.connectChild(1, child3);       // on newRight
    }   // end split()

    public Node getNextChild(Node theNode, String keyWord) {

        int j;
        // assumes node is not empty, not full, not a leaf
        int numItems = theNode.getNumItems();

        // for each item in node
        for (j = 0; j < numItems; j++) {
            // is the value given less than the value at the 
            //first index of the array?                           
            if (keyWord.compareToIgnoreCase(theNode.getItem(j).dData) < 0) {
                // if so, return left child so we can use it at another 
                // point in time
                return theNode.getChild(j);
            }

        } // end for
        return theNode.getChild(j);
        // otherwise, our value is greater we're greater, so
        // we return right child (the child right after the 
        // value given, greater)        
    }

    public void displayTree() {
        recDisplayTree(root, 0, 0);
    }

    public void recDisplayTree(Node thisNode, int level, int childNumber) {
        System.out.print("level=" + level + " child=" + childNumber + " ");
        thisNode.displayNode();               // display this node

        // call ourselves for each child of this node
        int numItems = thisNode.getNumItems();
        for (int j = 0; j < numItems + 1; j++) {
            Node nextNode = thisNode.getChild(j);

            if (nextNode != null) {
                recDisplayTree(nextNode, level + 1, j);
            } else {
                return;
            }
        }
    }         // end recDisplayTree()

}

通常我只会发布我要查询的具体代码。然而，这个特殊的方法也跳入了其他两个类。所以我认为看看我如何设置它们会有一些好处。

节点类

public class Node {
    // Max size
    private static final int SIZE = 4;

    public int numItems;
    public Node parent;
    public Node children[] = new Node[SIZE];
    public DataItem items[] = new DataItem[SIZE - 1];

    public void connectChild(int childNum, Node child) {    //  Connect child to this Node
        children[childNum] = child;
        if (child != null) {
            child.parent = this;
        }
    }

    public Node disconnectChild(int childNum) { //  Disconnect child from this Node
        Node temp = children[childNum];
        children[childNum] = null;
        return temp;
    }

    public Node getChild(int childNum) {    // Returns child
        return children[childNum];
    }

    public Node getParent() {   // Returns parent
        return parent;
    }

    public Boolean isLeaf() {
        // test if child is a leaf
        return children[0] == null;
    }

    public int getNumItems() {
        return numItems;
    }

    public DataItem getItem(int index) {
        return items[index];
    }

    public Boolean isFull() {
        return numItems == SIZE - 1;
    }

    public int findItem(String term) {
        for (int j = 0; j < SIZE; j++) {

            if (items[j] == null) {
                break;
            } else if (items[j].dData.equalsIgnoreCase(term)) {
                return j;
            }
        }
        return -1;
    }     // end findItem()

    public int insertItem(DataItem newItem) {
        if (findItem(newItem.dData) != -1) {
            items[findItem(newItem.dData)].count++;
            return 0;
        }
        numItems++; // will add new item
        String newKey = newItem.dData;

        for (int j = numItems-1; j >= 0; j--) {
            if (items[j] != null){
                System.out.println(items[j].dData);

            }
            if (items[j] == null) {
            continue;
            } else {
                String itsKey = items[j].dData;
                if (newKey.compareToIgnoreCase(itsKey) < 0) {
                    items[j + 1] = items[j];
                } else {
                    items[j + 1] = newItem;
                    return j + 1;
                }
            }   // end else (not null)
        }       // end for  ---->   //  shifted all items,
        items[0] = newItem;     //  insert new item
        return 0;

    }   // end insertItem()

    public DataItem removeItem() {
        DataItem temp = items[numItems - 1];
        items[numItems - 1] = null;
        numItems--;
        return temp;
    }

    public void displayNode() {
        for (int j = 0; j < numItems; j++) {
            items[j].displayItem();
        }
        System.out.println();
    }
}   // end class Node

我现在已将所有内容设置为公开，因为我只是在测试代码的结构。

DataItem 类

public class DataItem {

    public String dData;
    public int count;

    public DataItem(String term) {
        dData = term;
        count = 1;
    }
    public String getItem() {
        return this.dData;
    }
    public int getCount() {
        return this.count;
    }
    public void displayItem() {
        System.out.print("\nWord: " + dData + "\t\tCount: " + count);
    }
}

下面是我如何将 DataItem 对象添加到树中。

public class Main {

    public static void main(String[] args) {

        Tree234 tree = new Tree234();

        for (int i = 0; i < 13; i++) {
            String temp = RandomName.getLast();
            System.out.println(temp);
            tree.insert(temp); 
        }
        tree.displayTree();                    
}            

输出

    Townsend
    George
    Townsend
    Welch
    Townsend
    Clemons
    George
    Rose
    George
    Bond
    Townsend
    Clemons
    Bowers
    Clemons
    Bond
    Foreman
    Townsend
    George
    Clemons
    Hahn
    Townsend
    Alston
    Bond
    Petersen
    Townsend
    Hahn
    Hansen
    George
    Hahn
    Moses
    Hansen
    level=0 child=0 
    Word: George            Count: 1
    Word: Petersen          Count: 1
    level=1 child=0 
    Word: Bowers            Count: 1
    level=2 child=0 
    Word: Alston            Count: 1
    Word: Bond          Count: 1
    level=2 child=1 
    Word: Clemons           Count: 1
    Word: Foreman           Count: 1
    level=1 child=1 
    Word: Hahn          Count: 1
    Word: Hansen            Count: 1
    Word: Moses         Count: 1
    level=1 child=2 
    Word: Townsend          Count: 1

树“似乎”可以工作，但是添加超过 10 个名称开始使其变得不稳定。它根本无法处理 15 个或更多。

输出15个或更多

    Bowman
    Moore
    Bowman
    Anthony
    Moore
    Bowman
    Graham
    Moore
    Nielsen
    Exception in thread "main" java.lang.NullPointerException
    Moore
    Camacho
    Bowman
    Graham
    Herman
    Graham
    Gallagher
    Moore
    Bowman
    Camacho
    Hartman
    Herman
    Daniels
    Gallagher
    Camacho
    Snyder
        at dataPackage.Tree234.insert(Tree234.java:40)
        at testPackage.Main.main(Main.java:31)
    X:\source\234Tree\234Tree\nbproject\build-impl.xml:1040: The following error occurred while executing this line:
    X:\source\234Tree\234Tree\nbproject\build-impl.xml:805: Java returned: 1
    BUILD FAILED (total time: 0 seconds)

我对算法还是很陌生，所以我可能完全遗漏了一些简单的东西。我开始认为插入方法很好，但我可能没有正确拆分。这就是为什么我现在可以插入到 2 级而不是更远。感谢您提供任何见解。

Answer 1

正如我所怀疑的那样!!我在树类中错误地拆分了节点。

for (int j = n - 1; j < itemIndex; j--) { // in this line  I had a '<' and should have
    Node temp = parent.disconnectChild(j); // had a '>' 
    parent.connectChild(j + 1, temp);
}

感谢所有和我一起看这个的人。