1
Ich arbeite an einem Problem auf BST und 2-3 Trees. Das Programm macht dasselbe nur mit verschiedenen Datenstrukturen, die das Inventar eines Baumarktes simulieren.Wie finde ich das richtige Kind in einem 2-3 Baum Java
Hier habe ich eine correctChild Methode, und es wird ein searchKey geleitet, das ist ein string, ist seine Aufgabe, einen Zeiger auf das Kind von this zurückzukehren, auf die wir sollten für searchKey bei der Suche bewegen.
Ich versuche meine 2-3 drei auf meine .txt-Dateien zu implementieren, aber mein Zeiger gibt mir einen Nullwert, der die Einfügung von Daten in meinem ganzen Programm beeinflusst.
/**********************************************************************************
***********************************************************************************
*
* 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
Es wirkt sich mein Einsatz Methode
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
und macht meine Ausgabe drucken, anstatt das Hinzufügen und das ist wegen 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
Was ist der beste Weg für die richtige zu überprüfen Kind eines Schlüssels für einen Baum 2-3? Alle Referenzen oder Vorschläge würden sehr geschätzt werden. korrekt Dank
Die findLeaf Methode verwendet Kind
private TwoThreeNode findLeaf(String searchKey)
{
TwoThreeNode Lsearch = null;
//ProductRecord code = null;
if (root!=null)
{
while (!root.isLeaf())
{
root.correctChild(searchKey);
}
}