For java
What you need to do: These files are provided for you, you need to download them and work on them: TreeNode.java AVLTree.java Test.java The basic skeleton of the program is provided for you. You only need to fill in the blanks. You can find the skeleton of class AVL Tree in the file provided. You need to complete the methods in this file, which are briefly explained in the table below. The file TreeNode contains the class of the nodes that you will use for the AVL tree and it is already provided for you. The file Test contains the class that will test your code and it is already provided for you you don't need to change. A sample output is shown at the end. Methods of AVLTree class: These are the methods that you need to change: Method Discerption private TreeNode This method searches the tree and tries to search(int key, TreeNode find the node with the given key. If the key subRoot) is not found it should return null, otherwise it should return the node that has the key. private boolean insert(int This method does the insertion work but key, TreeNode subRoot, should make sure that the tree is a valid TreeNode prev) AVL tree after the insertion. Hence, this method may call the balance Tree method. The Boolean value returned by this method is used to indicate whether the height of the subtree rooted at subRoot has changed or not. private boolean delete(int This method does the deletion work and key, TreeNode subRoot, also make sure the tree is a valid AVL tree TreeNode prev, TreeNode after the deletion. Hence, this method may data) call the balanceTree method. The deleted node should be placed in the data parameter passed. If the key is not found, this data parameter should not change. The Boolean value returned by this method is used to indicate whether the height of the subtree rooted at subRoot has changed or not. private void This method is used to check if the balanceTree(TreeNode subRoot node is left imbalanced subRoot, TreeNode prev) (balFactor == 2) or right imbalanced (balFactor == -2). Then, it should call the appropriate rotation methods to re- balance the tree. private void This method replaces subRoot with its rotateLeft(TreeNode right child and makes the subRoot the left subRoot, TreeNode prev) child of the child that replaced it. private void This method replaces subRoot with its left rotate Right(TreeNode child and makes the subRoot the right subRoot, TreeNode prev) child of the child that replaced it. private void This method calls rotateRight with rotate RightLeft(TreeNode subRoot's right child. Then, it calls subRoot, TreeNode prev) rotateLeft on the subRoot itself. private void This method calls rotateLeft with rotate LeftRight(TreeNode subRoot's left child. Then, it calls subRoot, TreeNode prev) rotateRight on the subRoot itself. These are the methods that you must not change: Method Description public TreeNode This method is the interface for the user. It search(int key) just calls the private search method with the key and the root. public void insert(int key) This method is the interface for the user. If the tree is empty, this method inserts the first node of the tree. Otherwise, it just calls the private insert method with the key, root, and null (the root doesn't have a prev node). public TreeNode This method is the interface for the user. delete(int key) First it initializes a TreeNode object to null. This object should store the node to be deleted. Then, it just calls the private delete method with the key, root, null (the root doesn't have a prev node), and the object reference. After returning from the private delete method, it should return the deleted node. public void printTree This method prints the first 4 levels of the tree. It prints it in a way that show the parent, child relationship. For each node, it shows the key and the balance factor. private void This method is called by printTree method. printLevel(Vector nodes. It is used to print the nodes at a particular int level) level. private int minValue(int x, You may need to call this method when inty) recalculating the balance factor of a node. It returns the minimum value of x and y. private int maxValue(int x, You may need to call this method when inty) recalculating the balance factor of a node. It returns the maximum value of x and y. Sample Output: 1) Insert a node. 2) Find a node. 3) Delete a tode. 4) Print the tree. 5) Quit. Enter a selection: 1 Enter a number this is the key): 50 1) Insert a node. 2) Find a node. 3) Delete a node. 4) Print the tree. 5) Quit. Enter a selection: Enter a number this is the keys: 25 1) Insert a node 2) Find a node. 3) Delete a node. 4) Print the tree. 5) Quit. Enter a selection: Enter a number this is the key): 75 1) Insert a node 2) Find a node 3) Delete a node 4) Print the tree. 5) Quit Enter a selection: 50 (0) 750) 250) 1) Insert a node. 2) Find a node. 3) Delete a node. 4) Print the tree. 5) Quit. Enter & selection Enter a number (this is the key): 12 1) Insert a node. 2) Find a node 3) Delete a node. 4) Print the tree. 5) Quit. Enter a selection: 1 Enter a number this is the keys: 6 1) Insert node. 2) Find a node. 3) Delete a node. 4) Print the tree. class TreeNode { public int key; public TreeNode left; public TreeNode right; public int balFactor; /* * constructor public TreeNode(int key) { this. key = key; left = right = null; balFactor = 0; } } What you need to do: These files are provided for you, you need to download them and work on them: TreeNode.java AVLTree.java Test.java The basic skeleton of the program is provided for you. You only need to fill in the blanks. You can find the skeleton of class AVL Tree in the file provided. You need to complete the methods in this file, which are briefly explained in the table below. The file TreeNode contains the class of the nodes that you will use for the AVL tree and it is already provided for you. The file Test contains the class that will test your code and it is already provided for you you don't need to change. A sample output is shown at the end. Methods of AVLTree class: These are the methods that you need to change: Method Discerption private TreeNode This method searches the tree and tries to search(int key, TreeNode find the node with the given key. If the key subRoot) is not found it should return null, otherwise it should return the node that has the key. private boolean insert(int This method does the insertion work but key, TreeNode subRoot, should make sure that the tree is a valid TreeNode prev) AVL tree after the insertion. Hence, this method may call the balance Tree method. The Boolean value returned by this method is used to indicate whether the height of the subtree rooted at subRoot has changed or not. private boolean delete(int This method does the deletion work and key, TreeNode subRoot, also make sure the tree is a valid AVL tree TreeNode prev, TreeNode after the deletion. Hence, this method may data) call the balanceTree method. The deleted node should be placed in the data parameter passed. If the key is not found, this data parameter should not change. The Boolean value returned by this method is used to indicate whether the height of the subtree rooted at subRoot has changed or not. private void This method is used to check if the balanceTree(TreeNode subRoot node is left imbalanced subRoot, TreeNode prev) (balFactor == 2) or right imbalanced (balFactor == -2). Then, it should call the appropriate rotation methods to re- balance the tree. private void This method replaces subRoot with its rotateLeft(TreeNode right child and makes the subRoot the left subRoot, TreeNode prev) child of the child that replaced it. private void This method replaces subRoot with its left rotate Right(TreeNode child and makes the subRoot the right subRoot, TreeNode prev) child of the child that replaced it. private void This method calls rotateRight with rotate RightLeft(TreeNode subRoot's right child. Then, it calls subRoot, TreeNode prev) rotateLeft on the subRoot itself. private void This method calls rotateLeft with rotate LeftRight(TreeNode subRoot's left child. Then, it calls subRoot, TreeNode prev) rotateRight on the subRoot itself. These are the methods that you must not change: Method Description public TreeNode This method is the interface for the user. It search(int key) just calls the private search method with the key and the root. public void insert(int key) This method is the interface for the user. If the tree is empty, this method inserts the first node of the tree. Otherwise, it just calls the private insert method with the key, root, and null (the root doesn't have a prev node). public TreeNode This method is the interface for the user. delete(int key) First it initializes a TreeNode object to null. This object should store the node to be deleted. Then, it just calls the private delete method with the key, root, null (the root doesn't have a prev node), and the object reference. After returning from the private delete method, it should return the deleted node. public void printTree This method prints the first 4 levels of the tree. It prints it in a way that show the parent, child relationship. For each node, it shows the key and the balance factor. private void This method is called by printTree method. printLevel(Vector nodes. It is used to print the nodes at a particular int level) level. private int minValue(int x, You may need to call this method when inty) recalculating the balance factor of a node. It returns the minimum value of x and y. private int maxValue(int x, You may need to call this method when inty) recalculating the balance factor of a node. It returns the maximum value of x and y. Sample Output: 1) Insert a node. 2) Find a node. 3) Delete a tode. 4) Print the tree. 5) Quit. Enter a selection: 1 Enter a number this is the key): 50 1) Insert a node. 2) Find a node. 3) Delete a node. 4) Print the tree. 5) Quit. Enter a selection: Enter a number this is the keys: 25 1) Insert a node 2) Find a node. 3) Delete a node. 4) Print the tree. 5) Quit. Enter a selection: Enter a number this is the key): 75 1) Insert a node 2) Find a node 3) Delete a node 4) Print the tree. 5) Quit Enter a selection: 50 (0) 750) 250) 1) Insert a node. 2) Find a node. 3) Delete a node. 4) Print the tree. 5) Quit. Enter & selection Enter a number (this is the key): 12 1) Insert a node. 2) Find a node 3) Delete a node. 4) Print the tree. 5) Quit. Enter a selection: 1 Enter a number this is the keys: 6 1) Insert node. 2) Find a node. 3) Delete a node. 4) Print the tree. class TreeNode { public int key; public TreeNode left; public TreeNode right; public int balFactor; /* * constructor public TreeNode(int key) { this. key = key; left = right = null; balFactor = 0; } }
