AVL Tree using JAVA : You are required to develop an AVL tree ( class AvlNode) t

Question

AVL Tree using JAVA

:

You are required to develop an AVL tree (

class AvlNode)

to support the following

operations

Find method

:

returns the node that contains the value indicated by the input

parameter;

Insert method:

insert the specified value into the AVL tree;

Remove method: remove the specified value from the AVL tree;

Inorder traversal method.

Testing data

You may test your program by do the following:

Insert 3, 2, 1, 4, 5, 6, 7, 16,

15, 14, 13, 12, 11, 10, 8, 9 into an initially empty AVL

tree, then

print the tree using Inorder traversal;

Remove 9, 6, 1, 3, then print the tree using Inorder traversal.

Explanation / Answer

import java.util.*;

/* Class AVLNode */

class AVLNode
{   
AVLNode left, right;
int data;
int height;

/* Constructor */
public AVLNode()
{
left = null;
right = null;
data = 0;
height = 0;
}
/* Constructor */
public AVLNode(int n)
{
left = null;
right = null;
data = n;
height = 0;
}
}

/* Class AVLTree */
class AVLTree
{
private AVLNode root;

/* Constructor */
public AVLTree()
{
root = null;
}
/* Function to insert data */
public void insert(int data)
{
root = insert(data, 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;
}

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

/* Function to insert data recursively */
private AVLNode insert(int x, AVLNode t)
{
if (t == null)
t = new AVLNode(x);
else if (x < t.data)
{
t.left = insert( x, t.left );
if( getBalance(t) == 2 )
if( x < t.left.data )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( x > t.data )
{
t.right = insert( x, t.right );
if( getBalance(t) == -2 )
if( x > t.right.data)
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/* 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 );
}   
/* Functions to find for an element */
public boolean find(int val)
{
return findNode(root, val);
}
private boolean findNode(AVLNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.data;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = findNode(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(AVLNode r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data +" ");
inorder(r.right);
}
}

/* Given a non-empty binary search tree, return the
node with minimum key value found in that tree.
Note that the entire tree does not need to be
searched. */
AVLNode minValueNode(AVLNode node)
{
AVLNode current = node;

/* loop down to find the leftmost leaf */
while (current.left != null)
current = current.left;

return current;
}

public void remove(int data)
{
root = removeNode(root, data);
}

private AVLNode removeNode(AVLNode root, int data)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == null)
return root;

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

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

// if data is same as root's data, then this is the node
// to be deleted
else
{

// node with only one child or no child
if ((root.left == null) || (root.right == null))
{
AVLNode temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;

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

// node with two children: Get the inorder
// successor (smallest in the right subtree)
AVLNode temp = minValueNode(root.right);

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

// Delete the inorder successor
root.right = removeNode(root.right, temp.data);
}
}

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

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = 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 rotateWithLeftChild(root);

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

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

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

return root;
}

}

class Main
{  
public static void main(String args[])
{
Scanner scan = new Scanner(System.in);
/* Creating object of AVLTree */
AVLTree avlt = new AVLTree();

System.out.println("AVLTree Tree Test ");   
char ch;
/* Perform tree operations */
do   
{
System.out.println(" AVLTree Operations ");
System.out.println("1. insert ");
System.out.println("2. find");
System.out.println("3. remove");

int choice = scan.nextInt();   
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
avlt.insert( scan.nextInt() );
/* Display tree */
System.out.print(" In order : ");
avlt.inorder();
break;   
case 2 :
System.out.println("Enter integer element to find");
System.out.println("find result : "+ avlt.find( scan.nextInt() ));
break;   
case 3 :
System.out.println(" Enter integer element to be removed");
avlt.remove( scan.nextInt() );
/* Display tree */
System.out.print(" In order : ");
avlt.inorder();
break;
default :
System.out.println("Wrong Entry ");
break;
}

System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);   
} while (ch == 'Y'|| ch == 'y');
}
}

Output:

--------

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.