The kth smallest element You can find the kth smallest eleme

(The kth smallest element) You can find the kth smallest element in a BST in O(n) time from an inorder iterator. For an AVL tree, you can find it in O(log n)time. To achieve this, add a new data field named size in AVLTreeNode to store the number of nodes in the subtree rooted at this node. Note that the size of a node v is one more than the sum of the sizes of its two children.

Figure 26.12 shows an AVL tree and the size value for each node in the tree

#5 in Chapter 25 of Intro to Java Programming - Liang

25) size: 6 20 size:2 34) size: 3 5 size:1 0 size:1 50size: 1 FIGURE 26.12 The size data field in AVLTreeNode stores the number of nodes in the sub- tree rooted at the node. In the AVLTree class, add the following method to return the kth smallest ele- ment in the tree. public E find(int k) The method returns null if k the size of the tree. This method can be implemented using the recursive method find(k, root), which returns the kth smallest element in the tree with the specified root. Let A and B be the left and right children of the root, respectively. Assuming that the tree is not empty and k s root.size, find(k, root) can be recursively defined as follows: root.element, ifA is null and k is 1; B.element, ifA is null and k is 2; find(k. A), if k A.size find(k, root) = 1; Modify the insert and delete methods in AVLTree to set the correct value for the size property in each node. The insert and delete methods will still be in O(log n) time. The find(k) method can be implemented in O(log n) time. Therefore, you can find the kth smallest element in an AVL tree in O(log n) time. Use the following main method to test your program: import java.util.Scanner public class Exercise26_05 i public static void main(String[] args) AVLTree«Double> tree = new AVLT ree(); Scanner input = new Scanner(System.in); System.out.print(\"Enter 15 numbers:\"); for (int i =0; i

Solution

public E find(int k) { Node nodeone = Root; int count = k; // assigning k to the count and search it in the list int sizeOfLeftSubtree = 0; while(nodeone!= null) { sizeOfLeftSubtree = nodeone.SizeOfLeftSubtree(); if (sizeOfLeftSubtree + 1 == count) return nodeone.Value; // if it is found in the left subtree else if (sizeOfLeftSubtree < count) { nodeone = nodeone.Right; count -= sizeOfLeftSubtree+1; // if element is found in right subtree } else { nodeone = nodeone.Left; } } return -1; // return -1 if the element is not found }