1
BST ve 2-3 Ağaçlarında bir sorun üzerinde çalışıyorum. Program, bir donanım deposunun envanterini simüle eden farklı veri yapılarıyla aynı şeyi yapar. İşte2-3 Ağacı java'da arama yapmak için doğru çocuğu nasıl bulabilirim?
Bir correctChild yöntemine sahip ve bir string bir searchKey geçirilir, onun görevi biz searchKey arayışında hareket etmeliyiz hangi this çocuğu bir gösterici döndürmektir.
.txt dosyalarında 2-3 üç uygulamayı deniyorum, ancak işaretçim tüm programımda veri ekleme işlemini etkileyen null bir değer veriyor.
/**********************************************************************************
***********************************************************************************
*
* 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
Benim insert metodu
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
etkiler ve ekleme yerine bu benim çıkış baskı yapar ve bu çünkü
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
findLeaf
ait ne var doğru kontrol etmenin en iyi yoludur 2-3 ağacın anahtarı mı? herhangi bir referans veya öneri çok takdir edilecektir. TeşekkürfindLeaf yöntemi doğru çocuğa kullanır Sizin findLeaf yöntem temelde hiç bir değer atanır ve bu yüzden her zaman null dönecektir Lsearch olarak hiçbir şey yapmıyor
private TwoThreeNode findLeaf(String searchKey)
{
TwoThreeNode Lsearch = null;
//ProductRecord code = null;
if (root!=null)
{
while (!root.isLeaf())
{
root.correctChild(searchKey);
}
}