add a new data field named size in AVLTreeNode to store the number of nodes in the subtree rooted at this node. Note the size of a node v is one more than the sum of the sizes of its two children. In the AVLTree class, add the following method to return the kth smallest element in the tree: public E find$($int k$)//$couldnt fit avltree full code public class AVLTree$>$ extends BST $\{$

$/**$ Create an empty AVL tree $*/$

public AVLTree$()\{$

$\}$

public AVLTree$($E$[]$objects$)\{$

super$($objects$)$;

$\}$

@Override $/**$ Override createNewNode to create an AVLTreeNode $*/$

protected AVLTreeNode createNewNode$($E e$)\{$

return new AVLTreeNode$($e$)$;

$\}$

@Override $/**$ Insert an element and rebalance if necessary $*/$

public boolean insert$($E e$)\{$

boolean successful $=$ super.insert$($e$)$;

if $(!$successful$)$

return false; $//$ e is already in the tree

else$\{$

balancePath$($e$)$;

$\}$

return true;

$\}$

private void updateHeight$($AVLTreeNode node$)\{$

if$($node$.$left $==$ null && node.right $==$ null$)$

node.height $=0$;

else if $($node$.$left $==$ null$)$

node.height $=1+(($AVLTreeNode$)($node$.$right$)).$height;

else if $($node$.$right $==$ null$)$

node.height $=1+(($AVLTreeNode$)($node$.$left$)).$height;

else

node.height $=1+$

Math.max$((($AVLTreeNode$)($node$.$right$)).$height,

$(($AVLTreeNode$)($node$.$left$)).$height$)$;

$\}$

$//$ Key is not found in the tree

private void balancePath$($E e$)\{$

java.util.ArrayList$>$ path $=$ path$($e$)$;

for $($int i $=$ path.size$()-1$; i $>=0$; i$--)\{$

AVLTreeNode A $=($AVLTreeNode$)($path$.$get$($i$))$;

updateHeight$($A$)$;

AVLTreeNode parentOfA $=($A $==$ root$)?$ null :

$($AVLTreeNode$)($path$.$get$($i $-1))$;

switch $($balanceFactor$($A$))\{$

case $-2$:

if $($balanceFactor$(($AVLTreeNode$)$A$.$left$)<=0)\{$

balanceLL$($A$,$ parentOfA$)$;

$\}$

else $\{$

balanceLR$($A$,$ parentOfA$)$;

$\}$

break;

case $+2$:

if $($balanceFactor$(($AVLTreeNode$)$A$.$right$)>=0)\{$

balanceRR$($A$,$ parentOfA$)$; $//$ Perform RR rotation

$\}$

else $\{$

balanceRL$($A$,$ parentOfA$)$;

$\}$

$\}$

$\}$

$\}$

private int balanceFactor$($AVLTreeNode node$)\{$

if $($node$.$right $==$ null$)//$ node has no right subtree

return $-$node.height;

else if $($node$.$left $==$ null$)//$ node has no left subtree

return $+$node.height;

else

return $(($AVLTreeNode$)$node$.$right$).$height $-$

$(($AVLTreeNode$)$node$.$left$).$height;

$\}$

$/**$ Balance LL $($see Figure $26\mathrm{.}3)*/$

private void balanceLL$($TreeNode A$,$ TreeNode parentOfA$)\{$

TreeNode B $=$ A$.$left;

if$($A $==$ root$)\{$

root $=$ B;

$\}$

else $\{$

if $($parentOfA$.$left $==$ A$)\{$

parentOfA.left $=$ B;

$\}$

else $\{$

parentOfA.right $=$ B;

$\}$

$\}$

A$.$left $=$ B$.$right; $//$ Make T$2$ the left subtree of A

B$.$right $=$ A; $//$ Make A the left child of B

updateHeight$(($AVLTreeNode$)$A$)$;

updateHeight$(($AVLTreeNode$)$B$)$;

$\}$

private void balanceLR$($TreeNode A$,$ TreeNode parentOfA$)\{$

TreeNode B $=$ A$.$left; $//$ A is left$$heavy

TreeNode C $=$ B$.$right; $//$ B is right$$heavy

if $($A $==$ root$)\{$

root $=$ C;

$\}$

else $\{$

if $($parentOfA$.$left $==$ A$)\{$

parentOfA.left $=$ C;

$\}$

else $\{$

parentOfA.right $=$ C;

$\}$

$\}$

A$.$left $=$ C$.$right; $//$ Make T$3$ the left subtree of A

B$.$right $=$ C$.$left; $//$ Make T$2$ the right subtree of B

C$.$left $=$ B;

C$.$right $=$ A;

$//$ Adjust heights

updateHeight$(($AVLTreeNode$)$A$)$;

updateHeight$(($AVLTreeNode$)$B$)$;

updateHeight$(($AVLTreeNode$)$C$)$;

$\}$

$/**$ Balance RR $($see Figure $26\mathrm{.}4)*/$

private void balanceRR$($TreeNode A$,$ TreeNode parentOfA$)\{$

TreeNode B $=$ A$.$right; $//$ A is right$-$heavy and B is right$-$heavy

if $($A $==$ root$)\{$

root $=$ B;

$\}$

else $\{$

if $($parentOfA$.$left $==$ A$)\{$

parentOfA.left $=$ B;

$\}$

else $\{$

parentOfA.right $=$ B;

$\}$

$\}$

A$.$right $=$ B$.$left; $//$ Make T$2$ the right subtree of A

B$.$left $=$ A;

updateHeight$(($AVLTreeNode$)$A$)$;

updateHeight$(($AVLTreeNode$)$B$)$;

$\}$

private void balanceRL$($TreeNode A$,$ TreeNode parentOfA$)\{$

TreeNode B $=$ A$.$right; $//$ A is right$-$heavy

TreeNode C $=$ B$.$left; $//$ B is left$-$heavy

if $($A $==$ root$)\{$

root $=$ C;

$\}$

else $\{$

if $($parentOfA$.$left $==$ A$)\{$

parentOfA.left $=$ C;

$\}$

else $\{$

parentOfA.right $=$ C;

$\}$

$\}$

A$.$right $=$ C$.$left; $//$ Make T$2$ the right subtree of A

B$.$left $=$ C$.$right; $//$ Make T$3$ the left subtree of B

C$.$left $=$ A;

C$.$right $=$ B;

updateHeight$(($AVLTreeNode$)$A$)$;

updateHeight$(($AVLTreeNode$)$B$)$;

updateHeight$(($AVLTreeNode$)$C$)$;

$\}$

@Override $/**$ Delete an element from the AVL tree.

$*$ Return true if the element is deleted successfully

$*$ Return false if the element is not in the tree $*/$

public boolean delete$($E element$)\{$

if $($root $==$ null$)$

return false; $//$ Element is not in the tree

$//$ Locate the node to be deleted and also locate its parent node

TreeNode parent $=$ null;

TreeNode current $=$ root;

while $($current $!=$ null$)\{$

if $($element$.$compareTo$($current$.$element$)<0)\{$