26.5 (The kth smallest element) You can find the kth smallest element in a BST in On) time from an inonder iterator. For an AVL tree, you can find it in Olog n) time, To achieve this, add a new data field named size in AVLTreeNode to store the number of nodes in the suhtree 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. 25) sine 6 20) size: 2 34 )sine: 3 5 ) sine: 1 30) sine: 1 Ssine: 1 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 1 or 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, findCk, root) can be recursively defined as follows: root element, if A is null and k is Belement, if A is nall and k is 2 findk, root)findkA). ifkAsize. root.element, ifk-Asize1 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 findCk) method can be implemented in Ollog n time. Therefore, you can find the kth smallest element in an AVL tree in Ollog n) time Use the following main method to test your program: import java.util.Scanner public class Exercise26 05 public static void main(String[] args) f AVLTreecDouble> tree new AVLTreeo O: Scanner input new Scanner(System.in): System.out.print("Enter 15 numbers:: for (int i . 0; i 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, findCk, root) can be recursively defined as follows: root element, if A is null and k is Belement, if A is nall and k is 2 findk, root)findkA). ifkAsize. root.element, ifk-Asize1 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 findCk) method can be implemented in Ollog n time. Therefore, you can find the kth smallest element in an AVL tree in Ollog n) time Use the following main method to test your program: import java.util.Scanner public class Exercise26 05 public static void main(String[] args) f AVLTreecDouble> tree new AVLTreeo O: Scanner input new Scanner(System.in): System.out.print("Enter 15 numbers:: for (int i . 0; i
