Subversion Repositories programming

Rev

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

Rev 44 Rev 45
Line 189... Line 189...
189 
        this(keys[0],data[0]); //create a new tree
 189 
        this(keys[0],data[0]); //create a new tree
190
190
191 
        //call add() for every element in the array
 191 
        //call add() for every element in the array
192 
        for( int i=1; i < keys.length; i++ ) add(keys[i],data[i]);
 192 
        for( int i=1; i < keys.length; i++ ) add(keys[i],data[i]);
193 
    }
 193 
    }
- 
 
 194
- 
 
 195
- 
 
 196 
    public boolean remove( int key ) {
- 
 
 197 
        if( !contains(key) ) { return false; }
- 
 
 198 
        removeHelper(this,key);
- 
 
 199 
        if( contains(key) ) { return false; }
- 
 
 200 
        return true;
- 
 
 201 
    }
- 
 
 202 
 
- 
 
 203 
    private AVLTree removeHelper( AVLTree tree, int key ) {
- 
 
 204 
        if( tree == NIL ) { return NIL; }
- 
 
 205 
        else if( key < tree.key ) { tree.left = removeHelper(tree.left,key); }
- 
 
 206 
        else if( key > tree.key ) { tree.right = removeHelper(tree.right,key); }
- 
 
 207 
        else if( tree.left != NIL && tree.right != NIL ) { tree = deleteMinimum(tree.right); }
- 
 
 208 
        else if( tree.left != NIL ) { tree = tree.left; }
- 
 
 209 
        else { tree = tree.right; }
- 
 
 210 
        tree.rebalance();
- 
 
 211 
        return tree;
- 
 
 212 
    }
- 
 
 213
- 
 
 214
194 
    /*
 215 
    /*
195 
    public boolean remove( int key ) {
216 
    public boolean remove( int key ) {
196 
        if( this == NIL ) { return false; }
 217 
        if( this == NIL ) { return false; }
197 
        if( key < this.key ) { return left.remove(key); }
 218 
        if( key < this.key ) { return left.remove(key); }
198 
        if( key > this.key ) { return right.remove(key); }
 219 
        if( key > this.key ) { return right.remove(key); }
Line 216... Line 237...
216 
            setThis(temp);
 237 
            setThis(temp);
217
238
218 
            return true;
 239 
            return true;
219 
        }
 240 
        }
220 
        //same as "this = new AVLTree(deleteMinimum(right));
 241 
        //same as "this = new AVLTree(deleteMinimum(right));
221 
        AVLTree temp = new AVLTree( deleteMinimum(right) );
 242 
        AVLTree temp = deleteMinimum(right);
222 
        setThis(temp);
 243 
        setThis(temp);
223
244
224 
        rebalance(); //fix the balance
 245 
        rebalance(); //fix the balance
225 
        return true;
 246 
        return true;
226 
    } */
 247 
    }
227
248 
    */
228 
    public void ira_dm() {
 249 
    public void ira_dm() {
229 
        System.out.println( this );
 250 
        System.out.println( this );
230 
        System.out.println( deleteMinimum( this ) );
 251 
        System.out.println( deleteMinimum(this) );
231 
    }
 252 
    }
232
253
233 
    public AVLTree deleteMinimum( AVLTree tree ) {
 254 
    private AVLTree deleteMinimum( AVLTree tree ) {
234 
        if( tree == NIL ) { return NIL; }
 255 
        if( tree == NIL ) { return NIL; }
235 
        if( tree.left == NIL && tree.right == NIL ) { return NIL; }
 256 
        if( tree.left == NIL && tree.right == NIL ) { return NIL; }
236 
        if( tree.left == NIL ) {
257 
        if( tree.left == NIL ) {
237 
            return new AVLTree(tree.right.key,tree.right.data,
 258 
            return new AVLTree(tree.right.key,tree.right.data,
238 
                               tree.right.left,tree.right.right);
259 
                               tree.right.left,tree.right.right);