Subversion Repositories programming

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
41 irasnyd 1 
// Written by Ira Snyder
2 
// Due Date: 11-24-2004
3 
// Project #4
4 
 
5 
import java.io.*;
6 
import java.util.*;
7 
 
8 
class AVLTree {
9 
    private int key, height;
10 
    private AVLTree left, right;
11 
 
12 
    public static final AVLTree NIL = new AVLTree();
13 
 
14 
    public AVLTree( int key ) {
15 
        this.key = key;
16 
        left = right = NIL;
17 
    }
18 
 
19 
    public boolean add( int key ) {
20 
        int oldSize = size();
21 
        grow(key);
22 
        return size() > oldSize;
23 
    }
24 
 
25 
    public AVLTree grow( int key ) {
26 
        if( this == NIL ) return new AVLTree(key);
27 
        if( key == this.key ) return this; //prevent key dupes
28 
        if( key < this.key ) left = left.grow(key);
29 
        else right = right.grow(key);
30 
 
31 
        rebalance();
32 
 
33 
        height = 1 + Math.max(left.height,right.height);
34 
        return this;
35 
    }
36 
 
37 
    public int size() {
38 
        if( this == NIL ) return 0;
39 
        return 1 + left.size() + right.size();
40 
    }
41 
 
42 
    public String toString() {
43 
        if( this == NIL ) return "";
44 
        return left + " " + key + " " + right;
45 
    }
46 
 
47 
    private AVLTree() { //construct the empty tree
48 
        left = right = this;
49 
        height = -1;
50 
    }
51 
 
52 
    private AVLTree( int key, AVLTree left, AVLTree right ) {
53 
        this.key = key;
54 
        this.left = left;
55 
        this.right = right;
56 
        height = 1 + Math.max(left.height,right.height);
57 
    }
58 
 
59 
    private void rebalance() {
60 
        if( right.height > (left.height + 1) ) {
61 
            if( right.left.height > right.right.height ) right.rotateRight();
62 
            rotateLeft();
63 
        }
64 
        else if( left.height > (right.height + 1) ) {
65 
            if( left.right.height > left.left.height ) left.rotateLeft();
66 
            rotateRight();
67 
        }
68 
    }
69 
 
70 
    private void rotateLeft() {
71 
        left = new AVLTree(key,left,right.left);
72 
        key = right.key;
73 
        right = right.right;
74 
    }
75 
 
76 
    private void rotateRight() {
77 
        right = new AVLTree(key,left.right,right);
78 
        key = left.key;
79 
        left = left.left;
80 
    }
81 
 
82 
} //end AVLTree class
83