Member Avatar for cppStudent

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

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
  protected static class BinaryNode<AnyType> {
    BinaryNode(AnyType theElement) {
      this(theElement, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt,
        BinaryNode<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
    }

    AnyType element;
    BinaryNode<AnyType> left; // left child
    BinaryNode<AnyType> right; // right child
  }

  BinaryNode<AnyType> root;

  public BinarySearchTree() {
    root = null;
  }

  public void insert(AnyType x) {
    root = insert(x, root);
  }

  public void preOrderPrint() {
    preOrderPrint(root, 0);
  }

  public void remove(AnyType x) {
    root = remove(x, root);
  }

  public BinaryNode<AnyType> getParent(AnyType x) {
    BinaryNode<AnyType> aParent = getParent(x, root);
    return aParent;
  }

  public BinaryNode<AnyType> getParentNew(AnyType x) {
    BinaryNode<AnyType> aParent = getParentNew(x, root, null);
    return aParent;
  }

  public boolean contains(AnyType x) {
    return contains(x, root);
  }

  public BinaryNode<AnyType> getMostRight(AnyType x, BinaryNode<AnyType> t) {
    if (t != null)
      while (t.right != null)
        t = t.right;

    return t;
  }

  private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
    if (t == null)
      return new BinaryNode(x, null, null);

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0)
      t.left = insert(x, t.left);
    else if (compareResult > 0)
      t.right = insert(x, t.right);
    else
      ;

    return t;
  }

  private void preOrderPrint(BinaryNode<AnyType> t, int a) {
    if (t != null) {

      for (int spaces = 0; spaces <= a; spaces++) {
        System.out.print("  ");
      }
      if (t == root)
        System.out.println(t.element + " (root)");
      else
        System.out.println(t.element);
      preOrderPrint(t.left, a + 1);
      preOrderPrint(t.right, a + 1);

    }
  }

  private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
    if (t == null)
      return t;

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0)
      t.left = remove(x, t.left);
    else if (compareResult > 0)
      t.right = remove(x, t.right);
    else if (t.right != null && t.left != null) {
      t.element = getMostRight(x, t.left).element;
      t.left = remove(t.element, t.left);
    } else if (t.right == null && t.left == null) {
      t = null;
    } else {
      if (t.left != null)
        t = t.left;
      else
        t = t.right;
    }
    return t;
  }

  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;
    }
  }

  private BinaryNode<AnyType> getParent(AnyType x, BinaryNode<AnyType> t) {

    if (t == null)
      return null;

    int compareResult = x.compareTo(t.element);

    if (t.left != null)
      if (x.compareTo(t.left.element) == 0)
        compareResult = 0;

    if (t.right != null)
      if (x.compareTo(t.right.element) == 0)
        compareResult = 0;

    if (compareResult < 0)
      return getParent(x, t.left);
    else if (compareResult > 0)
      return getParent(x, t.right);
    else
      return t;
  }

  private BinaryNode<AnyType> getParentNew(AnyType x, BinaryNode<AnyType> t,
      BinaryNode<AnyType> parent) {
    if (t == null) {
      return null;
    } else {
      if (x.compareTo(t.element) < 0) {
        return getParentNew(x, t.left, t);
      } else if (x.compareTo(t.element) > 0) {
        return getParentNew(x, t.right, t);
      } else if (x.compareTo(t.element) == 0) {
        return parent;
      } else
        return null;
    }
  }

  private boolean isLeftChild(BinaryNode<AnyType> t) {
    BinaryNode<AnyType> parent = getParentNew(t.element);
    return (t == parent.left);
  }

  private boolean isRightChild(BinaryNode<AnyType> t) {
    BinaryNode<AnyType> parent = getParentNew(t.element);
    return (t == parent.right);
  }

  protected BinaryNode<AnyType> rotateWithLeftChild(
      BinaryNode<AnyType> rotateNode) {
    BinaryNode<AnyType> k1 = rotateNode.right;
    rotateNode.right = k1.left;
    k1.left = rotateNode;
    return k1;

  }

  protected BinaryNode<AnyType> rotateWithRightChild(
      BinaryNode<AnyType> rotateNode) {
    BinaryNode<AnyType> k1 = rotateNode.left;
    rotateNode.left = k1.right;
    k1.right = rotateNode;
    return k1;
  }

  private BinaryNode<AnyType> doubleRotateLeft(BinaryNode<AnyType> rotateNode) {
    rotateNode.left = rotateWithLeftChild(rotateNode.left);
    return rotateWithRightChild(rotateNode);
  }

  private BinaryNode<AnyType> doubleRotateRight(BinaryNode<AnyType> granParent) {
    granParent.right = rotateWithRightChild(granParent.right);
    return rotateWithLeftChild(granParent);
  }

}
  • 2 Contributors
  • 3 Replies
  • 114 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by cppStudent

Recommended Answers

All 3 Replies

Member Avatar for BestJewSinceJC

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

Member Avatar for cppStudent

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

Member Avatar for cppStudent

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.