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

Answer 1

Solution==================================

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

//May Change if needed
class Book {
   int ISBN;

   public Book(int iSBN2) {
       ISBN = iSBN2;
   }

}

/* Class AVLNode */

class AVLNode

{

   AVLNode left, right;

   Book book;

   int height;

   /* Constructor */

   public AVLNode(Book book)

   {

       left = null;

       right = null;

       this.book = book;

       height = 0;

   }

}

/* Class AVLTree */

class AVLTree

{

   private AVLNode root;

   /* Constructor */

   public AVLTree()

   {

       root = null;

   }

   /* Function to insert data */

   public void insert(Book book)

   {

       root = insert(book, root);

   }

   /* Function to get height of node */

   private int height(AVLNode t)

   {

       return t == null ? -1 : t.height;

   }

   /* Function to max of left/right node */

   private int max(int lhs, int rhs)

   {

       return lhs > rhs ? lhs : rhs;

   }

   /* Function to insert data recursively */

   private AVLNode insert(Book book, AVLNode top)

   {

       if (top == null)

           top = new AVLNode(book);

       else if (book.ISBN < top.book.ISBN)

       {
           top.left = insert(book, top .left);

           if (height(top .left) - height(top .right) == 2) {

               System.out.print("Imbalance occurred at inserting ISBN " + book.ISBN);

               if (book.ISBN < top.left.book.ISBN) {
                   System.out.println("; fixed in Left Rotation");
                   top = rotateWithLeftChild(top );
               }

               else {
                   System.out.println("; fixed in RightLeft Rotation");
                   top = doubleWithLeftChild(top);
               }

           }

       }

       else if (book.ISBN > top.book.ISBN)

       {

           top.right = insert(book, top.right);

           if (height(top.right) - height(top.left) == 2) {

               System.out.print("Imbalance occurred at inserting ISBN " + book.ISBN);

               if (book.ISBN > top.right.book.ISBN) {
                   System.out.println("; fixed in Right Rotation");
                   top = rotateWithRightChild(top);

               } else {
                   System.out.println("; fixed in LeftRight Rotation");
                   top = doubleWithRightChild(top);
               }

           }

       }

       top.height = max(height(top.left), height(top.right)) + 1;

       return top;

   }

   /* Rotate binary tree node with left child */

   private AVLNode rotateWithLeftChild(AVLNode k2)

   {

       AVLNode k1 = k2.left;

       k2.left = k1.right;

       k1.right = k2;

       k2.height = max(height(k2.left), height(k2.right)) + 1;

       k1.height = max(height(k1.left), k2.height) + 1;

       return k1;

   }

   /* Rotate binary tree node with right child */

   private AVLNode rotateWithRightChild(AVLNode k1)

   {

       AVLNode k2 = k1.right;

       k1.right = k2.left;

       k2.left = k1;

       k1.height = max(height(k1.left), height(k1.right)) + 1;

       k2.height = max(height(k2.right), k1.height) + 1;

       return k2;

   }

   /**
   *
   * Double rotate binary tree node: first left child
   *
   * with its right child; then node k3 with new left child
   */

   private AVLNode doubleWithLeftChild(AVLNode k3)

   {

       k3.left = rotateWithRightChild(k3.left);

       return rotateWithLeftChild(k3);

   }

   /**
   *
   * Double rotate binary tree node: first right child
   *
   * with its left child; then node k1 with new right child
   */

   private AVLNode doubleWithRightChild(AVLNode k1)

   {

       k1.right = rotateWithLeftChild(k1.right);

       return rotateWithRightChild(k1);

   }

   /* Function for inorder traversal */

   public void inorder()

   {

       inorder(root);

   }

   private void inorder(AVLNode r)

   {

       if (r != null)

       {

           inorder(r.left);

           System.out.print(r.book.ISBN + " ");

           inorder(r.right);

       }

   }
}

/* Class AVL Tree Test */

public class AVLTreeTest

{

   public static void main(String[] args) throws FileNotFoundException

   {

       Scanner in = new Scanner(new File("books.txt"));
       AVLTree avlt = new AVLTree();

       while (in.hasNextLine()) {
           Book book = new Book(in.nextInt());
           avlt.insert(book);
       }
      
       System.out.print("\nIn order : ");
       avlt.inorder();

       in.close();

   }

}

Output===================

Books.txt data:

123456
789456
564789
536479
321590
260640
035478
594430
979094
799830
031236
014589
239803
123659