1
234ツリーの新しいレベルを最初のレベルを超えて作成する値を追加する際に問題が発生しています。私のメソッドはルートオブジェクトに子を作成しますが、他のノードの子を作成することはできません。私は子ノードを作成するノードを埋めることができない限り、与えられた数のデータオブジェクトを作成して挿入することができます...私は真剣にこれを数日間梳かしてきました。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()
}
通常、私は私が問い合わせる午前固有のコードを投稿します。しかし、この特定のメソッドは他の2つのクラスにもジャンプします。だから私は彼らがどのように設定しているのかを見て、何らかの利益があると思った。
ザ・ノードクラス
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に今すぐ挿入できます。あなたが持つ可能性のあるあらゆる洞察に感謝します。