WebSVN – programming – Diff – /cs241/p4/AVLTree.java

 // 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
+    //provide name mapping for add
     public boolean insert( int key, Object data ) {
         return add(key,data);
+    }
+    //method to add an element to a tree
-    public AVLTree grow( int key, Object data ) {
+    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; } //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();
+        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();
+    }
         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();
         //return the assembled string
         return answer;
+    }
-    private AVLTree() { //construct the empty tree
+    //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;
+    }
-    // new functions from Prog. Probs PG 411
+    //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);
+    }
-    // I am guessing this returns the tree with x == key as the root,
-    // since the book was not very specific
+    //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
         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
+        //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.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
+        tree.rebalance(); //rebalance as we recurse back up
-        return true;
+        return tree;
-    }
-    */
-    public void ira_dm() {
-        System.out.println( this );
-        System.out.println( deleteMinimum(this) );
+    }
+    //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);
+    }
-    private void setThis( AVLTree that ) {
+    //method to print a tree InOrder
-        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() ) {
             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() );

Subversion Repositories programming

(root)/cs241/p4/AVLTree.java @ 47 – Rev 45 → 46