Embedded Files
Post date: Mar 10, 2019 5:24:25 AM
Chapter 6 Binary Trees:
Tree Traversal,
Insertion,
Deletion
Lab 8 – AVL Tree
Objectives:
Learn How to Implement and Use AVL Tree
Examples:
The given java file, AVLTree.java implements a generic AVLTree class with AVLNode as an inner class. Most of the operations are copied with minor changes from BST. The Major changes are:
AVLNode now has an additional variable, height
The insert() method has been updated to ensure balance after each insertion.
Rotation methods are added to support the insert() method.
The class, TestIntegerAVL shows how to use methods of AVLTree.
The Word class represents a word and its count. It is needed to solve task 2(b).
Tasks:
1. (a) For each of the following, insert the given sequence of numbers manually into an initially empty AVL tree. Show all rotations involved by drawing a separate tree after each rotation. Note: For double rotation, you must show the result of each.
i). 8, 12, 14, 18, 20, 23
ii). 5, 15, 18, 4, 3, 1, 9, 7, 12
iii). 2, 1, 4, 5, 9, 3, 6
iv). 10, 15, 19, 5, 8, 2, 25, 31, 20
(b) Run the program, TestIntegerAVL to verify your manual result.
2. (a) The text file, AboutJUC.txt contains basic information about JUC (culled from the college website). Write a program, PrintWords.java, that uses AVLTree to print the words in this file sorted in alphabetical order.
Hint: You need to read the content of the file word-by-word and for each word encountered, insert it into an AVLTree of Strings. After all data is entered, traverse the tree using inorder() method.
(b) Your program in (a) above would have automatically discarded all duplicates of words since duplicates are not accepted in BST/AVL trees. Write another program, PrintWordCounts.java, that prints each word in the input file along with its count.
Hint::For each word encountered, use it to create a Word object named target
Search for target in the tree. If found, increment the count of the result else, insert target in the tree.
At the end, traverse the tree using inorder() method.
(c) Update PrintWordsCount to print not only the count of each word but also the line numbers where the word occurred in the text file. See sample output below:
Hint:Update the Word class as follows:
l Add a LinkedList instance variable, lines, to store line numbers as each word is encountered.
l Update the Constructor to receive not only a word but also the initial line number
l Update the toString() method to also return the lines variable.
l Update the compareTo() method to ignore the case of the words being compared.
Update the PrintWordsCount as follows:
l Do not read the file word by word. Instead, read the file line-by-line and use a variable to track the line number of each line read.
l Use the method of the String class, String[] split(String regex), to split each line read into an array of words. You need to pass the same delimiters string as with useDelimeter() method.
l For each word in the array returned by the split() method, use it along with the current line number to create a Word object and search for it in the array. If the target is not found, insert it in the tree, else update both the count and add the current line number.
Page updated
Google Sites
Report abuse