Subversion Repositories programming

Rev

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

Rev 47 Rev 48
Line 43... Line 43...
43 
        //prevent key dupes, update data
 43 
        //prevent key dupes, update data
44 
        if( key == this.key ) { this.data = data; return this; }
44 
        if( key == this.key ) { this.data = data; return this; }
45 
        if( key < this.key ) left = left.grow(key,data);
 45 
        if( key < this.key ) left = left.grow(key,data);
46 
        else right = right.grow(key,data);
 46 
        else right = right.grow(key,data);
47 
 
 47 
 
48 
        rebalance(); //fix the balance as we recurse back up
 - 
 
49 
 
 - 
 
50 
        height = 1 + Math.max(left.height,right.height);
 48 
        height = 1 + Math.max(left.height,right.height);
51 
        return this;
 49 
        return this;
52 
    }
 50 
    }
53
51
54 
    //method to return the size of the tree
 52 
    //method to return the size of the tree
Line 100... Line 98...
100 
        this.left = left;
 98 
        this.left = left;
101 
        this.right = right;
 99 
        this.right = right;
102 
        height = 1 + Math.max(left.height,right.height);
 100 
        height = 1 + Math.max(left.height,right.height);
103 
    }
 101 
    }
104
102
105 
    //method to rebalance the tree if it is out of balance, using rotations
 - 
 
106 
    private void rebalance() {
 - 
 
107 
        if( right.height > (left.height + 1) ) {
 - 
 
108 
            if( right.left.height > right.right.height ) right.rotateRight();
 - 
 
109 
            rotateLeft();
 - 
 
110 
        }
 - 
 
111 
        else if( left.height > (right.height + 1) ) {
 - 
 
112 
            if( left.right.height > left.left.height ) left.rotateLeft();
 - 
 
113 
            rotateRight();
 - 
 
114 
        }
 - 
 
115 
    }
 - 
 
116
- 
 
117 
    //method to rotate the tree to the left
 - 
 
118 
    private void rotateLeft() {
 - 
 
119 
        left = new BSTree(key,data,left,right.left);
 - 
 
120 
        key = right.key;
 - 
 
121 
        data = right.data;
 - 
 
122 
        right = right.right;
 - 
 
123 
    }
 - 
 
124 
 
 - 
 
125 
    //method to rotate the tree to the right
 - 
 
126 
    private void rotateRight() {
 - 
 
127 
        right = new BSTree(key,data,left.right,right);
 - 
 
128 
        key = left.key;
 - 
 
129 
        data = left.data;
 - 
 
130 
        left = left.left;
 - 
 
131 
    }
 - 
 
132
- 
 
133 
    //method to return the height of the tree
 103 
    //method to return the height of the tree
134 
    public int getHeight() { return height; }
 104 
    public int getHeight() { return height; }
135 
 
 105 
 
136 
    //method to return the height of the subtree with the
 106 
    //method to return the height of the subtree with the
137 
    //given key
 107 
    //given key
Line 249... Line 219...
249 
            tree = deleteMinimum(tree.right);
219 
            tree = deleteMinimum(tree.right);
250 
        }
 220 
        }
251 
        else if( tree.left != NIL ) { tree = tree.left; }
 221 
        else if( tree.left != NIL ) { tree = tree.left; }
252 
        else { tree = tree.right; }
 222 
        else { tree = tree.right; }
253
223
254 
        tree.rebalance(); //rebalance as we recurse back up
 - 
 
255 
        return tree;
 224 
        return tree;
256 
    }
 225 
    }
257
226
258 
    //method to remove the minimum element in a tree
 227 
    //method to remove the minimum element in a tree
259 
    private BSTree deleteMinimum( BSTree tree ) {
 228 
    private BSTree deleteMinimum( BSTree tree ) {