CS 151 -- Lab 10

The last lab

AVL trees

Today in class we discussed the AVL algorithm. In lab, you will implement the record-keeping part of AVL. We discussed this in psuedocode in class. Here you will write java code.

The only code you should write the following:

Keeping track of the AVL level of nodes during insertion
Print a message to indicate that the tree is out of balance.
Optional: Describe the necessary rotation(s)

Code is available at

    https://cs.brynmawr.edu/cs151/Data/Lab10/LinkedBinaryTree.java
    https://cs.brynmawr.edu/cs151/Data/Lab10/TreeInterface.java

or via scp at

    /home/gtowell/Public/151/Data/Lab10/LinkedBinaryTree.java
    /home/gtowell/Public/151/Data/Lab10/TreeInterface.java

For example: if this is the code in my main method:

        public static void main(String[] args) {
            LinkedBinaryTree ts = new LinkedBinaryTree<>();
            ts.insert(0);
            System.out.println(ts.toString());
            ts.insert(2);
            System.out.println(ts.toString());
            ts.insert(4);
            System.out.println(ts.toString());
            ts.insert(-1);
            System.out.println(ts.toString());
            ts.insert(-2);
            System.out.println(ts.toString());
            ts.insert(-3);
            System.out.println(ts.toString());
        }

then this is the output of my program

        <0: 0 avl:1> 
        <0: 0 avl:2> <1: 2 avl:1> 
        Out of balance in subtree rooted at 0 avl:3
               Right side to deep
        <0: 0 avl:3> <1: 2 avl:2> <2: 4 avl:1> 
        <1: -1 avl:1> <0: 0 avl:3> <1: 2 avl:2> <2: 4 avl:1> 
        <2: -2 avl:1> <1: -1 avl:2> <0: 0 avl:3> <1: 2 avl:2> <2: 4 avl:1> 
        Out of balance in subtree rooted at -1 avl:3
               Left side to deep
        <3: -3 avl:1> <2: -2 avl:2> <1: -1 avl:3> <0: 0 avl:4> <1: 2 avl:2> <2: 4 avl:1>

What to turn in

Send email to gtowell@brynmawr.edu with your changes to LinkedBinaryTree or just the entire LinkedBinaryTree.java file.