Question

This assignment helps to reinforce your understanding of AVL trees (and thus binary search trees).

Implement method restructure in file AVLTree.java. Submit only file AVLTree.java.

You may use either the cut/link restructuring algorithm or the trinode restructuring algorithm (in the textbook). The latter is recommended as it makes program tracing and debugging easier.

Output Expectation:

single rotation - Right
Test case 1a:
Preorder : 40 30 50 
Postorder: 30 50 40 

Test case 1b:
Preorder : 40 30 60 50 70 
Postorder: 30 50 70 60 40 

Test case 1c:
Preorder : 60 40 30 50 70 80 
Postorder: 30 50 40 80 70 60 

Test case 1d:
Preorder : 60 40 30 50 80 70 90 
Postorder: 30 50 40 70 90 80 60 

Double rotation >
Test case 3a:
Preorder : 35 30 40 
Postorder: 30 40 35 

Test case 3b:
Preorder : 35 30 45 40 50 
Postorder: 30 40 50 45 35 

Test case 3c:
Preorder : 40 35 30 38 45 50 
Postorder: 30 38 35 50 45 40 

Test case 3d:
Preorder : 40 35 30 38 48 45 50 
Postorder: 30 38 35 45 50 48 40 

Download all the files in this directory/folder to your computer, including AVLTree.java and testProgram.java. To compile all the files, simply issue the command:
javac testProgram.java

Answer 1

import java.io.*;
import java.util.*;

public class AVLTree {
public class Node {
private Node left, right, parent;
private int height = 1;
private int value;

private Node (int val) {
this.value = val;
}
}
private int height (Node N) {
if (N == null)
return 0;
return N.height;
}

private Node insert(Node node, int value) {
/* 1. Perform the normal BST rotation */
if (node == null) {
return(new Node(value));
}

if (value < node.value)
node.left = insert(node.left, value);
else
node.right = insert(node.right, value);

/* 2. Update height of this ancestor node */
node.height = Math.max(height(node.left), height(node.right)) + 1;

/* 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

// Left Left Case
if (balance > 1 && value < node.left.value)
return rightRotate(node);

// Right Right Case
if (balance < -1 && value > node.right.value)
return leftRotate(node);

// Left Right Case
if (balance > 1 && value > node.left.value)
{
node.left = leftRotate(node.left);
return rightRotate(node);
}

// Right Left Case
if (balance < -1 && value < node.right.value)
{
node.right = rightRotate(node.right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */
return node;
}

private Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;

// Perform rotation
x.right = y;
y.left = T2;

// Update heights
y.height = Math.max(height(y.left), height(y.right))+1;
x.height = Math.max(height(x.left), height(x.right))+1;

// Return new root
return x;
}

private Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;

// Perform rotation
y.left = x;
x.right = T2;

// Update heights
x.height = Math.max(height(x.left), height(x.right))+1;
y.height = Math.max(height(y.left), height(y.right))+1;

// Return new root
return y;
}

// Get Balance factor of node N
private int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}

public void preOrder(Node root) {
if (root != null) {
preOrder(root.left);
System.out.printf("%d ", root.value);
preOrder(root.right);
}
}

private Node minValueNode(Node node) {
Node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null)
current = current.left;
return current;
}

private Node deleteNode(Node root, int value) {
// STEP 1: PERFORM STANDARD BST DELETE

if (root == null)
return root;

// If the value to be deleted is smaller than the root's value,
// then it lies in left subtree
if ( value < root.value )
root.left = deleteNode(root.left, value);

// If the value to be deleted is greater than the root's value,
// then it lies in right subtree
else if( value > root.value )
root.right = deleteNode(root.right, value);

// if value is same as root's value, then This is the node
// to be deleted
else {
// node with only one child or no child
if( (root.left == null) || (root.right == null) ) {

Node temp;
if (root.left != null)
temp = root.left;
else
temp = root.right;

// No child case
if(temp == null) {
temp = root;
root = null;
}
else // One child case
root = temp; // Copy the contents of the non-empty child

temp = null;
}
else {
// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node temp = minValueNode(root.right);

// Copy the inorder successor's data to this node
root.value = temp.value;

// Delete the inorder successor
root.right = deleteNode(root.right, temp.value);
}
}

// If the tree had only one node then return
if (root == null)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = Math.max(height(root.left), height(root.right)) + 1;

// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);

// Left Right Case
if (balance > 1 && getBalance(root.left) < 0) {
root.left = leftRotate(root.left);
return rightRotate(root);
}

// Right Right Case
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);

// Right Left Case
if (balance < -1 && getBalance(root.right) > 0) {
root.right = rightRotate(root.right);
return leftRotate(root);
}

return root;
}

public void print(Node root) {

if(root == null) {
System.out.println("(XXXXXX)");
return;
}

int height = root.height,
width = (int)Math.pow(2, height-1);

// Preparing variables for loop.
List<Node> current = new ArrayList<Node>(1),
next = new ArrayList<Node>(2);
current.add(root);

final int maxHalfLength = 4;
int elements = 1;

StringBuilder sb = new StringBuilder(maxHalfLength*width);
for(int i = 0; i < maxHalfLength*width; i++)
sb.append(' ');
String textBuffer;

// Iterating through height levels.
for(int i = 0; i < height; i++) {

sb.setLength(maxHalfLength * ((int)Math.pow(2, height-1-i) - 1));

// Creating spacer space indicator.
textBuffer = sb.toString();

// Print tree node elements
for(Node n : current) {

System.out.print(textBuffer);

if(n == null) {

System.out.print(" ");
next.add(null);
next.add(null);

} else {

System.out.printf("(%6d)", n.value);
next.add(n.left);
next.add(n.right);

}

System.out.print(textBuffer);

}

System.out.println();
// Print tree node extensions for next level.
if(i < height - 1) {

for(Node n : current) {

System.out.print(textBuffer);

if(n == null)
System.out.print(" ");
else
System.out.printf("%s %s",
n.left == null ? " " : "/", n.right == null ? " " : "\\");

System.out.print(textBuffer);

}

System.out.println();

}

// Renewing indicators for next run.
elements *= 2;
current = next;
next = new ArrayList<Node>(elements);

}

}

public static void main(String args[]) {
AVLTree t = new AVLTree();
Node root = null;
   /*
while (true) {
System.out.println("(1) Insert");
System.out.println("(2) Delete");

try {
BufferedReader bufferRead = new BufferedReader(new InputStreamReader(System.in));
String s = bufferRead.readLine();

if (Integer.parseInt(s) == 1) {
System.out.print("Value to be inserted: ");
root = t.insert(root, Integer.parseInt(bufferRead.readLine()));
}
else if (Integer.parseInt(s) == 2) {
System.out.print("Value to be deleted: ");
root = t.deleteNode(root, Integer.parseInt(bufferRead.readLine()));
}
else {
System.out.println("Invalid choice, try again!");
continue;
}

t.print(root);
}
catch(IOException e) {
e.printStackTrace();
}
   */
   System.out.println("Test Case 1 : ");
   root = t.insert(root, 50);
   root = t.insert(root, 40);
   root = t.insert(root, 30);
   t.print(root);

   root = t.insert(root, 70);
   root = t.insert(root, 60);
   t.print(root);
  
   root = t.insert(root, 80);
   t.print(root);

   root = t.insert(root, 90);
   t.print(root);

   System.out.println("Test Case 3 : ");
   root = t.insert(root, 30);
   root = t.insert(root, 40);
   root = t.insert(root, 35);
   t.print(root);

   root = t.insert(root, 50);
   root = t.insert(root, 45);
   t.print(root);
  
   root = t.insert(root, 38);
   t.print(root);

   root = t.insert(root, 48);
   t.print(root);
}
}
}