Subversion Repositories programming

Rev

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

Rev 41 Rev 42
Line 37... Line 37...
37 
    public int size() {
 37 
    public int size() {
38 
        if( this == NIL ) return 0;
 38 
        if( this == NIL ) return 0;
39 
        return 1 + left.size() + right.size();
 39 
        return 1 + left.size() + right.size();
40 
    }
 40 
    }
41 
 
 41 
 
- 
 
 42 
    //I like the BinaryTree toString better than the author's toString()
- 
 
 43 
    //so I used it here instead. I left the author's code for completeness.
- 
 
 44 
    /*
42 
    public String toString() {
 45 
    public String toString() {
43 
        if( this == NIL ) return "";
 46 
        if( this == NIL ) return "";
44 
        return left + " " + key + " " + right;
 47 
        return left + " " + key + " " + right;
45 
    }
 48 
    }
- 
 
 49 
    */
- 
 
 50
- 
 
 51 
    public String toString() {
- 
 
 52
- 
 
 53 
        if( this == NIL ) return "()";
- 
 
 54
- 
 
 55 
        String sLeft = sLeft = left.toString();
- 
 
 56 
        String sRight = sRight = right.toString();
- 
 
 57 
        String answer = new String();
- 
 
 58
- 
 
 59 
        //assemble the string to return
- 
 
 60 
        answer = "(";
- 
 
 61 
        if( !sLeft.equals("()") ) { answer += sLeft + ","; }
- 
 
 62 
        answer += key;
- 
 
 63 
        if( !sRight.equals("()") ) { answer += "," + sRight; }
- 
 
 64 
        answer += ")";
- 
 
 65
- 
 
 66 
        //return the assembled string
- 
 
 67 
        return answer;
- 
 
 68 
    }
46 
 
 69
47 
    private AVLTree() { //construct the empty tree
 70 
    private AVLTree() { //construct the empty tree
48 
        left = right = this;
 71 
        left = right = this;
49 
        height = -1;
 72 
        height = -1;
50 
    }
 73 
    }
51 
 
 74 
 
Line 77... Line 100...
77 
        right = new AVLTree(key,left.right,right);
 100 
        right = new AVLTree(key,left.right,right);
78 
        key = left.key;
 101 
        key = left.key;
79 
        left = left.left;
 102 
        left = left.left;
80 
    }
 103 
    }
81
104
- 
 
 105 
    // new functions from Prog. Probs PG 411
- 
 
 106 
    public int getHeight() { return height; }
- 
 
 107
- 
 
 108 
    public AVLTree getLeft() {
- 
 
 109 
        if( this == NIL ) { return NIL; }
- 
 
 110 
        return left;
- 
 
 111 
    }
- 
 
 112
- 
 
 113 
    public AVLTree getRight() {
- 
 
 114 
        if( this == NIL ) { return NIL; }
- 
 
 115 
        return right;
- 
 
 116 
    }
- 
 
 117
- 
 
 118 
    public int getRoot() {
- 
 
 119 
        return key;
- 
 
 120 
    }
- 
 
 121 
 
- 
 
 122 
    public boolean contains( int x ) {
- 
 
 123 
        if( this == NIL ) { return false; }
- 
 
 124 
        if( key == x ) { return true; }
- 
 
 125 
 
- 
 
 126 
        return left.contains(x) || right.contains(x);
- 
 
 127 
    }
- 
 
 128
- 
 
 129 
    // am guessing this returns the tree with x == key as the root
- 
 
 130 
    public AVLTree get( int x ) {
- 
 
 131 
        if( this == NIL ) { return NIL; }
- 
 
 132 
        if( x == key ) { return this; }
- 
 
 133 
 
- 
 
 134 
        if( x < key ) { return left.get(x); }
- 
 
 135 
        return right.get(x);
- 
 
 136 
    }
- 
 
 137 
 
- 
 
 138 
    public boolean equals( Object object ) {
- 
 
 139 
        if( !(object instanceof AVLTree) ) { return false; }
- 
 
 140
- 
 
 141 
        AVLTree temp = (AVLTree)object; //make it typed
- 
 
 142
- 
 
 143 
        boolean l=false, r=false;
- 
 
 144
- 
 
 145 
        //check the left
- 
 
 146 
        if( left == NIL && temp.left == NIL ) l = true;
- 
 
 147 
        else l = left.equals(temp.left);
- 
 
 148
- 
 
 149 
        //check the right
- 
 
 150 
        if( right == NIL && temp.right == NIL ) r = true;
- 
 
 151 
        else r = right.equals(temp.right);
- 
 
 152
- 
 
 153 
        return (temp.key == key) && l && r;
- 
 
 154 
    }
- 
 
 155 
 
- 
 
 156 
    public AVLTree( int[] a ) {
- 
 
 157 
        this(a[0]); //create a new tree
- 
 
 158
- 
 
 159 
        //call add() for every element in the array
- 
 
 160 
        for( int i=1; i < a.length; i++ ) add(a[i]);
- 
 
 161 
    }
- 
 
 162 
 
- 
 
 163 
    /*
- 
 
 164 
    public boolean remove( int key ) {
- 
 
 165 
        if( this == NIL ) { return false; }
- 
 
 166 
        if( key < this.key ) { return left.remove(key); }
- 
 
 167 
        if( key > this.key ) { return right.remove(key); }
- 
 
 168 
 
- 
 
 169 
        if( left == NIL && right == NIL ) { this = NIL; return true; }
- 
 
 170 
        if( left == NIL ) {
- 
 
 171 
            this = new AVLTree(right.key,right.left,right.right);
- 
 
 172 
            return true;
- 
 
 173 
        }
- 
 
 174 
        if( right == NIL ) {
- 
 
 175 
            this = new AVLTree(left.key,left.left,left.right);
- 
 
 176 
            return true;
- 
 
 177 
        }
- 
 
 178 
        this = new AVLTree( deleteMinimum(right) );
- 
 
 179 
        rebalance(); //fix the balance
- 
 
 180 
        return true;
- 
 
 181 
    }
- 
 
 182
- 
 
 183 
    private int deleteMinimum( AVLTree tree ) {
- 
 
 184 
        int tempKey=0;
- 
 
 185
- 
 
 186 
        if( left == NIL ) {
- 
 
 187 
            tempKey = key;
- 
 
 188 
            this = new AVLTree(right.key,right.left,right.right);
- 
 
 189 
        }
- 
 
 190 
        if( left.left == NIL && left.right == NIL ) {
- 
 
 191 
            tempKey = key;
- 
 
 192 
            this = new AVLTree(left.key,left.left,right.right);
- 
 
 193 
        }
- 
 
 194 
        return deleteMinimum(left);
- 
 
 195 
    }
- 
 
 196 
    */
- 
 
 197 
 
82 
} //end AVLTree class
 198 
} //end AVLTree class
83 
 
 199