Write a java program that performs n operations (find, insert, and delete String
ID: 3806245 • Letter: W
Question
Write a java program that performs n operations (find, insert, and delete Strings) on AVL tree and tracks the performance (hint: System.currentTimeMillis()). Your program must have at least one class called Driver2 which runs the program. This classes should have a no argument constructor and implement the following interface. public interface BalancedTree<E extends Comparable<E>> { public void insert(E item);public E find(E item);
public void delete(E item);
public void printInOrderTraversal();
public int isWellFormed(); }
The isWellFormed() method checks the AVL tree if it follows the appropriate rules (0 for true and 1 for false).
Write a java program that performs n operations (find, insert, and delete Strings) on AVL tree and tracks the performance (hint: System.currentTimeMillis()). Your program must have at least one class called Driver2 which runs the program. This classes should have a no argument constructor and implement the following interface. public interface BalancedTree<E extends Comparable<E>> { public void insert(E item);
public E find(E item);
public void delete(E item);
public void printInOrderTraversal();
public int isWellFormed(); }
The isWellFormed() method checks the AVL tree if it follows the appropriate rules (0 for true and 1 for false).
Write a java program that performs n operations (find, insert, and delete Strings) on AVL tree and tracks the performance (hint: System.currentTimeMillis()). Your program must have at least one class called Driver2 which runs the program. This classes should have a no argument constructor and implement the following interface. public interface BalancedTree<E extends Comparable<E>> { public void insert(E item);
public E find(E item);
public void delete(E item);
public void printInOrderTraversal();
public int isWellFormed(); }
The isWellFormed() method checks the AVL tree if it follows the appropriate rules (0 for true and 1 for false).
Explanation / Answer
----------------BalancedTree.java--------------------------
public interface BalancedTree<E extends Comparable<E>> {
public void insert(E item);
public E find(E item);
public void delete(E item);
public void printInOrderTraversal();
public int isWellFormed();
}
------------------Node.java-------------------
// Java program for insertion in AVL Tree
public class Node {
String key;
int height;
Node left, right;
Node(String d) {
key = d;
height = 1;
}
}
-----------------------AVLTree.java------------------
public class AVLTree implements BalancedTree<String> {
Node root;
// A utility function to get height of the tree
int height(Node N)
{
if (N == null)
return 0;
return N.height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
Node rightRotate(Node y)
{
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
Node leftRotate(Node x)
{
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node N)
{
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
Node insert(Node node, String key)
{
/* 1. Perform the normal BST rotation */
if (node == null)
return (new Node(key));
if (key.compareTo(node.key) < 0)
node.left = insert(node.left, key);
else if (key.compareTo(node.key) > 0)
node.right = insert(node.right, key);
else // Equal keys not allowed
return node;
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left),
height(node.right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
Wunbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then
// there are 4 cases Left Left Case
if (balance > 1 && key.compareTo(node.left.key)<0)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key.compareTo(node.right.key)>0)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key.compareTo(node.left.key)>0)
{
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key.compareTo(node.right.key)<0)
{
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
/* Given a non-empty binary search tree, return the
node with minimum key value found in that tree.
Note that the entire tree does not need to be
searched. */
Node minValueNode(Node node)
{
Node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null)
current = current.left;
return current;
}
Node deleteNode(Node root, String key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == null)
return root;
// If the key to be deleted is smaller than
// the root's key, then it lies in left subtree
if (key.compareTo(root.key)<0)
root.left = deleteNode(root.left, key);
// If the key to be deleted is greater than the
// root's key, then it lies in right subtree
else if (key.compareTo(root.key)>0)
root.right = deleteNode(root.right, key);
// if key is same as root's key, then this is the node
// to be deleted
else
{
// node with only one child or no child
if ((root.left == null) || (root.right == null))
{
Node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
// No child case
if (temp == null)
{
temp = root;
root = null;
}
else // One child case
root = temp; // Copy the contents of
// the non-empty child
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node temp = minValueNode(root.right);
// Copy the inorder successor's data to this node
root.key = temp.key;
// Delete the inorder successor
root.right = deleteNode(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = max(height(root.left), height(root.right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root.left) < 0)
{
root.left = leftRotate(root.left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root.right) > 0)
{
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
// A utility function to print preorder traversal of
// the tree. The function also prints height of every
// node
void inOrder(Node node)
{
if (node != null)
{
inOrder(node.left);
System.out.print(node.key + " ");
inOrder(node.right);
}
}
public void insert(String item) {
insert(root, item);
}
public String find(String item) {
return search(root,item);
}
public void delete(String item) {
deleteNode(root, item);
}
public void printInOrderTraversal() {
inOrder(root);
}
public int isWellFormed() {
return isBalanced(root);
}
String search(Node node, String key)
{
/* 1. Perform the normal BST rotation */
if (node.key.equalsIgnoreCase(key))
return key;
if(node==null)
return "Not Found";
if (key.compareTo(node.key) < 0)
search(node.left, key);
else if (key.compareTo(node.key) > 0)
search(node.right, key);
return "Not Found";
}
int isBalanced(Node node)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (node == null)
return 1;
/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);
if (Math.abs(lh-rh) <= 1 && isBalanced(node.left)==1 && isBalanced(node.right)==1)
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
}
-----------------------Driver2.java-------------
public class Driver2 {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.insert( "A");
tree.insert("B");
tree.insert("C");
tree.insert("D");
tree.printInOrderTraversal();
tree.delete("C");
}
}
------------------Some Source code has been taken from geeksforgeeks--------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.