Subversion Repositories programming

Rev

Rev 42 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 42 Rev 43
Line 5... Line 5...
5 
import java.io.*;
 5 
import java.io.*;
6 
import java.util.*;
 6 
import java.util.*;
7 
 
 7 
 
8 
class AVLTree {
 8 
class AVLTree {
9 
    private int key, height;
 9 
    private int key, height;
- 
 
 10 
    private Object data;
10 
    private AVLTree left, right;
 11 
    private AVLTree left, right;
11 
 
 12 
 
12 
    public static final AVLTree NIL = new AVLTree();
 13 
    public static final AVLTree NIL = new AVLTree();
13 
 
 14 
 
14 
    public AVLTree( int key ) {
 15 
    public AVLTree( int key, Object data ) {
15 
        this.key = key;
 16 
        this.key = key;
- 
 
 17 
        this.data = data;
16 
        left = right = NIL;
 18 
        left = right = NIL;
17 
    }
 19 
    }
18 
 
 20 
 
19 
    public boolean add( int key ) {
 21 
    public boolean add( int key, Object data ) {
20 
        int oldSize = size();
 22 
        int oldSize = size();
21 
        grow(key);
 23 
        grow(key,data);
22 
        return size() > oldSize;
 24 
        return size() > oldSize;
23 
    }
 25 
    }
24 
 
 26 
 
- 
 
 27 
    //provide name mapping
- 
 
 28 
    public boolean insert( int key, Object data ) {
- 
 
 29 
        return add(key,data);
- 
 
 30 
    }
- 
 
 31 
 
25 
    public AVLTree grow( int key ) {
 32 
    public AVLTree grow( int key, Object data ) {
26 
        if( this == NIL ) return new AVLTree(key);
 33 
        if( this == NIL ) return new AVLTree(key,data);
27 
        if( key == this.key ) return this; //prevent key dupes
 34 
        if( key == this.key ) { this.data = data; return this; } //prevent key dupes, update data
28 
        if( key < this.key ) left = left.grow(key);
 35 
        if( key < this.key ) left = left.grow(key,data);
29 
        else right = right.grow(key);
 36 
        else right = right.grow(key,data);
30 
 
 37 
 
31 
        rebalance();
 38 
        rebalance();
32 
 
 39 
 
33 
        height = 1 + Math.max(left.height,right.height);
 40 
        height = 1 + Math.max(left.height,right.height);
34 
        return this;
 41 
        return this;
Line 70... Line 77...
70 
    private AVLTree() { //construct the empty tree
 77 
    private AVLTree() { //construct the empty tree
71 
        left = right = this;
 78 
        left = right = this;
72 
        height = -1;
 79 
        height = -1;
73 
    }
 80 
    }
74 
 
 81 
 
75 
    private AVLTree( int key, AVLTree left, AVLTree right ) {
 82 
    private AVLTree( int key, Object data, AVLTree left, AVLTree right ) {
76 
        this.key = key;
 83 
        this.key = key;
- 
 
 84 
        this.data = data;
77 
        this.left = left;
 85 
        this.left = left;
78 
        this.right = right;
 86 
        this.right = right;
79 
        height = 1 + Math.max(left.height,right.height);
 87 
        height = 1 + Math.max(left.height,right.height);
80 
    }
 88 
    }
81 
 
 89 
 
Line 89... Line 97...
89 
            rotateRight();
 97 
            rotateRight();
90 
        }
 98 
        }
91 
    }
 99 
    }
92 
 
 100 
 
93 
    private void rotateLeft() {
 101 
    private void rotateLeft() {
94 
        left = new AVLTree(key,left,right.left);
 102 
        left = new AVLTree(key,data,left,right.left);
95 
        key = right.key;
 103 
        key = right.key;
- 
 
 104 
        data = right.data;
96 
        right = right.right;
 105 
        right = right.right;
97 
    }
 106 
    }
98 
 
 107 
 
99 
    private void rotateRight() {
 108 
    private void rotateRight() {
100 
        right = new AVLTree(key,left.right,right);
 109 
        right = new AVLTree(key,data,left.right,right);
101 
        key = left.key;
 110 
        key = left.key;
- 
 
 111 
        data = left.data;
102 
        left = left.left;
 112 
        left = left.left;
103 
    }
 113 
    }
104
114
105 
    // new functions from Prog. Probs PG 411
 115 
    // new functions from Prog. Probs PG 411
106 
    public int getHeight() { return height; }
 116 
    public int getHeight() { return height; }
- 
 
 117 
 
- 
 
 118 
    public int getHeight( int key ) {
- 
 
 119 
        if( this == NIL ) { return -1; }
- 
 
 120 
        if( key == this.key ) { return getHeight(); }
- 
 
 121 
        if( key < this.key ) { return left.getHeight(key); }
- 
 
 122 
        return right.getHeight(key);
- 
 
 123 
    }
107
124
108 
    public AVLTree getLeft() {
125 
    public AVLTree getLeft() {
109 
        if( this == NIL ) { return NIL; }
 126 
        if( this == NIL ) { return NIL; }
110 
        return left;
 127 
        return left;
111 
    }
 128 
    }
- 
 
 129 
 
- 
 
 130 
    public AVLTree getLeft( int key ) {
- 
 
 131 
        if( this == NIL ) { return null; } //key not in tree
- 
 
 132 
        if( key == this.key ) { return getLeft(); }
- 
 
 133 
        if( key < this.key ) { return left.getLeft(key); }
- 
 
 134 
        return right.getLeft(key);
- 
 
 135 
    }
112
136
113 
    public AVLTree getRight() {
137 
    public AVLTree getRight() {
114 
        if( this == NIL ) { return NIL; }
 138 
        if( this == NIL ) { return NIL; }
115 
        return right;
 139 
        return right;
116 
    }
 140 
    }
117
141 
 
118 
    public int getRoot() {
 142 
    public AVLTree getRight( int key ) {
- 
 
 143 
        if( this == NIL ) { return null; } //key not in tree
- 
 
 144 
        if( key == this.key ) { return getRight(); }
- 
 
 145 
        if( key < this.key ) { return left.getRight(key); }
119 
        return key;
 146 
        return right.getRight(key);
120 
    }
 147 
    }
- 
 
 148
- 
 
 149 
    public int getRoot() { return key; }
- 
 
 150 
    public int getKey() { return key; }
- 
 
 151 
    public Object getData() { return data; }
121 
 
 152 
 
122 
    public boolean contains( int x ) {
153 
    public boolean contains( int x ) {
123 
        if( this == NIL ) { return false; }
 154 
        if( this == NIL ) { return false; }
124 
        if( key == x ) { return true; }
 155 
        if( key == x ) { return true; }
125 
 
 156 
 
126 
        return left.contains(x) || right.contains(x);
 157 
        return left.contains(x) || right.contains(x);
127 
    }
 158 
    }
128
159
129 
    // am guessing this returns the tree with x == key as the root
 160 
    // I am guessing this returns the tree with x == key as the root,
- 
 
 161 
    // since the book was not very specific
130 
    public AVLTree get( int x ) {
 162 
    public Object get( int key ) {
131 
        if( this == NIL ) { return NIL; }
 163 
        if( this == NIL ) { return NIL; }
132 
        if( x == key ) { return this; }
 164 
        if( key == this.key ) { return data; }
133 
 
 165 
 
134 
        if( x < key ) { return left.get(x); }
 166 
        if( key < this.key ) { return left.get(key); }
135 
        return right.get(x);
 167 
        return right.get(key);
136 
    }
 168 
    }
137 
 
 169 
 
138 
    public boolean equals( Object object ) {
170 
    public boolean equals( Object object ) {
139 
        if( !(object instanceof AVLTree) ) { return false; }
 171 
        if( !(object instanceof AVLTree) ) { return false; }
140
172
Line 151... Line 183...
151 
        else r = right.equals(temp.right);
 183 
        else r = right.equals(temp.right);
152
184
153 
        return (temp.key == key) && l && r;
 185 
        return (temp.key == key) && l && r;
154 
    }
 186 
    }
155 
 
 187 
 
156 
    public AVLTree( int[] a ) {
188 
    public AVLTree( int[] keys, Object[] data ) {
157 
        this(a[0]); //create a new tree
 189 
        this(keys[0],data[0]); //create a new tree
158
190
159 
        //call add() for every element in the array
 191 
        //call add() for every element in the array
160 
        for( int i=1; i < a.length; i++ ) add(a[i]);
 192 
        for( int i=1; i < keys.length; i++ ) add(keys[i],data[i]);
161 
    }
 193 
    }
162 
 
 - 
 
163 
    /*
 194 
    /*
164 
    public boolean remove( int key ) {
195 
    public boolean remove( int key ) {
165 
        if( this == NIL ) { return false; }
 196 
        if( this == NIL ) { return false; }
166 
        if( key < this.key ) { return left.remove(key); }
 197 
        if( key < this.key ) { return left.remove(key); }
167 
        if( key > this.key ) { return right.remove(key); }
 198 
        if( key > this.key ) { return right.remove(key); }
168 
 
 199 
 
169 
        if( left == NIL && right == NIL ) { this = NIL; return true; }
 200 
        if( left == NIL && right == NIL ) {
- 
 
 201 
            //same as "this = NIL;"
- 
 
 202 
            setThis(NIL);
- 
 
 203
- 
 
 204 
            return true;
- 
 
 205 
        }
170 
        if( left == NIL ) {
206 
        if( left == NIL ) {
171 
            this = new AVLTree(right.key,right.left,right.right);
 207 
            //same as "this = new AVLTree(right.key,right.left,right.right);"
- 
 
 208 
            AVLTree temp = new AVLTree(right.key,right.data,right.left,right.right);
- 
 
 209 
            setThis(temp);
- 
 
 210
172 
            return true;
 211 
            return true;
173 
        }
 212 
        }
174 
        if( right == NIL ) {
 213 
        if( right == NIL ) {
175 
            this = new AVLTree(left.key,left.left,left.right);
 214 
            //same as "this = new AVLTree(left.key,left.left,left.right);"
- 
 
 215 
            AVLTree temp = new AVLTree(left.key,left.data,left.left,left.right);
- 
 
 216 
            setThis(temp);
- 
 
 217
176 
            return true;
 218 
            return true;
177 
        }
 219 
        }
- 
 
 220 
        //same as "this = new AVLTree(deleteMinimum(right));
178 
        this = new AVLTree( deleteMinimum(right) );
 221 
        AVLTree temp = new AVLTree( deleteMinimum(right) );
- 
 
 222 
        setThis(temp);
- 
 
 223
179 
        rebalance(); //fix the balance
 224 
        rebalance(); //fix the balance
180 
        return true;
 225 
        return true;
181 
    }
 226 
    }
182
227
183 
    private int deleteMinimum( AVLTree tree ) {
 228 
    private int deleteMinimum( AVLTree tree ) {
184 
        int tempKey=0;
 229 
        int tempKey=0;
185
230
186 
        if( left == NIL ) {
231 
        if( left == NIL ) {
187 
            tempKey = key;
 232 
            tempKey = key;
- 
 
 233
188 
            this = new AVLTree(right.key,right.left,right.right);
 234 
            //same as "this = new AVLTree(right.key,right.left,right.right);"
- 
 
 235 
            AVLTree temp = new AVLTree(right.key,right.data,right.left,right.right);
- 
 
 236 
            setThis(temp);
189 
        }
 237 
        }
190 
        if( left.left == NIL && left.right == NIL ) {
 238 
        if( left.left == NIL && left.right == NIL ) {
191 
            tempKey = key;
 239 
            tempKey = key;
- 
 
 240
192 
            this = new AVLTree(left.key,left.left,right.right);
 241 
            //same as "this = new AVLTree(left.key,left.left,right.right);"
- 
 
 242 
            AVLTree temp = new AVLTree(left.key,left.data,left.left,right.right);
- 
 
 243 
            setThis(temp);
193 
        }
 244 
        }
194 
        return deleteMinimum(left);
 245 
        return deleteMinimum(left);
195 
    }
 246 
    }
- 
 
 247
196 
    */
 248 
    */
- 
 
 249 
    private void setThis( AVLTree that ) {
- 
 
 250 
        this.key = that.key;
- 
 
 251 
        this.data = that.data;
- 
 
 252 
        this.height = that.height;
- 
 
 253 
        this.left = that.left;
- 
 
 254 
        this.right = that.right;
- 
 
 255 
    }
- 
 
 256 
 
- 
 
 257 
    public static void printInOrder( AVLTree tree ) {
- 
 
 258 
        Queue queue = new Queue();
- 
 
 259 
        queue.enqueue(tree);
- 
 
 260 
 
- 
 
 261 
        while( !queue.isEmpty() ) {
- 
 
 262 
            AVLTree temp = (AVLTree)queue.dequeue();
- 
 
 263 
            System.out.print(temp.getKey());
- 
 
 264 
            if( temp.getLeft() != NIL ) { queue.enqueue(temp.getLeft()); }
- 
 
 265 
            if( temp.getRight() != NIL ) { queue.enqueue(temp.getRight()); }
- 
 
 266 
        }
- 
 
 267 
    }
- 
 
 268 
 
- 
 
 269 
    public static void printPreOrder( AVLTree tree ) {
- 
 
 270 
        if( tree == NIL ) return;
- 
 
 271
- 
 
 272 
        System.out.print(tree.getKey());
- 
 
 273 
        AVLTree.printPreOrder( tree.getLeft() );
- 
 
 274 
        AVLTree.printPreOrder( tree.getRight() );
- 
 
 275 
    }
197 
 
 276 
 
198 
} //end AVLTree class
 277 
} //end AVLTree class
199 
 
 278