public class AVLTree$>$ extends BST $\{$

protected int height;

public AVLTree$()\{$

super$()$;

height $=-1$;

$\}$

public AVLTree$($BSTNode root$)\{$

super$($root$)$;

height $=-1$;

$\}$

public int getHeight$()\{$

return getHeight$($root$)$;

$\}$

private int getHeight$($BSTNode node$)\{$

if$($node $==$ null$)$

return $-1$;

else

return $1+$ Math.max$($getHeight$($node$.$left$),$ getHeight$($node$.$right$))$;

$\}$

private AVLTree getLeftAVL$()\{$

AVLTree leftsubtree $=$ new AVLTree$($root$.$left$)$;

return leftsubtree;

$\}$

private AVLTree getRightAVL$()\{$

AVLTree rightsubtree $=$ new AVLTree$($root$.$right$)$;

return rightsubtree;

$\}$

protected int getBalanceFactor$()\{$

if$($isEmpty$())$

return $0$;

else

return getRightAVL$().$getHeight$()-$ getLeftAVL$().$getHeight$()$;

$\}$

public void insertAVL$($T el$)\{$

super.insert$($el$)$;

this.balance$()$;

$\}$

public void deleteAVL$($T el$)\{$

$//$Q$1$

$\}$

protected void balance$()$

$\{$

if$(!$isEmpty$())$

$\{$

getLeftAVL$().$balance$()$;

getRightAVL$().$balance$()$;

adjustHeight$()$;

int balanceFactor $=$ getBalanceFactor$()$;

if$($balanceFactor $==-2)\{$

System.out.println$("$Balancing node with el: $"+$root.el$)$;

if$($getLeftAVL$().$getBalanceFactor$()<mtext\; id="EditorElement\_797471"></mtext><mn\; id="EditorElement\_797472">0</mn><mi\; id="EditorElement\_797473">)</mi>$

rotateRight$()$;

else

rotateLeftRight$()$;

$\}$

else if$($balanceFactor $==2)\{$

System.out.println$("$Balancing node with el: $"+$root.el$)$;

if$($getRightAVL$().$getBalanceFactor$()>0)$

rotateLeft$()$;

else

rotateRightLeft$()$;

$\}$

$\}$

$\}$

protected void adjustHeight$()$

$\{$

if$($isEmpty$())$

height $=-1$;

else

height $=1+$ Math.max$($getLeftAVL$().$getHeight$(),$ getRightAVL$().$getHeight$())$;

$\}$

protected void rotateRight$()\{$

System.out.println$("$RIGHT ROTATION"$)$;

$//$Q$1$

$\}$

protected void rotateLeft$()\{$

System.out.println$("$LEFT ROTATION"$)$;

BSTNode tempNode $=$ root.left;

root.left $=$ root.right;

root.right $=$ root.left.right;

root.left.right $=$ root.left.left;

root.left.left $=$ tempNode;

T val $=($T$)$ root.el;

root.el $=$ root.left.el;

root.left.el $=$ val;

getLeftAVL$().$adjustHeight$()$;

adjustHeight$()$;

$\}$

protected void rotateLeftRight$()$

$\{$

System.out.println$("$Double Rotation..."$)$;

$//$Q$1$

$\}$

protected void rotateRightLeft$()$

$\{$

System.out.println$("$Double Rotation..."$)$;

getRightAVL$().$rotateRight$()$;

getRightAVL$().$adjustHeight$()$;

this.rotateLeft$()$;

this.adjustHeight$()$;

$\}$

$\}.............................................................................$ Objectives

The objective of this lab is to design, implement and use AVL trees.

Outcomes

After completing this Lab, students are expected to:

Design classes for AVL trees.

Delete from AVL trees.

Notes

For the purpose of this lab, you may download the attached programs.

Lab Exercises

Complete the class AVLTree that extends BST$.$ It should have four methods RotateLeft,

RotateRight, RotateLeftRight, and RotateRightLeft. You have to provide the methods

rotateRight$(),$ and rotateRightLeft. Provide the method deleteAVL$($T el$)$ to delete

elements in the AVL tree. Note that the BST class for AVL trees has been modified to have

an extra constructor.

Create an AVL tree in which the following keys are inserted in the given order:

$8,14,12,18,23,20,15,13,7,16$

Print the resulting AVL tree in BFS$.$ Your BFS result should correspond to the following

AVL Tree:

Now ask the user to provide any $3$ elements to delete. After deleting the elements, print the

BFS of the AVL tree again.

Create an AVL tree of strings. Test your program on the given text file $($sampletextfile$.$txt$).$

After creating the AVLTree of strings, print the AVLTree using inorder traversal. $[$Note:

Do not insert duplicate words in your AVL tree$]$ Stack Queue and BST$,$ BSTnode are provided