[Link].
Scanner;
classAVLTree
{
// NODE structure
class Node
{
int value;
int height;
Node left;
Node right;
public Node(int value)
{
[Link] = value;
[Link] = 1;
[Link] = null;
[Link] = null;
}
}
// returns the height of the node
int Height(Node key)
{
if (key == null)
return 0;
else
return [Link];
}
// Balance computes the balance factor of the node
int Balance(Node key)
{
if (key == null)
return 0;
else
return ( Height([Link]) - Height([Link]) );
}
// updateHeight updates the height of the node
void updateHeight(Node key)
{
int l = Height([Link]);
int r = Height([Link]);
[Link] = [Link](l , r) + 1;
}
Node rotateLeft(Node x)
{
Node y = [Link];
Node T2 = [Link];
[Link] = x;
[Link] = T2;
updateHeight(x);
updateHeight(y);
return y;
}
Node rotateRight(Node y)
{
Node x = [Link];
Node T2 = [Link];
[Link] = y;
[Link] = T2;
updateHeight(y);
updateHeight(x);
return x;
}
// balanceTree balances the tree using rotations after an insertion or deletion
Node balanceTree(Node root)
{
updateHeight(root);
int balance = Balance(root);
if (balance > 1) //R
{
if (Balance([Link]) < 0)//RL
{
[Link] = rotateRight([Link]);
return rotateLeft(root);
}
else //RR
returnrotateLeft(root);
}
if (balance < -1)//L
{
if (Balance([Link]) > 0)//LR
{
[Link] = rotateLeft([Link]);
return rotateRight(root);
}
else//LL
return rotateRight(root);
}
return root;
}
Node Root;
Node BSTInsert(Node root, int key)
{
// Performs normal BST insertion
if (root == null)
return new Node(key);
else if (key <[Link])
[Link] = BSTInsert([Link], key);
else
[Link] = BSTInsert([Link], key);
// Balances the tree after BST Insertion
Return balanceTree(root);
}
// Successor returns the next largest node
Node Successor(Node root)
{
if ([Link] != null)
return Successor([Link]);
else
return root;
}
Node Remove(Node root, int key)
{
// Performs standard BST Deletion
if (root == null)
return root;
else if (key <[Link])
[Link] = Remove([Link], key);
else if (key >[Link])
[Link] = Remove([Link], key);
else
{
if ([Link] == null)
root = [Link];
else if ([Link] == null)
root = [Link];
else
{
Node temp = Successor([Link]);
[Link] = [Link];
[Link] = Remove([Link], [Link]);
}
}
if (root == null)
return root;
else
// Balances the tree after deletion
returnbalanceTree(root);
}
// findNode is used to search for a particular value given the root
Node findNode(Node root, int key)
{
if (root == null || key==[Link])
return root;
if (key <[Link])
return findNode([Link], key);
else
return findNode([Link], key);
}
// Utility function for insertion of node
void add(int key)
{
if (findNode(Root , key) == null)
{
Root = BSTInsert(Root , key);
[Link]("Insertion successful");
}
else
[Link]("\nKey with the entered value already exists in the tree");
}
int search(int key)
{
if(findNode(Root, key) == null)
return 0;
else
return 1;
}
// Utility function for deletion of node
void delete(int key)
{
if (findNode(Root , key) != null)
{
Root = Remove(Root , key);
[Link]("\nDeletion successful ");
}
else
[Link]("\nNo node with entered value found in tree");
}
voidInOrder(Node root)
{
if(root == null)
{
[Link]("\nNo nodes in the tree");
return;
}
if([Link] != null)
InOrder([Link]);
[Link]([Link] + " ");
if([Link] != null)
InOrder([Link]);
}
voidPreOrder(Node root)
{
if(root == null)
{
[Link]("No nodes in the tree");
return;
}
[Link]([Link] + " ");
if([Link] != null)
PreOrder([Link]);
if([Link] != null)
PreOrder([Link]);
voidPostOrder(Node key)
{
if(key == null)
{
[Link]("No nodes in the tree");
return;
}
if([Link] != null)
PostOrder([Link]);
if([Link] != null)
PostOrder([Link]);
[Link]([Link] + " ");
public class Main
{
public static void main(String[] args)
{
Scanner scan = new Scanner([Link]);
AVLTree tree = new AVLTree();
while(true)
{
[Link]("\n\n1. Insert\n2. Delete\n3. Search\n4. Inorder traversal\n5. Preorder traversal\n6.
Postorder traversal\n7. Exit");
int choice = [Link]();
if(choice == 7) {
[Link]("Exit");
break;
}
switch(choice) {
case 1:
{
[Link]("Enter the elements to add and enter -999 to stop:");
while([Link]()) {
int temp = [Link]();
if(temp == -999)
break;
[Link](temp);
}
[Link]("\nInOrder Traversal :");
[Link]([Link]);
[Link]("\nPreOrder Traversal :");
[Link]([Link]);
break;
}
case 2:
{
[Link]("Enter the element to be deleted:");
int temp = [Link]();
[Link](temp);
[Link]("\nInOrder Traversal :");
[Link]([Link]);
[Link]("\nPreOrder Traversal :");
[Link]([Link]);
break;
}
case 3:
{
[Link]("Enter the element to be searched:");
int temp = [Link]();
int c = [Link](temp);
if(c==0)
[Link]("\nKey not found");
else
[Link](temp + "found");
}
case 4:
{
[Link]("\nInOrder Traversal :");
[Link]([Link]);
break;
}
case 5:
{
[Link]("\nPreOrder Traversal :");
[Link]([Link]);
break;
}
case 6:
{
[Link]("\nPostOrder Traversal :");
[Link]([Link]);
break;
}
}
}
}
}