我正在解决 BST 和 2-3 树的问题。该程序使用不同的数据结构执行相同的操作，模拟硬件商店的库存。
这里我有一个 CorrectChild 方法，它传递了一个 searchKey ，它是一个 字符串，它的任务是返回一个指向 this 子级的指针，我们应该在搜索 searchKey 时将其移动到该子级。
我正在尝试在 .txt 文件上实现 2-3 3，但我的指针不断给我一个空值，这会影响整个程序中数据的插入。
/**********************************************************************************
***********************************************************************************
*
* 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);
}
}
最佳答案
您的 findLeaf 方法基本上不执行任何操作，因为 Lsearch 从未分配过值，因此它将始终返回 null。
这就是没有所有注释代码的样子:
private TwoThreeNode findLeaf(String searchKey) {
TwoThreeNode Lsearch = null;
if ( root!=null ) {
while (!root.isLeaf()) {
root.correctChild(searchKey);
}
}
return Lsearch;
}
据推测，要解决问题(或至少进一步进展)，您需要执行诸如 Lsearch = root. CorrectChild(searchKey) 之类的分配。
关于java - 如何在 2-3 树 java 中找到正确的子节点进行搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36464288/