Subversion Repositories programming

// Written by Ira Snyder

// Due Date: 11-24-2004

// Project #4

import java.io.*;

import java.util.*;

class AVLTree {

    private int key, height;

    private Object data;

    private AVLTree left, right;

    public static final AVLTree NIL = new AVLTree();

    public AVLTree( int key, Object data ) {

        this.key = key;

        this.data = data;

        left = right = NIL;

    }

    public boolean add( int key, Object data ) {

        int oldSize = size();

        grow(key,data);

        return size() > oldSize;

    }

    //provide name mapping

    public boolean insert( int key, Object data ) {

        return add(key,data);

    }

    public AVLTree grow( int key, Object data ) {

        if( this == NIL ) return new AVLTree(key,data);

        if( key == this.key ) { this.data = data; return this; } //prevent key dupes, update data

        if( key < this.key ) left = left.grow(key,data);

        else right = right.grow(key,data);

        rebalance();

        height = 1 + Math.max(left.height,right.height);

        return this;

    }

    public int size() {

        if( this == NIL ) return 0;

        return 1 + left.size() + right.size();

    }

    //I like the BinaryTree toString better than the author's toString()

    //so I used it here instead. I left the author's code for completeness.

    /*

    public String toString() {

        if( this == NIL ) return "";

        return left + " " + key + " " + right;

    }

    */

    public String toString() {

        if( this == NIL ) return "()";

        String sLeft = sLeft = left.toString();

        String sRight = sRight = right.toString();

        String answer = new String();

        //assemble the string to return

        answer = "(";

        if( !sLeft.equals("()") ) { answer += sLeft + ","; }

        answer += key;

        if( !sRight.equals("()") ) { answer += "," + sRight; }

        answer += ")";

        //return the assembled string

        return answer;

    }

    private AVLTree() { //construct the empty tree

        left = right = this;

        height = -1;

    }

    private AVLTree( int key, Object data, AVLTree left, AVLTree right ) {

        this.key = key;

        this.data = data;

        this.left = left;

        this.right = right;

        height = 1 + Math.max(left.height,right.height);

    }

    private void rebalance() {

        if( right.height > (left.height + 1) ) {

            if( right.left.height > right.right.height ) right.rotateRight();

            rotateLeft();

        }

        else if( left.height > (right.height + 1) ) {

            if( left.right.height > left.left.height ) left.rotateLeft();

            rotateRight();

        }

    }

    private void rotateLeft() {

        left = new AVLTree(key,data,left,right.left);

        key = right.key;

        data = right.data;

        right = right.right;

    }

    private void rotateRight() {

        right = new AVLTree(key,data,left.right,right);

        key = left.key;

        data = left.data;

        left = left.left;

    }

    // new functions from Prog. Probs PG 411

    public int getHeight() { return height; }

    public int getHeight( int key ) {

        if( this == NIL ) { return -1; }

        if( key == this.key ) { return getHeight(); }

        if( key < this.key ) { return left.getHeight(key); }

        return right.getHeight(key);

    }

    public AVLTree getLeft() { 

        if( this == NIL ) { return NIL; }

        return left;

    }

    public AVLTree getLeft( int key ) {

        if( this == NIL ) { return null; } //key not in tree

        if( key == this.key ) { return getLeft(); }

        if( key < this.key ) { return left.getLeft(key); }

        return right.getLeft(key);

    }

    public AVLTree getRight() {

        if( this == NIL ) { return NIL; }

        return right;

    }

    public AVLTree getRight( int key ) {

        if( this == NIL ) { return null; } //key not in tree

        if( key == this.key ) { return getRight(); }

        if( key < this.key ) { return left.getRight(key); }

        return right.getRight(key);

    }

    public int getRoot() { return key; }

    public int getKey() { return key; }

    public Object getData() { return data; }

    public boolean contains( int x ) { 

        if( this == NIL ) { return false; }

        if( key == x ) { return true; }

        return left.contains(x) || right.contains(x);

    }

    // I am guessing this returns the tree with x == key as the root,

    // since the book was not very specific

    public Object get( int key ) {

        if( this == NIL ) { return NIL; }

        if( key == this.key ) { return data; }

        if( key < this.key ) { return left.get(key); }

        return right.get(key);

    }

    public boolean equals( Object object ) { 

        if( !(object instanceof AVLTree) ) { return false; }

        AVLTree temp = (AVLTree)object; //make it typed

        boolean l=false, r=false;

        //check the left

        if( left == NIL && temp.left == NIL ) l = true;

        else l = left.equals(temp.left);

        //check the right

        if( right == NIL && temp.right == NIL ) r = true;

        else r = right.equals(temp.right);

        return (temp.key == key) && l && r;

    }

    public AVLTree( int[] keys, Object[] data ) { 

        this(keys[0],data[0]); //create a new tree

        //call add() for every element in the array

        for( int i=1; i < keys.length; i++ ) add(keys[i],data[i]);

    }

    public boolean remove( int key ) {

        if( !contains(key) ) { return false; }

        removeHelper(this,key);

        if( contains(key) ) { return false; }

        return true;

    }

    private AVLTree removeHelper( AVLTree tree, int key ) {

        if( tree == NIL ) { return NIL; }

        else if( key < tree.key ) { tree.left = removeHelper(tree.left,key); }

        else if( key > tree.key ) { tree.right = removeHelper(tree.right,key); }

        else if( tree.left != NIL && tree.right != NIL ) { tree = deleteMinimum(tree.right); }

        else if( tree.left != NIL ) { tree = tree.left; }

        else { tree = tree.right; }

        tree.rebalance();

        return tree;

    }

    /*

    public boolean remove( int key ) { 

        if( this == NIL ) { return false; }

        if( key < this.key ) { return left.remove(key); }

        if( key > this.key ) { return right.remove(key); }

        if( left == NIL && right == NIL ) { 

            //same as "this = NIL;"

            setThis(NIL);

            return true; 

        }

        if( left == NIL ) { 

            //same as "this = new AVLTree(right.key,right.left,right.right);"

            AVLTree temp = new AVLTree(right.key,right.data,right.left,right.right);

            setThis(temp);

            return true;

        }

        if( right == NIL ) {

            //same as "this = new AVLTree(left.key,left.left,left.right);"

            AVLTree temp = new AVLTree(left.key,left.data,left.left,left.right);

            setThis(temp);

            return true;

        }

        //same as "this = new AVLTree(deleteMinimum(right));

        AVLTree temp = deleteMinimum(right);

        setThis(temp);

        rebalance(); //fix the balance

        return true;

    } 

    */

    public void ira_dm() {

        System.out.println( this );

        System.out.println( deleteMinimum(this) );

    }

    private AVLTree deleteMinimum( AVLTree tree ) {

        if( tree == NIL ) { return NIL; }

        if( tree.left == NIL && tree.right == NIL ) { return NIL; }

        if( tree.left == NIL ) { 

            return new AVLTree(tree.right.key,tree.right.data,

                               tree.right.left,tree.right.right); 

        }

        return new AVLTree(tree.key,tree.data,deleteMinimum(tree.left),tree.right);

    }

    private void setThis( AVLTree that ) {

        this.key = that.key;

        this.data = that.data;

        this.height = that.height;

        this.left = that.left;

        this.right = that.right;

    }

    public static void printInOrder( AVLTree tree ) {

        Queue queue = new Queue();

        queue.enqueue(tree);

        while( !queue.isEmpty() ) {

            AVLTree temp = (AVLTree)queue.dequeue();

            System.out.print(temp.getKey());

            if( temp.getLeft() != NIL ) { queue.enqueue(temp.getLeft()); }

            if( temp.getRight() != NIL ) { queue.enqueue(temp.getRight()); }

        }

    }

    public static void printPreOrder( AVLTree tree ) {

        if( tree == NIL ) return;

        System.out.print(tree.getKey());

        AVLTree.printPreOrder( tree.getLeft() );

        AVLTree.printPreOrder( tree.getRight() );

    }

} //end AVLTree class