Topic: AVL Tree and Red$/$Black Tree

Policy: $1)$ Each lab is due at the end of each allocated Lab Section. The TA will be available to

help you for the lab$/$homework$.$

$2)$ Exception: if you plan to do the lab in advance, you must submit your lab answer before the

start of your allocated lab section.

Instruction:

In this exercise, you are going to learn AVL tree and Red$/$Black Tree. A Node class contains key,

height, left, right, color and parent is given. Class AVLTree and RedBlackTree are also given in

the same java file.

Download the provided Java file. There is a driver program class to test. Your job is to

implement the missing methods in the AVLTree class and RedBlackTree class, respectively.

Tasks: AVLTree class: Node minValueNode$($Node node$)$ and Node maxValueNode$($Node node$)$

RedBlackTree class: Node rotateLeft$($Node node$)$ and Node rotateRight$($Node node$)$

public class Lab$4$CS$3\{$

public static void main$($String$[]$ args$)\{$

AVLTree tree $=$ new AVLTree$()$;

$/*$ Constructing tree given in the above figure $*/$

tree.root $=$ tree.insert$($tree$.$root, $20)$;

tree.root $=$ tree.insert$($tree$.$root, $10)$;

tree.root $=$ tree.insert$($tree$.$root, $40)$;

tree.root $=$ tree.insert$($tree$.$root, $25)$;

tree.root $=$ tree.insert$($tree$.$root, $30)$;

tree.root $=$ tree.insert$($tree$.$root, $35)$;

tree.root $=$ tree.insert$($tree$.$root, $45)$;

tree.root $=$ tree.insert$($tree$.$root, $50)$;

tree.root $=$ tree.insert$($tree$.$root, $15)$;

tree.root $=$ tree.insert$($tree$.$root, $5)$;

$/*$ he AVL Tree after deletion of $10$

$30$

$/\backslash$

$2040$

$/\backslash /\backslash$

$10253545$

$/\backslash \backslash$

$51550$

$*/$

System.out.println$("$Inorder traversal" $+$

$"$ of constructed tree is : $")$;

tree.inOrder$($tree$.$root$)$;

System.out.println$()$;

System.out.println$("$Maximum value in the tree is $"+$tree.maxValueNode$($tree$.$root$).$key$)$;

System.out.println$("$Minimum value in the tree is $"+$tree.minValueNode$($tree$.$root$).$key$)$;

System.out.println$("$my Red Black Tree"$)$;

$//$ let us try to insert some data into tree and try to visualize the tree as well as traverse.

RedBlackTree t $=$ new RedBlackTree$()$;

int$[]$ arr $=\{1,4,6,3,5,7,8,2,9\}$;

for$($int i$=0$;i$<9$;i$++)$

$\{$

t$.$insert$($arr$[$i$])$;

System.out.println$()$;

t$.$inorderTraversal$()$;

$\}$

$\}$

$\}$