Subversion Repositories programming

// Written by Ira Snyder
// Due Date: 11-24-2004
// Project #4
// Helped and was Helped By: Allen Oliver
// Got information from: 
//     http://www.cs.dartmouth.edu/~chepner/cs15/notes/08_bst.html

import java.io.*;
import java.util.*;

class AVLTree {
    private int key, height;
    private Object data;
    private AVLTree left, right;

    //create an empty tree to be used instead of checking
    //for nulls all over the place
    public static final AVLTree NIL = new AVLTree();

    //constructor for the basic AVLTree
    public AVLTree( int key, Object data ) {
        this.key = key;
        this.data = data;
        left = right = NIL;
    }
    
    //method to insert a new key-data pair into the tree
    public boolean add( int key, Object data ) {
        int oldSize = size();
        grow(key,data);
        return size() > oldSize;
    }

    //provide name mapping for add
    public boolean insert( int key, Object data ) {
        return add(key,data);
    }

    //method to add an element to a tree
    private AVLTree grow( int key, Object data ) {
        if( this == NIL ) return new AVLTree(key,data);

        //prevent key dupes, update data
        if( key == this.key ) { this.data = data; return this; } 
        if( key < this.key ) left = left.grow(key,data);
        else right = right.grow(key,data);

        rebalance(); //fix the balance as we recurse back up

        height = 1 + Math.max(left.height,right.height);
        return this;
    }
    
    //method to return the size of the tree
    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;
    }
    */
    
    //method to print the tree as a String
    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;
    }
 
    //constructor to make the empty tree
    private AVLTree() {
        left = right = this;
        height = -1;
    }
    
    //constructor to make a new AVLTree given a key-data pair, and left
    //and right subtrees
    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);
    }
    
    //method to rebalance the tree if it is out of balance, using rotations
    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();
        }
    }
    
    //method to rotate the tree to the left
    private void rotateLeft() {
        left = new AVLTree(key,data,left,right.left);
        key = right.key;
        data = right.data;
        right = right.right;
    }

    //method to rotate the tree to the right
    private void rotateRight() {
        right = new AVLTree(key,data,left.right,right);
        key = left.key;
        data = left.data;
        left = left.left;
    }
    
    //method to return the height of the tree
    public int getHeight() { return height; }

    //method to return the height of the subtree with the
    //given key
    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);
    }
    
    //method to return the left subtree
    public AVLTree getLeft() { 
        if( this == NIL ) { return NIL; }
        return left;
    }
    
    //method to return the left subtree of the subtree with the
    //given key
    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);
    }
    
    //method to return the right subtree
    public AVLTree getRight() {
        if( this == NIL ) { return NIL; }
        return right;
    }
    
    //method to return the right subtree of the subtree with the
    //given key
    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);
    }
    
    //method to return the key of the root
    public int getRoot() { return key; }

    //method to return the key of the root
    public int getKey() { return key; }

    //method to return the data of the root
    public Object getData() { return data; }

    //method to see if the tree contains a key
    public boolean contains( int x ) { 
        if( this == NIL ) { return false; }
        if( key == x ) { return true; }

        return left.contains(x) || right.contains(x);
    }
    
    //return the data associated with a given key
    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);
    }

    //check if two trees are equals
    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;
    }

    //method to create a new tree from an array of keys,
    //and an array of data
    public AVLTree( int[] keys, Object[] data ) { 
        //this(keys[0],data[0]); //create a new tree
        
        if( keys.length != data.length ) { throw new IllegalArgumentException(); }
        
        this.key = keys[0];
        this.data = data[0];
        left = right = NIL;
        
        //call add() for every element in the array
        for( int i=1; i < keys.length; i++ ) add(keys[i],data[i]);
    }
    
    //method to remove a key-data pair from the tree
    public boolean remove( int key ) {
        if( !contains(key) ) { return false; }
        removeHelper(this,key);
        if( contains(key) ) { return false; }
        return true;
    }
    
    //a helper method for remove, which performs the actual recursion
    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(); //rebalance as we recurse back up
        return tree;
    }
    
    //method to remove the minimum element in a tree
    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);
    }
    
    //method to print a tree InOrder
    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()); }
        }
    }

    //method to print a tree in PreOrder
    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