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 AVLTree left, right;

    public static final AVLTree NIL = new AVLTree();

    public AVLTree( int key ) {
        this.key = key;
        left = right = NIL;
    }

    public boolean add( int key ) {
        int oldSize = size();
        grow(key);
        return size() > oldSize;
    }

    public AVLTree grow( int key ) {
        if( this == NIL ) return new AVLTree(key);
        if( key == this.key ) return this; //prevent key dupes
        if( key < this.key ) left = left.grow(key);
        else right = right.grow(key);

        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, AVLTree left, AVLTree right ) {
        this.key = key;
        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,left,right.left);
        key = right.key;
        right = right.right;
    }

    private void rotateRight() {
        right = new AVLTree(key,left.right,right);
        key = left.key;
        left = left.left;
    }
    
    // new functions from Prog. Probs PG 411
    public int getHeight() { return height; }
    
    public AVLTree getLeft() { 
        if( this == NIL ) { return NIL; }
        return left;
    }
    
    public AVLTree getRight() { 
        if( this == NIL ) { return NIL; }
        return right;
    }
    
    public int getRoot() {
        return key;
    }

    public boolean contains( int x ) { 
        if( this == NIL ) { return false; }
        if( key == x ) { return true; }

        return left.contains(x) || right.contains(x);
    }
    
    // am guessing this returns the tree with x == key as the root
    public AVLTree get( int x ) {
        if( this == NIL ) { return NIL; }
        if( x == key ) { return this; }

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

    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[] a ) { 
        this(a[0]); //create a new tree
        
        //call add() for every element in the array
        for( int i=1; i < a.length; i++ ) add(a[i]);
    }

    /*
    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 ) { this = NIL; return true; }
        if( left == NIL ) { 
            this = new AVLTree(right.key,right.left,right.right);
            return true;
        }
        if( right == NIL ) {
            this = new AVLTree(left.key,left.left,left.right);
            return true;
        }
        this = new AVLTree( deleteMinimum(right) );
        rebalance(); //fix the balance
        return true;
    }
    
    private int deleteMinimum( AVLTree tree ) {
        int tempKey=0;
        
        if( left == NIL ) { 
            tempKey = key;
            this = new AVLTree(right.key,right.left,right.right);
        }
        if( left.left == NIL && left.right == NIL ) {
            tempKey = key;
            this = new AVLTree(left.key,left.left,right.right);
        }
        return deleteMinimum(left);
    }
    */

} //end AVLTree class