Pls use AVL tree and answer 2 and 3. thx.

AVL tree code:

public class AVLNode{ int key; int height; int size; AVLNode left; AVLNode right; //Constructor public AVLNode(int k){ size=0; key=k; height=0; left=null; right=null; } }

------------------------------------

import java.util.*; import java.lang.Math; import java.io.*; import java.lang.Integer; public class AVLTree{ AVLNode root; //constructor public AVLTree(){ root=null; } //helper function public void insert(int k){ AVLNode newnode = new AVLNode(k); // make new node if (root==null){ root=newnode; } else { root=AVLinsert(newnode,root); } } public int subtreeSize(AVLNode N){ if(){ } return N.size; } //AVLinsert is a recursive function public AVLNode AVLinsert(AVLNode newnode, AVLNode parent){ AVLNode temp=parent; if (newnode.keyparent.key){ if(parent.right==null){ parent.right=newnode; } else{ parent.right=AVLinsert(newnode, parent.right); if (Height(parent.left)-Height(parent.right)==-2){ if (newnode.key>parent.right.key){ temp=leftrotation(parent); //apply left rotation } else { temp=rightleftrotation(parent); //apply rightleft rotation } } } } else{ System.out.println("Duplicate Keys"); } updateHeight(parent); return temp; } public void updateHeight(AVLNode x){ if(x.left==null && x.right==null) x.height=0; else if (x.left==null && x.right!=null) x.height=x.right.height+1; else if (x.left!=null & x.right==null) x.height=x.left.height+1; else x.height=Math.max(x.left.height,x.right.height)+1; } public AVLNode rightrotation(AVLNode parent){ //right rotation for LL Case AVLNode temp=parent.left; parent.left=temp.right; temp.right=parent; parent.height=Math.max(Height(parent.left),Height(parent.right))+1; // update the height after rotation temp.height=Math.max(Height(temp.left),Height(temp.right))+1; //update the height after rotation return temp; } public AVLNode leftrotation(AVLNode parent){ //left rotation for RR Case AVLNode temp=parent.right; parent.right=temp.left; temp.left=parent; parent.height=Math.max(Height(parent.left),Height(parent.right))+1; // update the height after rotation temp.height=Math.max(Height(temp.left),Height(temp.right))+1; //update the height after rotation return temp; } public AVLNode leftrightrotation(AVLNode parent){ //leftright rotation for RL Case parent.left=leftrotation(parent.left); AVLNode temp=rightrotation(parent); return temp; } public AVLNode rightleftrotation(AVLNode parent){ //rightleft rotation for LR Case parent.right=rightrotation(parent.right); AVLNode temp=leftrotation(parent); return temp; } public int Height(AVLNode x){ // return height of tree rooted at x if (x == null){ // If node is null take height= -1 return -1;} else { return x.height;} } public boolean empty(){ //test if the tree is empty if (root==null){ return true;} return false; } public void printLevelOrder(){ //print the in level order int h=root.height; for (int i=0; i0){ printLevel(root.left, level-1); printLevel(root.right, level-1); } } public void preorder(AVLNode root){ if (root==null){ return;} else{ System.out.print(root.key+" "); preorder(root.left); preorder(root.right); } } public void inorder(AVLNode root){ if (root==null){ return;} else{ inorder(root.left); System.out.print(root.key+" "); inorder(root.right); } } public void postorder(AVLNode root){ if (root==null){ return;} else{ postorder(root.left); postorder(root.right); System.out.print(root.key+" "); } } p public static void main(String[] args){ AVLTree T=new AVLTree(); T.insert(5); T.insert(4); /*T.insert(3); T.insert(6); T.insert(7); T.insert(2); T.insert(1); */ T.printLevelOrder(); System.out.println(" "); System.out.print("Preorder Traversal :"); T.preorder(T.root); System.out.println(" "); System.out.print("Inorder Traversal :"); T.inorder(T.root); System.out.println(" "); System.out.print("Postorder Traversal:"); T.postorder(T.root); System.out.println(" "); System.out.println(subtreeSize(T.root)); } }

Consider the following abstract data type that supports the 1. insert(int k): Insert a key k into the data structure only if it is not 2. search next(int k): Find the smallest key in the data structure that is 3. search smallest(int k): Find the kth smallest key in the data structure. All operations are operations are done in O(log(n) where n is the Implement the above ADT in java. Which data structure we saw in class is following operations already in the ADT. greater than k. For example search smallest (0) wil return the smallest key in the ADT number of keys in the data structure. most appropriate to implement this ADT? You are allowed to use any java code you have been provided. You can assume the keys are of type int