JAVA -------------- 1 Requirements 1. Design and implement an AVL Tree Node clas
ID: 3733322 • Letter: J
Question
JAVA
--------------
1 Requirements
1. Design and implement an AVL Tree Node class that must support "nd-
Min", "insert" and "remove" operations.
2. Design and implement a driver (the main method) that does the following:
(a) Creates an array that contains a list of 5000 integers, in a random
order, from 0 to to 4098.
(b) AVL-insert, into the rst AVL tree that is initially empty, the num-
bers in the array sequentially from the start to the end.
(c) Initialize the second empty AVL tree.
(d) Enter a forever while loop to do the following:
i. Call "ndMin" to nd the node with the smallest value.
ii. Call "Remove" to remove the smallest value from the rst AVL
tree, and display "The process with a priority of %d is now sched-
uled to run!"
iii. For the removed value, change it to a random value between 0
and 4098.
iv. Call "Insert" to insert the removed value (now changed to a
dierent value in the previous step) to the second AVL tree, and
display "The process with a priority of %d has run out of its
timeslice!"
v. When the rst AVL tree becomes empty, display "Every process
has got a chance to run; Please press "Enter" to start the next
round!"
vi. When "Enter" is pressed, swap the two AVL trees, and continue
the loop.
2 Deliverables
1. Design document
2. Source code
Explanation / Answer
// Java program for insertion in AVL Tree
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
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, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate 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
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// A utility function to print preorder traversal
// of the tree.
// The function also prints height of every node
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
}
}
// This code has been contributed by Kiran
---------------------------------------------------------------------------------------------------------------
// Java program for Remove in AVL Tree
// Java program for insertion in AVL Tree
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
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, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate 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
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// A utility function to print preorder traversal
// of the tree.
// The function also prints height of every node
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
}
}
// This code has been contributed by Kiran
---------------------------------------------------------------------------------------------------------------
// Java program for Remove in AVL Tree
private AVLNode<K> findMin( AVLNode<K> t ) { if( t == null ) return t; while( t.left != null ) t = t.left; return t; } public void remove( K x ) { root = remove( x, root ); } private AVLNode<K> remove( K x, AVLNode<K> t ) { if( t == null ) return t; // Item not found; do nothing int compareResult = x.compareTo( t.data ); if( compareResult < 0 ) t.left = remove( x, t.left ); else if( compareResult > 0 ) t.right = remove( x, t.right ); else if( t.left != null && t.right != null ) // Two children { t.data = findMin( t.right ).data; t.right = remove( t.data, t.right ); } else t = ( t.left != null ) ? t.left : t.right; return t; } Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.