LAB#08 : AVL-Trees

---

Objectives:

1.       Implementing the rotateLeft( ) method of AVLTree class.

2.       Comparison of BSTs and AVL trees when inserting data that is sorted.

3.       Implementing a cross-reference generator using an AVL tree.

1.  Downloadables:

Download lab08.zip.

     After unzipping, the following files will be added in the ics202 package:

             AVLTree.java

     The following files will be placed in a package ics202.lab08:

             AVLTreeTest.java

             CrossReferenceBuilder.java

             BinarySearchTreeTest2.java

             MyAssociation.java

            input.txt

2. Task1

Study each of the files: AVLTree.java, MyAssociation.java, input.txt.

The class MyAssociation will be used in Task5 to create an AVL tree in which each node is an association between a distinct word in a text-file and an object that stores the frequency of that word in the text-file and all the line numbers in the text-file in which that word appears.

3. Task2

Implement the method rotateLeft( )  in AVLTree.java.

Note: The remaining tasks in this lab-work require the implementation of this method.

4. Task3

(a)    Using AVLTreeTest.java, create an AVL tree in which the following keys are inserted in the given order:

 8, 12, 14, 18, 20, 23

(b)    Draw the resulting AVL tree. Verify your result from the output of part (a).

(c)    Using the program BinarySearchTreeTest2.java, create a BST in which the keys in (a) are inserted in the same order.

(d)    Draw the resulting BST. Verify your result from the output of part (c).

(e)    Repeat (a) and (c) by inserting keys in the following order: 10, 5, 20, 3, 7, 15, 30. What do you notice?

(f)     From the results in (a) and (c), which is a better search-tree data structure, an AVL tree or an ordinary BST? Why?

5.  Task4

(i)   Verify all the insertion cases given in lecture#23 (“Insertion and Deletion in AVL-Trees”) from page#3 to page#7. For each case,

       insert the keys in the given order:

(a)     Page#3: Insertion case 1: “Insertion that does not cause an imbalance in the AVL tree”

13, 10, 15, 5, 11, 16, 4, 6, 14

(b)    Page#4: Insertion case 2a: “Insertion that requires a single right rotation to rebalance the AVL tree”

13, 10, 15, 5, 11, 16, 4, 8, 3

(c)   Page#5: Insertion case 2b: “Insertion that requires a single left rotation to rebalance the AVL tree”

30, 5, 35, 32, 40, 45

(d)    Page#6: Insertion case 3a: “Insertion that requires a double left-right rotation to rebalance the AVL tree”

13, 10, 15, 5, 11, 16, 4, 6, 7

(e)    Page#7: Insertion case 3b: “Insertion that requires a double right-left rotation to rebalance the AVL tree”

5, 2, 7, 1, 4, 6, 9, 3, 16, 15

(ii) Verify that if you insert the following key sequence: 45, 50, 78, 40, 35, 43, 70 in an originally empty AVL-tree you will get the

      following sequence of rotations: Single Left, Single Right, Double Left-Right, Double Right-Left.

6. Task5

Comment the println statements in rotateLeft( ), rotateRight( ) and balance( ) methods.

Complete the choices in CrossReference.java as follows:

(a)       Choice#1: As the program reads a text-file it inserts MyAssociation objects in an AVL-tree. After the text-file has been read, each association object contains a distinct word from the text-file, together with the frequency of that word and all the distinct line numbers in which it appears.

(b)       Choice#2: The program displays the created cross-reference (i.e., the AVL-tree that has been built in (a)) in increasing order of keys. For example the given input.txt results in the following output:

(c)       Choice#3: The program prompts for and reads a word to be searched in the AVL-tree created in (a). If the word is found, the corresponding AVL-node is displayed; otherwise the message: THE WORD IS NOT FOUND is displayed.