1
我對BST和2-3樹問題的工作進行搜索。該程序僅使用模擬硬件存儲庫的不同數據結構來執行相同的操作。如何找到正確的孩子在2-3樹的java
在這裏，我有一個correctChild方法，它傳遞一個searchKey這是一個string，它的任務是返回一個指針的this孩子，我們應該在尋求移動的searchKey。
我想實現我的2-3 3對我的.txt文件，但我的指針一直給我影響數據在我的整個程序中插入一個空值。
/**********************************************************************************
***********************************************************************************
*
* TwoThreeTree class
*
* A leaf-based 2-3 tree:
* - all data is stored in the leaves
* - interior nodes contain only index values to guide searches
*
***********************************************************************************
***********************************************************************************/
class TwoThreeTree
{
/**************************************************************
**************************************************************
* Nodes for the TwoThreeTree
**************************************************************
**************************************************************/
private class TwoThreeNode
{
public String[] key;
public ProductRecord data;
public TwoThreeNode[] child;
public int numKeys;
public TwoThreeNode parent;
// Create a new leaf for data d with key k. The leaf should have parent p.
public TwoThreeNode(String k, ProductRecord d, TwoThreeNode p)
{
key = new String[1]; // A leaf holds only ONE key, with its associated data.
key[0] = k; // The key of a data item!
data = d; // The data item associated with this key.
numKeys = 1;
child = null; // A leaf will _never_ have children.
parent = p;
}
// Create a new interior Node to contain index key k with parent p
// and two children l and r.
public TwoThreeNode(String k, TwoThreeNode p, TwoThreeNode l, TwoThreeNode r)
{
key = new String[2]; // May later hold 2 index values.
key[0] = k; // The index value.
key[1] = null;
data = null; // Interior nodes never contain real data (only index keys to guide the search).
numKeys = 1;
child = new TwoThreeNode[3]; // May later have 3 children.
child[0] = l;
child[1] = r;
child[2] = null;
parent = p;
}
/************************************************************
*
* printInorder
* Do an inorder traversal of the subtree rooted at
* the calling TwoThreeNode, printing the data values
* (i.e., only the data stored in the leaves)
*
**************************************************************/
public void printInorder()
{
ProductRecord code;
if (root.isLeaf())
{
code = root.data;
System.out.println(code);
}
else
{
root.child[0].printInorder();
if (root.numKeys == 2)
{
root.child[1].printInorder();
}
root.child[2].printInorder();
}
/*************** YOUR CODE GOES HERE ***********************/
} // end printInorder
/************************************************************
*
* correctChild
*
* Figure out which child to move to in the search for searchKey.
* Return a pointer to that child.
*
* Idea:
* - i is the index of the child we think we should move to
* - start by assuming we should move to the rightmost child
* - loop: if searchKey is less than the index value separating
* the current child from the child immediately to the left of it
* move i to the child immediately to the left
*
**************************************************************/
public TwoThreeNode correctChild(String searchKey)
{
TwoThreeNode result = null;
int i = numKeys+1;
if (root!=null)
{
if (!root.isLeaf())
{
if (this.numKeys == 1) // three child nodes
{
if (searchKey.compareTo(this.key[0]) < 0)
{
result = root.child[0];
}
else //greater than 0 move right
{
result = root.child[1];
}
}
if(root.numKeys ==2) // two child node
{
if (searchKey.compareTo(this.key[0]) < 0)
{
result = root.child[0];
}
else if(searchKey.compareTo(this.key[0]) > 0) //greater than the first key, move right
{
result = root.child[2];
}
else // the the middle child is less than or equal to the first key
{
result = root.child[1];
}
}
}
}
return result;
/*************** YOUR CODE GOES HERE ***********************/
}
/************************************************************
*
* isLeaf
* Return true if the TwoThreeNode is a leaf; false
* otherwise.
*
* Note: A TwoThreeNode is a leaf if it has no children
* and if it has no children, then child is null.
*
**************************************************************/
public boolean isLeaf()
{
return (child == null);
}
} // end class TwoThreeNode
/***************************************************************
****************************************************************
* Returning to class TwoThreeTree
****************************************************************
***************************************************************/
private TwoThreeNode root;
/************************************************************
*
* TwoThreeTree constructor
*
* Create an empty tree
*
**************************************************************/
public TwoThreeTree()
{
root = null;
}
/************************************************************
*
* findLeaf
*
* Return the leaf where searchKey should be
* (if it is in the tree at all).
*
* (A private helper method for search and insert.
*
**************************************************************/
private TwoThreeNode findLeaf(String searchKey)
{
TwoThreeNode Lsearch = null;
//ProductRecord code = null;
if (root!=null)
{
while (!root.isLeaf())
{
root.correctChild(searchKey);
}
}
/*if (root !=null)
{
result = find(searchKey);
System.out.println(result);
}
else
{
System.out.println("nooooo");
}*/
/*if (root == null)
{
System.out.println("nooooo");
}
else
{
result = find(searchKey);
System.out.println(result);
}*/
//res = find(searchKey);
return Lsearch;
/*************** YOUR CODE GOES HERE ***********************/
}
/************************************************************
*
* find
* Find and return the ProductRecord stored with key
* searchKey (or return null if searchKey is not in
* any leaf in the tree).
*
**************************************************************/
public ProductRecord find(String searchKey)
{
TwoThreeNode result;
ProductRecord code = null;
if (root!=null)
{
result = findLeaf(searchKey);
if (result!=null)
{
code = root.data;
}
}
return code;
/*************** YOUR CODE GOES HERE ***********************/
}
/************************************************************
*
* insert
* Insert ProductRecord p with key newKey into the tree.
* - First, search for newKey all the way to the leaves.
* - If the leaf contains newKey, simply return.
* - Otherwise, call recursive method addNewLeaf to handle
* the insertion (including any splitting and
* pushing up required).
*
**************************************************************/
public void insert(String newKey, ProductRecord p )
{
TwoThreeNode curr;
TwoThreeNode nextCurr;
boolean found = false;
int i;
if (root == null)
{
// Empty tree: Add first node as the root (it has no parent)
root = new TwoThreeNode(newKey, p, null);
}
else
{
// Tree is not empty.
// Find the leaf that would contain newKey if newKey is already in the tree.
curr = findLeaf(newKey);
if (curr != null && !curr.key[0].equals(newKey))
{
// The leaf at which the search ended does not contain searchKey.
// Insert!
addNewLeaf(newKey, p, curr);
}
else if (curr == null)
{
System.out.println("Not inserting " + newKey
+ ": search failed with curr == null in non-empty tree");
}
} // end else root != null
} // end insert
/************************************************************
*
* addNewLeaf
* Add a new leaf containing newKey and ProductRecord p into the tree.
* Add the new leaf as a child of the parent of leaf lsearch
* (where the search for newKey ended) if there's room.
* Otherwise, if the parent of lsearch has no room,
* split the parent and push the problem up to the grandparent.
* All work at the grandparent or above (where all nodes ---
* parent or child --- are interior nodes) is handled by
* helper method addIndexValueAndChild.
*
**************************************************************/
private void addNewLeaf(String newKey, ProductRecord p, TwoThreeNode lsearch)
{
TwoThreeNode lsParent = lsearch.parent;
TwoThreeNode newChild = new TwoThreeNode(newKey, p, lsParent);
int lsIndex = -1; // (will be) index of pointer to lsearch in lsParent.child array
// in case we have to split lsParent:
TwoThreeNode newParent;
String middleValue, largestValue;
TwoThreeNode secondLargestChild, largestChild;
if (lsParent == null)
{
// lsearch is the ONLY node in the tree (it's the root)
// create a new root to be the parent of lsearch and newChild
if (newKey.compareTo(lsearch.key[0]) < 0)
{
// newChild should be the left child, lsearch the right
root = new TwoThreeNode(lsearch.key[0], null, newChild, lsearch);
}
else
{
root = new TwoThreeNode(newKey, null, lsearch, newChild);
}
lsearch.parent = root;
newChild.parent = root;
}
else // lsearch has a parent (and lsearch is not the root)
{
if (lsearch == lsParent.child[0])
lsIndex = 0;
else if (lsearch == lsParent.child[1])
lsIndex = 1;
else if (lsParent.numKeys == 2 && lsearch == lsParent.child[2])
lsIndex = 2;
else
System.out.println("ERROR in addNewLeaf: Leaf lsearch containing " + lsearch.key[0]
+ " is not a child of its parent");
if (lsParent.numKeys == 1)
{
// Parent has room for another leaf child
if (newKey.compareTo(lsearch.key[0]) < 0)
{
if (lsIndex == 1)
{
lsParent.child[2] = lsearch;
lsParent.child[1] = newChild;
lsParent.key[1] = lsearch.key[0];
}
else
{
lsParent.child[2] = lsParent.child[1];
lsParent.key[1] = lsParent.key[0];
lsParent.child[1] = lsearch;
lsParent.child[0] = newChild;
lsParent.key[0] = lsearch.key[0];
}
}
else // lsearch's key is < newKey
{
if (lsIndex == 1)
{
lsParent.child[2] = newChild;
lsParent.key[1] = newKey;
}
else
{
lsParent.child[2] = lsParent.child[1];
lsParent.key[1] = lsParent.key[0];
lsParent.child[1] = newChild;
lsParent.key[0] = newKey;
}
}
lsParent.numKeys = 2;
newChild.parent = lsParent;
}
else
{
// Parent has NO room for another leaf child --- split and push up
if (lsIndex == 2) // lsearch is rightmost of 3 children
{
if (lsearch.key[0].compareTo(newKey) < 0)
{
largestChild = newChild;
secondLargestChild = lsearch;
largestValue = newKey;
middleValue = lsParent.key[1];
}
else // newKey < lsearch.key[0]
{
largestChild = lsearch;
secondLargestChild = newChild;
largestValue = lsearch.key[0];
middleValue = lsParent.key[1];
}
}
else if (lsIndex == 1) // lsearch is middle of 3 children
{
largestChild = lsParent.child[2];
largestValue = lsParent.key[1];
if (lsearch.key[0].compareTo(newKey) < 0)
{
secondLargestChild = newChild;
middleValue = newKey;
}
else // newKey < lsearch.key[0]
{
secondLargestChild = lsearch;
middleValue = lsearch.key[0];
lsParent.child[1] = newChild;
newChild.parent = lsParent;
}
}
else // lsIndex == 0 lsearch is leftmost of 3 children
{
largestChild = lsParent.child[2];
secondLargestChild = lsParent.child[1];
largestValue = lsParent.key[1];
middleValue = lsParent.key[0];
if (lsearch.key[0].compareTo(newKey) < 0)
{
lsParent.child[1] = newChild;
lsParent.key[0] = newKey;
}
else // newKey < lsearch.key[0]
{
lsParent.child[1] = lsearch;
lsParent.child[0] = newChild;
lsParent.key[0] = lsearch.key[0];
}
newChild.parent = lsParent;
}
newParent = new TwoThreeNode(largestValue, lsParent.parent, secondLargestChild, largestChild);
lsParent.numKeys = 1;
lsParent.key[1] = null;
lsParent.child[2] = null;
largestChild.parent = newParent;
secondLargestChild.parent = newParent;
// add new parent to grandparent:
if (lsParent.parent == null)
{
root = new TwoThreeNode(middleValue, null, lsParent, newParent);
lsParent.parent = root;
newParent.parent = root;
}
else
addIndexValueAndChild(lsParent.parent, middleValue, newParent);
}
} // end else lsearch has a parent
}
/************************************************************
*
* addIndexValueAndChild
* Insert index value m and the corresponding new child (mChild)
* into TwoThreeNode curr.
*
* (A child of curr was split, and index value m and new child mChild
* are the result of the split and must be added to curr, if possible.
* If they can't be added to curr (because curr is already full), then
* curr must also be split and the problem pushed up to curr's parent.)
*
**************************************************************/
private void addIndexValueAndChild(TwoThreeNode curr,
String m, TwoThreeNode mChild)
{
TwoThreeNode newNode;
String midKey;
if (curr.numKeys == 1)
{
// There's room for m and its child in curr.
if (m.compareTo(curr.key[0]) < 0)
{
// First child of curr was split to create mChild.
// Order of keys: m < curr.key[0].
// Order of children: curr.child[0] < mChild < curr.child[1].
// m becomes the first key and its child becomes
// the middle child.
curr.key[1] = curr.key[0];
curr.child[2] = curr.child[1];
curr.key[0] = m;
curr.child[1] = mChild;
}
else
{
// Second child of curr was split to create mChild.
// Order of keys: curr.key[0] < m.
// Order of children: curr.child[0] < curr.child[1] < mChild.
// m becomes the second key and its child
// becomes the rightmost child.
curr.key[1] = m;
curr.child[2] = mChild;
}
curr.numKeys = 2;
mChild.parent = curr;
}
else
{
// There's no room for m and its child in curr.
// Split curr into two (the original
// TwoThreeNode curr and a new TwoThreeNode) and
// push the middle key and a pointer to the new
// TwoThreeNode up to the parent.
if (m.compareTo(curr.key[0]) < 0)
{
// First child of curr was split to create mChild.
// Order of keys: m < curr.key[0] < curr.key[1].
// Order of children:
// curr.child[0] < mChild < curr.child[1] < curr.child[2].
// Original node gets key m and children
// curr.child[0] and mChild.
// New node gets key curr.key[1] and children
// curr.child[1] and curr.child[2].
// curr.key[0] is the middle key.
midKey = curr.key[0];
newNode = new TwoThreeNode(curr.key[1], curr.parent, curr.child[1], curr.child[2]);
curr.child[1].parent = newNode;
curr.child[2].parent = newNode;
mChild.parent = curr;
curr.key[0] = m;
curr.child[1] = mChild;
}
else if (m.compareTo(curr.key[1]) < 0)
{
// Second child of curr was split to create curr.
// Order of keys: curr.key[0] < m < curr.key[1].
// Order of children:
// curr.child[0] < curr.child[1] < mChild < curr.child[2].
// Original node retains key curr.key[0] and children
// curr.child[0] and curr.child[1].
// New node gets key curr.key[1] and children
// mChild and curr.child[2].
// m is the middle key.
midKey = m;
newNode = new TwoThreeNode(curr.key[1], curr.parent, mChild, curr.child[2]);
mChild.parent = newNode;
curr.child[2].parent = newNode;
}
else
{
// Order of keys: curr.key[0] < curr.key[1] < m.
// Order of children:
// curr.child[0] < curr.child[1] < curr.child[2] < mChild.
// Original node retains key curr.key[0] and children
// curr.child[0] and curr.child[1].
// New node gets key m and children
// curr.child[2] and mChild.
// curr.key[1] is the middle key.
midKey = curr.key[1];
newNode = new TwoThreeNode(m, curr.parent, curr.child[2], mChild);
curr.child[2].parent = newNode;
mChild.parent = newNode;
}
curr.numKeys = 1;
curr.key[1] = null;
curr.child[2] = null;
if (curr != root)
addIndexValueAndChild(curr.parent, midKey, newNode);
else
{
root = new TwoThreeNode(midKey, null, curr, newNode);
curr.parent = root;
newNode.parent = root;
}
}
} // end addIndexValueAndChild
/************************************************************
*
* printTable
* Print an appropriate message if the tree is empty;
* otherwise, call a recursive method to print the
* data values in an inorder traversal.
*
**************************************************************/
public void printTable()
{
if (root != null)
{
this.root.printInorder();
}
else
{
System.out.println("The tree is empty");
}
/*************** YOUR CODE GOES HERE ***********************/
} // end printTree
} // end class TwoThreeTree
它會影響我的插入方法
public void insert(String newKey, ProductRecord p )
{
TwoThreeNode curr;
TwoThreeNode nextCurr;
boolean found = false;
int i;
if (root == null)
{
// Empty tree: Add first node as the root (it has no parent)
root = new TwoThreeNode(newKey, p, null);
}
else
{
// Tree is not empty.
// Find the leaf that would contain newKey if newKey is already in the tree.
curr = findLeaf(newKey);
if (curr != null && !curr.key[0].equals(newKey))
{
// The leaf at which the search ended does not contain searchKey.
// Insert!
addNewLeaf(newKey, p, curr);
}
else if (curr == null)
{
System.out.println("Not inserting " + newKey
+ ": search failed with curr == null in non-empty tree");
}
} // end else root != null
} // end insert
，使我的輸出打印，而不是添加的，這就是因爲findLeaf
Not inserting P24-Qbw-2495: search failed with curr == null in non-empty tree
Not inserting P33-Qes-4782: search failed with curr == null in non-empty tree
Not inserting P25-Taa-1244: search failed with curr == null in non-empty tree
Not inserting P25-Tab-3509: search failed with curr == null in non-empty tree
Not inserting P25-Tab-3506: search failed with curr == null in non-empty tree
Not inserting P25-Tac-3672: search failed with curr == null in non-empty tree
什麼是檢查正確的最佳方式2-3樹的鑰匙的孩子？任何參考或建議將非常感激。由於
的findLeaf方法使用正確的子
private TwoThreeNode findLeaf(String searchKey)
{
TwoThreeNode Lsearch = null;
//ProductRecord code = null;
if (root!=null)
{
while (!root.isLeaf())
{
root.correctChild(searchKey);
}
}