Hi!
I implemented a Binary search tree, which worked as desired. Then I had to create a new class which inherits from "BinarySearchTree" called "SplayTree". "SplayTree" has only one method called "contain" which overrides the inherited "contain". The new "contain" will return a boolean. If the object is found in contains then that node must be splayed using bottom-up technique.
The problem is: I changed the "contains" method in "BinarySearchTree", not overriding it in "SplayTree". When I try to use that implementation in "SplayTree" I reveive a lot errors.
1.) Can someone please have a look at the way I'm splaying the nodes and tell if there's a better implementation, I have a feeling that I got lost somewhere.
2.) How I can override it in a class that extends BinarySearchTree.
I'll attach the java file.
New contain that splay.
private boolean contains(AnyType x, BinaryNode<AnyType> t)
{
if (t == null)
return false;
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
return contains(x, t.left);
else if (compareResult > 0)
return contains(x, t.right);
else
{
while (getParentNew(t.element) != null)
{
if (getParentNew(t.element).element.compareTo(root.element) == 0)
{
if (x.compareTo(root.left.element) == 0)
{
t = rotateWithRightChild(root);
}
else
{
t = rotateWithLeftChild(root);
}
}
else
if (getParentNew(getParentNew(t.element).element) != null)
{
BinaryNode<AnyType> granParent = getParentNew(getParentNew(t.element).element);
BinaryNode<AnyType> parent = getParentNew(t.element);
if (isLeftChild(t)&& isLeftChild(parent))
{
rotateWithRightChild(granParent);
rotateWithRightChild(parent);
}
else
if (isRightChild(t)&& isRightChild(getParentNew(t.element)))
{
rotateWithLeftChild(granParent);
rotateWithLeftChild(parent);
}
else //zag-zig
if(isRightChild(t) && isLeftChild(getParentNew(t.element)))
{
doubleRotateLeft(granParent);
}
else//zig-zag
{
t = doubleRotateRight(granParent);
}
if (getParentNew(granParent.element) != null)
{
if (isRightChild(granParent))
{
getParentNew(granParent.element).right = t;
}
else
if (isLeftChild(granParent))
{
getParentNew(granParent.element).left = t;
}
}
}
}
root = t;
return true;
}
}
Old contain which need to be "override"
private boolean contains(AnyType x, BinaryNode<AnyType> t)
{
if (t == null)
return false;
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
return contains(x, t.left);
else if (compareResult > 0)
return contains(x, t.right);
else
return true;
}
Any help will be appreciated.
Thanks