Hi Guys,
Been on the boards for a while answering other people's queries. I think it's high time I posed my problems to you
I am working on implementing a
2-3 Tree and I am at the end of my wits trying to get this figured out (lack of sleep has something to do with it
). Here is a nice
applet that further shows how the tree works.
I am having trouble trying to "split" the nodes right. Here is my code so far.. it is a bit much and if some parts don't make sense please ask for clarification.
I am using a TreeNode class that looks like
Code:
public class TreeNode
{
/**
* Constructor initializes the various node values
*/
public TreeNode()
{
smallKey = -1001;
bigKey = -1001;
right = null;
left = null;
middle = null;
parent = null;
}
/**
* This method returns true if the node is empty
* @return true if node is empty false otherwise
*/
public boolean isEmpty()
{
if (this.smallKey == -1001 && this.bigKey == -1001)
return true;
else
return false;
}
//Data Fields
public TreeNode left;
public TreeNode right;
public TreeNode middle;
public TreeNode parent;
public int smallKey;
public int bigKey;
//public final int DEFAULT_VALUE = -1001
}
And my TwoThreeTree makes use of this node to build the tree.
Code:
public class TwoThreeTree
{
/**
* Constructor creates a node to initialize the tree
*/
public TwoThreeTree()
{
root = new TreeNode();
}
/**
* Method to traverse the tree looking for a node to insert the given key
* @param key to be searched
* @param starting node (always root)
* @return TreeNode where the value occurs (or would have occurred)
*/
public TreeNode searchTree(int key, TreeNode node)
{
TreeNode n = new TreeNode();
//Check if the node is empty... Need a better way to do this
//Only supposed to be true once, when we first deal with root node and
//this is where the 4th value is getting inserted in the wrong place.
if (node.smallKey == -1001 || node.bigKey == -1001)
{
//if a match is found return the node
return node;
}
else
{
//if the key is smaller than the small key
//go to the left child of tree
if (key < node.smallKey)
{
if (node.left == null)
return node;
//But if the left child doesn't exist return the node
//otherwise continue searching down the tree
else searchTree(key, node.left);
}
//if key is bigger than the big key go to
//the right child of the tree
else if (key > node.bigKey)
{
if (node.right == null)
return node;
else searchTree(key, node.right);
}
//The last option is the key is inbetween big and small
//so go the middle child
else
{
if (node.middle == null)
return node;
else searchTree(key, node.middle);
}
}
//Otherwise we don't have a tree and need to create one
return n;
}
/**
* This method inserts a key into the tree
* @param key to be inserted into the tree
*/
public void insert(int key)
{
tnode = searchTree(key, root);
//This should happen only once for root
if (tnode.isEmpty())
{
tnode.smallKey = key;
}
//Problem Child continues here from the search method as the wrong node
//is returned and value is added to the wrong place
else if (tnode.bigKey == -1001)
{
tnode.bigKey = key;
if (tnode.smallKey > key)
{
tnode.bigKey = tnode.smallKey;
tnode.smallKey = key;
}
}
else
split(key, tnode);
}
/**
* This method splits a given node
* @param key the value causing the split
* @param node to be split
*/
public void split(int key, TreeNode node)
{
//If the node doesn't have a parent we are dealing with the root
//node
if (node.parent == null)
{//THIS NEEDS SERIOUS WORK :((((((((((((
//Create a new node to be root
TreeNode t = new TreeNode();
node.parent = t;
//And another node to be the other child
TreeNode c = new TreeNode();
c.parent = t;
root = t;
if (key > node.smallKey && key < node.bigKey)
{
//Set the key for new parent node to the promoted value
t.smallKey = key;
//Set the key for the new child as the bigKey from split node
c.smallKey = node.bigKey;
//Reset the bigKey value in the split node
node.bigKey = -1001;
}
else if (key < node.smallKey)
{
t.smallKey = node.smallKey;
t.left = node;
node.smallKey = key;
c.smallKey = node.bigKey;
t.right = c;
node.bigKey = -1001;
}
else
{
t.smallKey = node.bigKey;
t.right = c;
node.bigKey = -1001;
c.smallKey = key;
}
}
}
public TreeNode getRoot()
{
return root;
}
//Data Fields
private TreeNode tnode;
private TreeNode root;
}
Lots of code.. I am sorry. But I think it is fairly straightforward at this point and it works correctly for the first 3 values. It's the 4th value that it flounders at. I have put the comments //Problem Child at those parts.
If anyone has seen 2-3 Trees before and knows a better way of doing this, please kindly point me in the right direction.
My code is loosely based on the pseudo code provided in the wikipedia
link at the bottom of the 2-3 Tree description. Again any help will be greatly appreciated.
Linear Mode
