Question

Your work should be readable as well as correct.

Always Verify Time!

Write code for O(n) worst-case algorithm that verifies that a tree is actually an AVL tree by detecting imbalance. If imbalance is true, then call the proper rotation function provided in the lecture slides to fix the imbalance condition.

1. Must read AVLNode data from a text file

2. Create a Book Object; and an AVL node object to be inserted into the AVL tree

3. At each insert, detect imbalance and fix the AVL tree

4. Report each imbalance detection and the node where it occurred; and output the message:

Output:

Imbalance occurred at inserting ISBN 12345; fixed in LeftRight Rotation

Imbalance occurred at inserting ISBN 87654; fixed in Left Rotation

Imbalance occurred at inserting ISBN 974321; fixed in RightLeft Rotation

class AVLNode

int key; (ISBN number)

Book value; //create a class representing a book with minimum attributes

int height;

AVLNode leftPtr;

AVLNode rightPtr;

}

You must verify the AVL balance condition at each insert and detect and fix imbalance, output result of each insertion. A null node is considered AVL property of height -1.

Java or C++ are the options.

Bonus (20%): Create a random binary tree and verify BST property and AVL balance condition. Do not hard code the tree inside the code.

Answer 1

Note:

• Please save all the files in the single project and then run the AVLTreeTest .java file to get the output.
• This code compiled and executed successfully in the eclipse editor.
• Books.txt have some random values. Because the input text file is not given in the question and also ISBN values taken as integer type as per the question.

Program Screenshots:

Sample Input:

Books.txt

Sample Output:

Code to be Copied:

AVLNode.java

//Create a class AVL node
class AVLNode
{
   //(ISBN number)
   int key;
  
   //create a class representing a
   //book with minimum attributes
   Book value;
   int height;
   AVLNode leftPtr;
   AVLNode rightPtr;
  
   /* Parameter Constructor */
   public AVLNode(Book book)
   {
       leftPtr = null;
       rightPtr = null;
       this.value = book;
       height = 0;
   }
}
//Declare book class
class Book
{
   //declare isbn value
   int ISBN;
   //book constructor
   public Book(int isbnValue)
   {
       ISBN = isbnValue;
   }
}

AVLTree.java

//Class AVLTree
class AVLTree
{  
   //Define the variable root
   private AVLNode root;
  
   //Constructor
   public AVLTree()
   {
       root = null;
   }
   //Implement function
   //to insert the data
   public void insert(Book book)
   {
       root = insert(book, root);
   }
   //Implement function to
   //get the height of tree
   private int height(AVLNode tree)
   {
       //if tree is null return -1
       //otherwise return height of tree
       return tree == null ? -1 : tree.height;
   }

   //Implement method to get the maxValue
   private int maxValue(int left, int right)
   {
       return left > right ? left : right;
   }
  
   //Implement the method to insert
   //the data recursively
   private AVLNode insert(Book book, AVLNode top)
   {
       //if the top value is null
       if (top == null)
       {
           top = new AVLNode(book);
       }
       //Otherwise compare the ISBN
       else if (book.ISBN < top.value.ISBN)
       {      
           top.leftPtr = insert(book,top.leftPtr);
           //Compare the height of the trees
           if (height(top.leftPtr) - height(top.rightPtr) == 2)
           {
               System.out.print("Imbalance occurred at inserting ISBN " + book.ISBN);
               //Compare the nodes of the trees
               if (book.ISBN < top.leftPtr.value.ISBN)
               {
                   System.out.println("; fixed in Left Rotation");
                   top = rotateWithLeftChild(top );
               }
               else
               {
                   System.out.println("; fixed in RightLeft Rotation");
                   top = doubleWithLeftChild(top);
               }
           }
       }
      
       //compare wether the top element
       //inserted element is greater or not
       else if (book.ISBN > top.value.ISBN)
       {
           top.rightPtr = insert(book, top.rightPtr);
           if (height(top.rightPtr) - height(top.leftPtr) == 2)
           {
               System.out.print("Imbalance occurred at inserting ISBN " + book.ISBN);
               if (book.ISBN > top.rightPtr.value.ISBN)
               {
                   System.out.println("; fixed in Right Rotation");
                   top = rotateWithRightChild(top);
               }
               else
               {
                   System.out.println("; fixed in LeftRight Rotation");
                   top = doubleWithRightChild(top);
               }
           }
       }
       //Get the max value for the left and right nodes of the tree
       top.height = maxValue(height(top.leftPtr), height(top.rightPtr)) + 1;
       return top;
   }
   // Rotate binary tree node with left child
   private AVLNode rotateWithLeftChild(AVLNode k2)
   {
       AVLNode k1 = k2.leftPtr;
       k2.leftPtr = k1.rightPtr;
       k1.rightPtr = k2;
       k2.height = maxValue(height(k2.leftPtr), height(k2.rightPtr)) + 1;
       k1.height = maxValue(height(k1.leftPtr), k2.height) + 1;
       return k1;
   }
   // Rotate binary tree node with right child
   private AVLNode rotateWithRightChild(AVLNode right)
   {
       AVLNode k2 = right.rightPtr;
       right.rightPtr = k2.leftPtr;
       k2.leftPtr = right;
       right.height = maxValue(height(right.leftPtr), height(right.rightPtr)) + 1;
       k2.height = maxValue(height(k2.rightPtr), right.height) + 1;
       return k2;
   }
  
   //Implement method for doubleWithRightChild
   private AVLNode doubleWithLeftChild(AVLNode value)
   {
       value.leftPtr = rotateWithRightChild(value.leftPtr);
       return rotateWithLeftChild(value);
   }
  
   //Implement method for doubleWithRightChild
   private AVLNode doubleWithRightChild(AVLNode value)
   {
       value.rightPtr = rotateWithLeftChild(value.rightPtr);
       return rotateWithRightChild(value);
   }
   //Implement method to
   //call the inorder traversal
   public void inorder()
   {
       inorder(root);
   }
   //Implement method inorder()
   private void inorder(AVLNode root)
   {
       //If root is not equal to null
       if (root!= null)
       {
           //traverse left
           inorder(root.leftPtr);
           //print the node
           System.out.print(root.value.ISBN + " ");
           //traverse the right
           inorder(root.rightPtr);
       }
   }
}

AVLTreeTest.java

//Declare packages for File
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

//Create AVL test class
public class AVLTreeTest
{
   //main method
   public static void main(String[] args) throws FileNotFoundException
   {
       //Create scanner object
       Scanner sc = new Scanner(new File("Books.txt"));
       //Create object for AVL tree class
       AVLTree treeObj = new AVLTree();

       //Read the integer isbn values from file
       while (sc.hasNextLine())
       {          
           Book book = new Book(sc.nextInt());
           treeObj.insert(book);
       }
       //print the inorder
       System.out.print("\nIn order : ");
       treeObj.inorder();
       sc.close();
   }

}

Bonus Question:

Program Screenshots:

Sample Output:

Code to be Copied:

Bonus Part:

BinaryTree.java

//Include required package
import java.util.*;

//Declare Node class
class Node
{
   int key;
   Node leftPtr,rightPtr;
   public Node(int key)
   {
       this.key = key;
       leftPtr = null;
       rightPtr = null;
   }
}

//Define method to set height is 0
class Height
{
   int height=0;
}

//Declare class Binary tree
public class BinaryTree
{
   //Insert method
   static void insert(Node root,int key)
   {
       //Create random values
       Random rand = new Random();      
       int value = rand.nextInt(2);
       //System.out.print("root: "+ value);

       //insert in left sub tree
       //with 0.5 probability
       if (value==0)
       {
           if (root.leftPtr!=null)
           {
               insert(root.leftPtr,key);
               return;
           }
           else
           {
               Node temp = new Node(key);
               root.leftPtr = temp;
               return;
           }
       }
       else
       {
           //insert in right sub tree
           //with 0.5 probability
           if (root.rightPtr!=null)
           {
               insert(root.rightPtr,key);
               return;
           }
           else{
               Node temp = new Node(key);
               root.rightPtr = temp;
               return;
           }
       }
   }
  
   //Check the bst priperty of the tree
   static boolean checkBSTOrder(Node root)
   {
       return isBST(root, Integer.MIN_VALUE,
               Integer.MAX_VALUE);
   }
  
   //check whether the tree is BST tree or not
   static boolean isBST(Node node, int min, int max)
   {
       //If node is empty, then return true
       if (node == null)
           return true;
      
       //If the conditon false, the BST property fails
       if (node.key < min || node.key > max)
           return false;
      
       //check the condition of nodes recursively
       return (isBST(node.leftPtr, min, node.key-1) &&
               isBST(node.rightPtr, node.key+1, max));
   }
  
   //implement method
   static int treeHeight(Node node)
   {
       //If tree is null then height is 0
       if (node == null)
           return 0;
       //If tree is not empty then
       //height = 1 + max of left
       //height and right heights
       return 1 + Math.max(treeHeight(node.leftPtr),
               treeHeight(node.rightPtr));
   }
  
   //check AVLtree property
   static boolean checkAVLProperty(Node root,Height height)
   {
       //If root is null, then tree is empty
       if (root == null)
       {
           height.height = 0;
           return true;
       }
      
       //Get heights of left and right sub trees
       Height lheight = new Height();
       Height rheight = new Height();
      
       boolean checkLeft = checkAVLProperty(root.leftPtr, lheight);
       boolean checkRight = checkAVLProperty(root.rightPtr, rheight);
      
       //Get height of left and right subtrees
       int lh = lheight.height;
       int rh = rheight.height;
      
       // Height of current node is max of heights of
       //left and right subtrees plus 1
       height.height = (lh > rh? lh: rh) + 1;
      
       //comute to check height of tree condition
       if (Math.abs(lh - rh)>=2)
           return false;
       else
           return checkLeft && checkRight;
   }

   //Main method
   public static void main(String[] args)
   {
       //create random class object
       Random r = new Random();
       int nodeValue = r.nextInt(50);
       Node root = new Node(nodeValue);
       int values[] = new int[50];
       values[nodeValue]=1;
       //use for-loop to iterate 10times
       for (int i=0;i<10;i++)
       {
           //insert the keys in the BST
           while (true)
           {
               //generate random number
               nodeValue = r.nextInt(50);
               if (values[nodeValue]==0)
               {
                   //if the genrate value is 0
                   //then set the number to 1
                   values[nodeValue] = 1;
                   break;
               }
           }
           //insert the element in the tree
           insert(root,nodeValue);
       }

       //Check the BSTOrder for the root
       if (checkBSTOrder(root))
       {
           System.out.println("Random generated tree follow BST order property.");
       }
       else
       {
           System.out.println("Random generated tree not following BST order property.");
       }
       Height height = new Height();
       //Check the AVLtree Property
       if (checkAVLProperty(root,height))
       {
           System.out.println("Random generated tree following "
                   + "AVL balance condition.");
       }
       else{
           System.out.println("Random generated tree not following "
                   + "AVL balance condition.");
       }  
}
}