Question

In: Computer Science

Write code for O(n) worst-case algorithm that verifies that a tree is actually an AVL tree by detecting imbalance.


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.

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

Solutions

Expert Solution


class Book {


int id;

}

class AVLNode {

Book value;

int key, height;

AVLNode leftPtrPtr, rightPtrPtr;

// A utility function to get height of the tree

int height(AVLNode N) {

if (N == null)

return 0;

return N.height;

}

// A utility function to get maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;

}

// A utility function to rightPtr rotate subtree rooted with y

// See the diagram given above.

AVLNode rightPtrRotate(AVLNode y) {

AVLNode x = y.leftPtrPtr;

AVLNode T2 = x.rightPtrPtr;

// Perform rotation

x.rightPtrPtr = y;

y.leftPtrPtr = T2;

// Update heights

y.height = max(height(y.leftPtrPtr), height(y.rightPtrPtr)) + 1;

x.height = max(height(x.leftPtrPtr), height(x.rightPtrPtr)) + 1;

// Return new root

return x;

}

// A utility function to leftPtr rotate subtree rooted with x

// See the diagram given above.

AVLNode leftPtrRotate(AVLNode x) {

AVLNode y = x.rightPtrPtr;

AVLNode T2 = y.leftPtrPtr;

// Perform rotation

y.leftPtrPtr = x;

x.rightPtrPtr = T2;

// Update heights

x.height = max(height(x.leftPtr), height(x.rightPtr)) + 1;

y.height = max(height(y.leftPtr), height(y.rightPtr)) + 1;

// Return new root

return y;

}

// Get Balance factor of node N

int getBalance(AVLNode N) {

if (N == null)

return 0;

return height(N.leftPtr) - height(N.rightPtr);

}

AVLNode insert(AVLNode node, int key) {

/* 1. Perform the normal BST insertion */

if (node == null)

return (new AVLNode(key));

if (key < node.key)

node.leftPtr = insert(node.leftPtr, key);

else if (key > node.key)

node.rightPtr = insert(node.rightPtr, key);

else // Duplicate keys not allowed

return node;

/* 2. Update height of this ancestor node */

node.height = 1 + max(height(node.leftPtr),

height(node.rightPtr));

/* 3. Get the balance factor of this ancestor

node to check whether this node became

unbalanced */

int balance = getBalance(node);

// If this node becomes unbalanced, then there

// are 4 cases leftPtr leftPtr Case

if (balance > 1 && key < node.leftPtr.key)

return rightPtrRotate(node);

// rightPtr rightPtr Case

if (balance < -1 && key > node.rightPtr.key)

return leftPtrRotate(node);

// leftPtr rightPtr Case

if (balance > 1 && key > node.leftPtr.key) {

node.leftPtr = leftPtrRotate(node.leftPtr);

return rightPtrRotate(node);

}

// rightPtr leftPtr Case

if (balance < -1 && key < node.rightPtr.key) {

node.rightPtr = rightPtrRotate(node.rightPtr);

return leftPtrRotate(node);

}

/* return the (unchanged) node pointer */

return node;

}

// A utility function to print preorder traversal

// of the tree.

// The function also prints height of every node

void preOrder(AVLNode node) {

if (node != null) {

System.out.print(node.key + " ");

preOrder(node.leftPtr);

preOrder(node.rightPtr);

}

}

public static void main(String[] args) {

AVLNode tree = new AVLNode();

/* Constructing tree given in the above figure */

tree.root = tree.insert(tree.root, 12345);

tree.root = tree.insert(tree.root, 87654);

tree.root = tree.insert(tree.root, 974321);


System.out.println("Imbalance occurred at inserting ISBN" +tree.preOrder(tree.root)+ " fixed in LeftRight Rotation");

System.out.println("Imbalance occurred at inserting ISBN" +tree.preOrder(tree.root)+ " fixed in Left Rotation");

System.out.println("Imbalance occurred at inserting ISBN" +tree.preOrder(tree.root)+ " fixed in RightLeft Rotation");

}

}


Related Solutions

Design a linear-time algorithm that verifies that the height information in an AVL tree is correctly...
Design a linear-time algorithm that verifies that the height information in an AVL tree is correctly maintained and that the balance property is in order. (C++)
1. Modify a binary search tree implementation code (that AVL tree code depends on) to print...
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...
AVL tree; Insert and Range Minimum operation in Java code.
AVL tree; Insert and Range Minimum operation in Java code.
Write a non recursive method to insert into an AVL tree in Java
Write a non recursive method to insert into an AVL tree in Java
Course: DSA Data Structure and Algorithm What is an AVL Tree, what are its different types...
Course: DSA Data Structure and Algorithm What is an AVL Tree, what are its different types of rotation, Illustrate with examples.
c++ is the language Code an O(nlog(n)) algorithm to count the number of inversions DO NOT...
c++ is the language Code an O(nlog(n)) algorithm to count the number of inversions DO NOT ADD OR EDIT FUNCTIONS USE THESE ONLY DO NOT EDIT THE TEST FILE EITHER countInv.cpp #include <vector> #include <algorithm> using namespace std; int mergeInv(vector<int>& nums, vector<int>& left, vector<int>& right) { // You will need this helper function that calculates the inversion while merging // Your code here } int countInv(vector<int>&nums) { // Your code here } countInv_test.cpp #include <iostream> #include <vector> using namespace std;...
Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree...
Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree in level-order. That is, the method should return the root, then the nodes at depth 1, followed by the nodes at depth 2, and so on. Your algorithm should begin by putting the tree root on an initially empty queue. Then dequeue a node, add it to the output, and enqueue its left and right children (if they exist). Repeat until the queue is...
Show that the worst-case number of entries computed by the refined dynamic programming algorithm for the...
Show that the worst-case number of entries computed by the refined dynamic programming algorithm for the 0-1 Knapsack problem is in Ω(2n). Do this by considering the instance in which W = 2n −2 and wi = 2i−1 for 1 ≤ i ≤ n. Please answer with clear explanations!!! Excerpt From: Richard Neapolitan. “Foundations of Algorithms.”
Algorithm problem 4 [3.1-4] Is (2^(n+1))∈O(2^n)? Is (2^(2n))∈O(2^n)?
Algorithm problem 4 [3.1-4] Is (2^(n+1))∈O(2^n)? Is (2^(2n))∈O(2^n)?
Present an O(n) algorithm that sorts n positive integer numbers a1, a2, . . . ,...
Present an O(n) algorithm that sorts n positive integer numbers a1, a2, . . . , an which are known to be bounded by n 2 (so ai ≤ n 2 , for every i = 1, . . . , n. Use the idea of Radix Sort (discussed in class and presented in Section 8.3 in the textbook). Illustrate your algorithm by showing on paper similar to Fig. 8.3, page 198 in the textbook (make sure you indicate clearly...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT