Question

1. Modify a binary search tree implementation code (that AVL tree code depends on) to print out the data value for each node it encounters in the insert operation.

Remember that the module AVL tree code gets part of its functionality from the BST type, since an AVL tree is a binary search tree, but adds some additional functionality.

2. Add code to the main method to meet the following requirements:

(a) Create an AVL tree to hold names stored as String objects (one name in each node of the tree)

(b) Repeat the following at least four times: i. Insert another String data node whose value ’comes after’ (lexicographically) the value last inserted, as ’banana’ comes after ’apple’, using standard tree operations

Try insert

ii. Print out the entire tree contents of the tree using a preorder traversal

Answer 1

Program

// An AVL tree node
class AVLTree
{
   //AVLTreeNode(inner) class
   public class AVLTreeNode
   {
       public String key;
       public AVLTreeNode left;
       public AVLTreeNode right;
       public char balanceFactor;
       int height;
      
       //constructoror
       public AVLTreeNode(String key, AVLTreeNode left, AVLTreeNode right)
       {
           this.key = key;
           this.left = left;
           this.right = right;
           height = 1;    // new AVLTreeNodeis initially added at leaf
           balanceFactor = '-';
       }
   }
  
   private AVLTreeNode root;
  
   //constructor
   public AVLTree()
   {
       root = null;
   }
  
   // A utility method to get height of the tree
   int height(AVLTreeNode N)
   {
       if (N == null)
           return 0;
       return max(height(N.left) , height(N.right)) + 1;
   }
  
   // A utility method to get maximum of two integers
   int max(int a, int b)
   {
       return (a > b)? a : b;
   }
  
   // A utility method to right rotate
   AVLTreeNode rightRotate(AVLTreeNode y)
   {
       AVLTreeNode x = y.left;
       AVLTreeNode T2 = x.right;
  
       // Perform rotation
       x.right = y;
       y.left = T2;
      
       return x;
   }
  
   // A utility function to left rotate
   AVLTreeNode leftRotate(AVLTreeNode x)
   {
       AVLTreeNode y = x.right;
       AVLTreeNode T2 = y.left;
      
       // Perform rotation
       y.left = x;
       x.right = T2;
      
       return y;
   }
  
   // Get Balance factor of AVLTreeNodeN
   char getBalance(AVLTreeNode N)
   {
       if (N == null)
       return '-';
       if(height(N.left) - height(N.right) > 1)
           return '/';
       if(height(N.left) - height(N.right) < -1)
           return '\\';
       return '-';
   }
  
   // Recursive method to insert key in subtree rooted
   // with AVLTreeNodeand returns new root of subtree.
   AVLTreeNode insert(AVLTreeNode node, String key)
   {
       /* 1. Perform the normal BST insertion */
       if (node== null)
           return new AVLTreeNode(key, null, null);
      
       System.out.print (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 are not allowed in BST
           return node;
      
       /* 2. Update height of this ancestor AVLTreeNode*/
       node.height = node.height + 1;
      
       /* 3. Get the balance factor of this ancestor
       AVLTreeNodeto check whether this AVLTreeNodebecame
       unbalanced */
       char balance = getBalance(node);
      
       // If this AVLTreeNodebecomes unbalanced, then
       // there are 4 cases
      
       // Left Left Case
       if (balance == '/' && key.compareTo(node.left.key)<0)
           return rightRotate(node);
      
       // Right Right Case
       if (balance == '\\' && key.compareTo(node.right.key)>0)
           return leftRotate(node);
      
       // Left Right Case
       if (balance == '/' && key.compareTo(node.left.key)>0)
       {
           node.left = leftRotate(node.left);
           return rightRotate(node);
       }
      
       // Right Left Case
       if (balance == '\\' && key.compareTo(node.right.key)<0)
       {
           node.right = rightRotate(node.right);
           return leftRotate(node);
       }
      
       /* return the (unchanged) AVLTreeNodepointer */
       return node;
   }
  
   public void insert(String key)
   {
       root = insert(root, key);
       System.out.println ();
   }
   // Helper method to traverse the avltree in preorder
   private void preorder(AVLTreeNode root)
   {
       if(root!=null)
       {
           System.out.print(root.key+ " ");
           preorder(root.left);
           preorder(root.right);
       }
   }
   //method to traverse the avltree in preorder
   public void preorder()
   {
       preorder(root);
   }
}

//Driver class to test
class Driver
{
   //main method
   public static void main (String[] args)
   {
       //create object of AVLTree
       AVLTree avl = new AVLTree();
      
       //insert String data
       System.out.print ("Insert \"apple\": ");
       avl.insert("apple");
       System.out.print ("Insert \"banana\": ");
       avl.insert("banana");
       System.out.print ("Insert \"cat\": ");
       avl.insert("cat");
       System.out.print ("Insert \"dog\": ");
       avl.insert("dog");
       //traverse the avltree in preorder
       System.out.println ("Preorder traversal: ");
       avl.preorder();
   }
}

Output:

Insert "apple":
Insert "banana": apple
Insert "cat": apple banana
Insert "dog": banana cat
Preorder traversal:
banana apple cat dog

Solving your question and helping you to well understand it is my focus. So if you face any difficulties regarding this please let me know through the comments. I will try my best to assist you. However if you are satisfied with the answer please don't forget to give your feedback. Your feedback is very precious to us, so don't give negative feedback without showing proper reason.

Thank you.