import java.util.*;
class AVLTree { private final static int PRINT_LEVELS = 4; private TreeNode root; /* * constructor */ public AVLTree() { root = null; }
/* * public search */ public TreeNode search(int key) { return search(key, root); }
/* * public insert */ public void insert(int key) { if(root == null) { root = new TreeNode(key); return; }
// insert the node in the tree insert(key, root, null); }
/* * public delete */ public TreeNode delete(int key) { TreeNode data = null; delete(key, root, null, data); return data; }
/* * private search */ private TreeNode search(int key, TreeNode subRoot) { /* * INSERT YOUR CODE HERE. */ }
/* * private insert */ private boolean insert(int key, TreeNode subRoot, TreeNode prev) { /* * INSERT YOUR CODE HERE. */ }
/* * private delete * * The arguments to this method are a bit of a kludge because * Java doesn't support pointers - at least not in any good way. :{ * So if on return from this method the key value in TreeNode data is * set to null, then the key wasn't found. Otherwise, the node was * found and it's key value is set to the appropriate value. */ private boolean delete(int key, TreeNode subRoot, TreeNode prev, TreeNode data) { /* * INSERT YOUR CODE HERE. */ } /* * balanceTree */ private void balanceTree(TreeNode subRoot, TreeNode prev) { /* * INSERT YOUR CODE HERE. */ }
/* * rotateLeft */ private void rotateLeft(TreeNode subRoot, TreeNode prev) { /* * INSERT YOUR CODE HERE. */ }
/* * rotateRight */ private void rotateRight(TreeNode subRoot, TreeNode prev) { /* * INSERT YOUR CODE HERE. */ }
/* * rotateRightLeft */ private void rotateRightLeft(TreeNode subRoot, TreeNode prev) { /* * INSERT YOUR CODE HERE. */ }
/* * rotateLeftRight */ private void rotateLeftRight(TreeNode subRoot, TreeNode prev) { /* * INSERT YOUR CODE HERE. */ }
/* * printTree */ public void printTree() { if(root == null) { System.out.println("Tree is empty"); return; } LinkedList queue = new LinkedList(); Vector nodes = new Vector(); int level = 0;
// enqueue the root queue.add(root);
// now print out each level - if a node is null, just enqueue null while(level
/* * printLevel */ private void printLevel(Vector nodes, int level) { // tab over for the first node in the level //for(int i=0; i
// printing out the node - no sibling if(nodes.size() == 1) { TreeNode tmp = (TreeNode)nodes.get(0); System.out.print(tmp.key + "(" + tmp.balFactor + ")"); }
// every other node has or could have a sibling else { for(int i=0; i // print out the first node if it exists if(tmp != null) System.out.print(tmp.key + "(" + tmp.balFactor + ")"); else System.out.print("\t");
// tab over to it's sibling for(int j=0; j
// now print out the sibling if it exists tmp = (TreeNode)nodes.get(i+1); if(tmp != null) System.out.print(tmp.key + "(" + tmp.balFactor + ")"); else System.out.print("\t");
// tab over to it's cousin for(int j=0; j
// done with this level System.out.print(" "); }
/* * minValue */ private int minValue(int x, int y) { return (x y) ? x : y; } }
----------------
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 AVLTree 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 balanceTree 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 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 AVLTree 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 balanceTree 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 == == re- 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 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 rotate Right with rotate RightLeft(TreeNode subRoot's right child. Then, it calls subRoot, TreeNode prev) rotate Left on the subRoot itself. private void This method calls rotateLeft with rotateLeftRight(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. 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 AVLTree 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 balanceTree 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 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 AVLTree 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 balanceTree 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 == == re- 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 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 rotate Right with rotate RightLeft(TreeNode subRoot's right child. Then, it calls subRoot, TreeNode prev) rotate Left on the subRoot itself. private void This method calls rotateLeft with rotateLeftRight(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
