Question

Lab Exercises 1. Complete the class AVLTree that extends BST. It should have four methods RotateLeft, Rotate Right RotateLeftRight, and RetateRightLeft. You have to provide the methods rotate Right(), rotateLeftRight and rotateRightLeft, Provide the method delete() to delete elements in the AVL tree. 2. Create an AVL tree in which the following keys are inserted in the given order: 8, 12, 14, 18, 20, 23, 15, 13, 7, 16 Then ask the user to provide any 3 elements to delete. Print the resulting AVL tree in BFS. 3. Create an AVL tree of strings. Test your program on any given text file. After creating the AVL Tree of strings, print the AVLTree using inorder traversal.

Using JAVA

Answer 1

AVL Tree is an extended version of Binary search tree(BST), AVL Tree is self balancing BST, where the difference between heights of left and right subtrees cannot be more than one for all nodes(-1, 0, 1).

The advantage of AVL tree over BST is its Time Complexity.

1 & 2) Please read the comments for better understanding of the concept

class Node {
int key, height;
Node left, right;
  
Node(int k) {
key = k;
height = 1;
}
}
  
class AVLTree {
  
Node root;
  
// function to get height of the tree
int height(Node N) {
if (N == null)
return 0;
  
return N.height;
}
  
// function to get maximum of two integer numbers
int max(int x, int y) {
return (x > y) ? x : y;
}
  
// Right Rotation
Node RotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
  
// Performing rotation
x.right = y;
y.left = T2;
  
// Updating 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;
}
  
// Left Rotation
Node RotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
  
// Performing rotation
y.left = x;
x.right = T2;
  
// Updating 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;
}
  
//Balance factor of node N
int getBalanceFactor(Node N) {
if (N == null)
return 0;
  
return height(N.left) - height(N.right);
}
  
Node insert(Node node, int key) {
  
// 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;
  
// Update height of this ancestor node
node.height = 1 + max(height(node.left),
height(node.right));
  
//To check whether this node became unbalanced
int balance = getBalanceFactor(node);
  
// If the node becomes unbalanced, then there are 4 cases as we know
// Left Left case
if (balance > 1 && key < node.left.key)
return RotateRight(node);
  
// Right Right Case
if (balance < -1 && key > node.right.key)
return RotateLeft(node);
  
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = RotateLeft(node.left);
return RotateRight(node);
}
  
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = RotateRight(node.right);
return RotateLeft(node);
}
  
return node;
}
  
Node minValueNode(Node node)
{
Node current = node;
  
// loop down to find the leftmost leaf
while (current.left != null)
current = current.left;
  
return current;
}
  
Node Delete(Node root, int key)
{
// Normal BST Delete
if (root == null)
return root;
  
// If the key to be deleted is smaller than the root's key, then it should be in left subtree
if (key < root.key)
root.left = Delete(root.left, key);
  
// If the key to be deleted is greater than root's key, then it is in right subtree
else if (key > root.key)
root.right = deleteNode(root.right, key);
  
// if key is same as root's key, it should 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;
}
else
{
  
Node temp = minValueNode(root.right);
  
// Copy the successor of inorder data to this node
root.key = temp.key;
  
root.right = Delete(root.right, temp.key);
}
}
  
if (root == null)
return root;
  
root.height = max(height(root.left), height(root.right)) + 1;
int balance = getBalanceFactor(root);

// Left Left Case
if (balance > 1 && getBalanceFactor(root.left) >= 0)
return RotateRight(root);
  
// Left Right Case
if (balance > 1 && getBalanceFactor(root.left) < 0)
{
root.left = RotateLeft(root.left);
return RotateRight(root);
}
  
// Right Right Case
if (balance < -1 && getBalanceFactor(root.right) <= 0)
return RotateLeft(root);
  
// Right Left Case
if (balance < -1 && getBalanceFactor(root.right) > 0)
{
root.right = RotateRight(root.right);
return RotateLeft(root);
}
  
return root;
}

   void inorder(Node node)
{
if (node == null)
return;
  
//recursion on left child
inorder(node.left);
  
// then print the data of node
System.out.print(node.key + " ");
  
// recursion on right child
inorder(node.right);
}   
  
public static void main(String[] args) {
AVLTree tree = new AVLTree();
  
//Constructing tree as given in the question(2)
tree.root = tree.insert(tree.root, 8);
tree.root = tree.insert(tree.root, 12);
tree.root = tree.insert(tree.root, 14);
tree.root = tree.insert(tree.root, 18);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 23);
       tree.root = tree.insert(tree.root, 15);
tree.root = tree.insert(tree.root, 13);
tree.root = tree.insert(tree.root, 7);
tree.root = tree.insert(tree.root, 16);
  
tree.inOrder(tree.root);
      
       Scanner sc = new Scanner(System.in);
       System.out.ptintln(" Enter 3 elements to be deleted from the avl tree: ");
       for(int i = 0; i < 1; i++){
tree.root = tree.Delete(tree.root, sc.nextInt());
       }      
       System.out.println("After Deletion :");
       tree.inorder(tree.root);
}
}

3) please read the comments for better understanding

class Node {
String key;
int height;  
Node left, right;
  
Node(String k) {
key = k;
height = 1;
}
}

Class AVLString{
public AVLNode search(String key)
{
// Tree is empty
if (root == null)
{
return null;
}
// Tree is not empty
AVLNode p = root;
try
{while (true)
{
if(p == null && p.getData().equals(key))
{
break;
}
else if (key.compareTo(p.getData()) < 0)
{
p = p.getLeftChild();
}
else
{
p = p.getRightChild();
}
}
}
catch(NullPointerException e)
{
e.printStackTrace();
}
return p;
}

public void insert(String data)
{
try
{
// Case: tree is empty
if (root == null)
{
root = new AVLNode(data);
return;
}
// Case: tree is not empty
AVLNode p = root;
// move p down as far as we can
while(true)
{
if (data.equals(p.getData()) && p.getLeftChild() != null)
{
p = p.getLeftChild();
}
else if(data.compareTo(p.getData()) < 0 && p.getLeftChild() != null)
{
p = p.getLeftChild();
}
else if (data.compareTo(p.getData()) > 0 && p.getRightChild() != null)
{
p = p.getRightChild();
}
else
{
break;
}
}
// insert new node to the tree as a child of node p
AVLNode newNode= new AVLNode(data);
if(data.equals(p.getData()))
{
p.setLeftChild(newNode);
}
else if (data.compareTo(p.getData()) < 0)
{
p.setLeftChild(newNode);
}
else
{
p.setRightChild(newNode);
}
rebalanceInsertionPath(newNode);
}
catch(NullPointerException n)
{
n.printStackTrace();
}
}
   void inorder(Node node)
{
if (node == null)
return;
  
//recursion on left child
inorder(node.getLeftChild());
  
// then print the data of node
System.out.print(node.key + " ");
  
// recursion on right child
inorder(node.getRightChild());
}   
  
  
   public static void main(String[] args) throws Exception
{
     
   AVLString tree = new AVLString();
// pass the path to the file as a parameter
FileReader fr =
new FileReader("your file path");
  
int i;
while ((i=fr.read()) != -1)
tree.insert((String) i);
     
   tree.inorder(tree.root);
  
}
}

The Height of AVL Tree is always O(log n) where n is number of nodes and time complexity of most of operations is O(log n).

Hope the answer is helpful, All the best!