Assignment 11 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial. If you have trouble with the classpath settings you could try reading this tutorial.
Unless stated otherwise, you are not allowed to use any classes from the dataStructures or the java.util packages.

For any coding question below, even in cases where you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
super();
}

public ALLExtended( int n ){
super(n);
}

  1. AVL tree
    Start with an empty AVL search tree and insert the keys 10,25,23,50,14,3,17,20,5,27,30 in this order.
    Draw figures similar to Figures 16.2 depicting your tree immediately after each insertion and following the rebalancing rotation (if any).
    You do not need to label nodes with their balance factors but MUST identify the rotation type (if any) that is done. See lec27.ppt (or section 16.1.5 in the book) for all possible rotations. You should follow the steps given in Fig 16.6 to solve this problem.

  2. Binary Search Tree
    In this problem, you will extend the BinarySearchTree class to support several additional functions.
    PLEASE put all your solutions in one single java file. Name this file MyBinarySearchTree.java.
    a) Implement a new method check(), which will check whether the current tree is a binary search tree or not. For example, if MyBinarySearchTree t equals to:



    then t.check() should return true. But if t equals to:



    t.check() should return false.

    b) Implement a new method removeLarger(int x), which will remove all elements larger than x from a given binarySearchTree.
    For example, if t equals to:



    After calling t.removeLarger(5), t should become



    Note that the worst time complexity of your method must be O(n), where n is the size of the tree.

You are NOT allowed to call any method of the BinarySearchTree class. Calling one of these methods can cost up to 100% of the question grade.

The template is:

package dataStructures;

public class MyBinarySearchTree extends BinarySearchTree {

    //Add any member variable when necessary
    public boolean check()
    {
        //Your code goes here
    }
    public void removeLarger(int x)
    {
        //Your code goes here
    }

    private boolean isLeaf(BinaryTreeNode current)
    {
        if((current.leftChild != null)||(current.rightChild != null))
            return false;
        return true;
    }
    public void print()
    {
        printR(root,0);
    }
    private void printR(BinaryTreeNode current,int level)
    {
        String blank = "";
        for(int i = 0 ; i < level ; i++)
        {
            blank += "\t";
        }
        if(current == null)
        {
            blank += "null";
            System.out.println(blank);
            return;
        }
        blank += current.toString();
        if(!isLeaf(current))
        {
            printR(current.rightChild,level + 1 );
            System.out.println(blank);
            printR(current.leftChild,level + 1 );
        }
        else
        {
            System.out.println(blank);
        }
    }

    // Please use the test code as follows.
    public static void main(String[] args) {
        MyBinarySearchTree t = new MyBinarySearchTree();

        int[] a = new int[10];
        a[0] = 21;
        a[1] = -72;
        a[2] = 56;
        a[3] = 39;
        a[4] = -29;
        a[5] = 93;
        a[6] = 7;
        a[7] = -19;
        a[8] = 26;
        a[9] = 2;

        for(int i = 0 ; i < 10 ; i++)
        {
            t.put(new Integer(a[i]),new Integer(a[i]));
        }
        System.out.println("t=");
        t.print();
        System.out.println("t.check() = " + t.check());
        System.out.println();

        t.root.leftChild.element = new Data(new Integer( -1) ,new Integer(-1));
        System.out.println("t=");
        t.print();
        System.out.println("t.check() = " + t.check());
        System.out.println();

        System.out.println("t=");
        t.root.leftChild.element = new Data(new Integer( -72) ,new Integer(-72));
        t.removeLarger(5);
        t.print();

    }
}