This part is concerned with AVL trees. An AVL tree is a self-balancing binary search tree....

 

Transcribed Image Text:

This part is concerned with AVL trees. An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. You are not expected to complete the entire worksheet in class. Work on as many problems as you can; the remaining problems you can use for practice and to test your understanding of AVL trees. 1. (10pts) Print the tree structure of a binary tree - implement PrintTree () method. You can either print it out with the root at the topmost or with the root at the leftmost position. For the former, you need to perform a breadth-first traversal of the binary tree, for the latter a normal in order traversal will work. 2. (2pts) Use the above Java Method to show how the structure of a tree grows as you insert new values into a binary search tree. 3. (10pts) Implement a recursive Java Method TreeHeight () for finding the height of a binary search tree. The height of a binary search tree is the length of the longest path from the root to a leaf. Hint: Modify your Java Method Print Tree () to determine the height of each node's left and right subtree. (10pts) 4. (20pts) The balance factor of a node is the height of its left subtree minus the height of its right subtree, and a node with balance factor 1, 0, or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees. Write a Java Method that computes the balance factor for each subtrees and prints it out along with the tree structure. 5. (5pts) Write a Java Method which checks whether a tree is an AVL tree. 6. (30pts): Write a Java Method to implement insertion of a node with tree rebalancing. After inserting a node, it is necessary to check each of the node's ancestors for consistency with the rules of AVL. For each node checked, if the balance factor remains -1, 0, or 1 then no rotations are necessary. However, if the balance factor becomes 2 or -2 then the subtree rooted at this node is unbalanced. If insertions are performed serially, after each insertion, at most two tree rotations are needed to restore the entire tree to the rules of AVL. There are four cases which need to be considered, of which two are symmetric to the other two. Let P be the root of the unbalanced subtree. Let R be the right child of P. Let L be the left child of P. Right-Right case and Right-Left case: If the balance factor of P is -2, then the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (R) must be checked. If the balance factor of R is -1, a left rotation is needed with P as the root. If the balance factor of R is +1, a double left rotation is needed. The first rotation is a right rotation with R as the root. The second is a left rotation with P as the root. Bonus 7. Write a Java Method to implement deletion of a node with tree rebalancing. The node is a leaf, remove it. If the node is not a leaf, replace it with either the largest in its left subtree (inorder predecessor) or the smallest in its right subtree (inorder successor), and remove that node. The node that was found as replacement has at most one subtree. After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed. As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above. 6 7 9 In addition to the balancing described above for insertions, if the balance factor for the tree is 2 and that of the right subtree is 0, a left rotation must be performed on P. The mirror of this case is also necessary. The retracing can stop if the balance factor becomes -1 or 1 indicating that the height of that subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. If the balance factor becomes -2 or 2 then the subtree is unbalanced and needs to be rotated to fix it. If the rotation leaves the subtree's balance factor at 0 then the retracing towards the root must continue since the height of this subtree has decreased by one. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged. Part 2 - Maps Using Map data structure, define a method letterFrequencie(), that takes a string as a parameter an outputs the frequencies of the letters in that string (note that you string must contains at least 20 distinct letters) (7pts). Using Map data structure, define a method word Frequencie(), that takes a string as a parameter an outputs the frequencies of the words in that string (note that you string must contains at least 20 distinct words) (6pts). Sorting a map on the keys is another frequent operation. Sort the generated maps above based on their keys (5pts). Sorting a map on the values is another frequent operation. Sort the generated maps above based on their values (5pts). This part is concerned with AVL trees. An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. You are not expected to complete the entire worksheet in class. Work on as many problems as you can; the remaining problems you can use for practice and to test your understanding of AVL trees. 1. (10pts) Print the tree structure of a binary tree - implement PrintTree () method. You can either print it out with the root at the topmost or with the root at the leftmost position. For the former, you need to perform a breadth-first traversal of the binary tree, for the latter a normal in order traversal will work. 2. (2pts) Use the above Java Method to show how the structure of a tree grows as you insert new values into a binary search tree. 3. (10pts) Implement a recursive Java Method TreeHeight () for finding the height of a binary search tree. The height of a binary search tree is the length of the longest path from the root to a leaf. Hint: Modify your Java Method Print Tree () to determine the height of each node's left and right subtree. (10pts) 4. (20pts) The balance factor of a node is the height of its left subtree minus the height of its right subtree, and a node with balance factor 1, 0, or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees. Write a Java Method that computes the balance factor for each subtrees and prints it out along with the tree structure. 5. (5pts) Write a Java Method which checks whether a tree is an AVL tree. 6. (30pts): Write a Java Method to implement insertion of a node with tree rebalancing. After inserting a node, it is necessary to check each of the node's ancestors for consistency with the rules of AVL. For each node checked, if the balance factor remains -1, 0, or 1 then no rotations are necessary. However, if the balance factor becomes 2 or -2 then the subtree rooted at this node is unbalanced. If insertions are performed serially, after each insertion, at most two tree rotations are needed to restore the entire tree to the rules of AVL. There are four cases which need to be considered, of which two are symmetric to the other two. Let P be the root of the unbalanced subtree. Let R be the right child of P. Let L be the left child of P. Right-Right case and Right-Left case: If the balance factor of P is -2, then the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (R) must be checked. If the balance factor of R is -1, a left rotation is needed with P as the root. If the balance factor of R is +1, a double left rotation is needed. The first rotation is a right rotation with R as the root. The second is a left rotation with P as the root. Bonus 7. Write a Java Method to implement deletion of a node with tree rebalancing. The node is a leaf, remove it. If the node is not a leaf, replace it with either the largest in its left subtree (inorder predecessor) or the smallest in its right subtree (inorder successor), and remove that node. The node that was found as replacement has at most one subtree. After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed. As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above. 6 7 9 In addition to the balancing described above for insertions, if the balance factor for the tree is 2 and that of the right subtree is 0, a left rotation must be performed on P. The mirror of this case is also necessary. The retracing can stop if the balance factor becomes -1 or 1 indicating that the height of that subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. If the balance factor becomes -2 or 2 then the subtree is unbalanced and needs to be rotated to fix it. If the rotation leaves the subtree's balance factor at 0 then the retracing towards the root must continue since the height of this subtree has decreased by one. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged. Part 2 - Maps Using Map data structure, define a method letterFrequencie(), that takes a string as a parameter an outputs the frequencies of the letters in that string (note that you string must contains at least 20 distinct letters) (7pts). Using Map data structure, define a method word Frequencie(), that takes a string as a parameter an outputs the frequencies of the words in that string (note that you string must contains at least 20 distinct words) (6pts). Sorting a map on the keys is another frequent operation. Sort the generated maps above based on their keys (5pts). Sorting a map on the values is another frequent operation. Sort the generated maps above based on their values (5pts).

Answer rating: 100% (QA)

import classes and packages import javautilScanner create Node class to design the structure of the AVL Tree Node class Node int key int h for height Node leftChild Node rightChild default constructor ... View the full answer