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

The method you were supposed to override is called contains, not contain.

Sorry, it's a typo. A bunch of them. :$

I've found the problem. Quite obvious if you think about it :D

public class newSplay<AnyType extends Comparable<? super AnyType>> extends SplayTree<AnyType>
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.