add$($self$,$ value: object$)->$ None:

This method adds a new value to the tree while maintaining its AVL property. Duplicate

values are not allowed. If the value is already in the tree, the method should not change

the tree. It must be implemented with $O(logN)$ runtime complexity.

Example #$1$:

test$\_$cases

$(1,2,3),$

#RR

$(3,2,1),$

#LL

$(1,3,2),$

#RL

$(3,1,2),$

#LR

for case in test$\_$cases:

tree $=$ AVL $($case$)$

print $($tree$)$

output:

AVL pre$-$order $\{2,1,3\}$

AVL pre$-$order $\{2,1,3\}$

AVL pre$-$order $\{2,1,3\}$

AVL pre$-$order $\{2,1,3\}$Example #$2$:

test$\_$cases $=1$

$(10,20,30,40,50),$#$RR,RR$

$(10,20,30,50,40),$#$RR,RL$

$(30,20,10,5,1),$ # LL$,$ LL

$(30,20,10,1,5),$ # LL$,$ LR

$(5,4,6,3,7,2,8),$ # LL$,$ RR

$($range $(0,30,3),$

$($range $(0,31,3),$

$($range $(0,34,3),$

$($range $(10,-10,-2)),$

$(\text{'}$A$\text{'},\text{'}$B$\text{'},\text{'}$C$\text{'},\text{'}$D$\text{'},\text{'}$E$\text{'}),$

$(1,1,1,1),$

for case in test$\_$cases:

tree $=$ AVL $($case$)$

print$(\text{'}$INPUT :$\text{'},$ case$)$

print $(\text{'}$RESULT :$\text{'},$ tree$)$

Qutput:

INPUT : $(10,20,30,40,50)$

RESULT : AVL pre$-$order $\{20,10,40,30,50\}$

INPUT : $(10,20,30,50,40)$

RESULT : AVL pre$-$order $\{20,10,40,30,50\}$

INPUT : $(30,20,10,5,1)$

RESULT : AVL pre$-$order $\{20,5,1,10,30\}$

INPUT : $(30,20,10,1,5)$

RESULT : AVL pre$-$order $\{20,5,1,10,30\}$

INPUT : $(5,4,6,3,7,2,8)$

RESULT : AVL pre$-$order $\{5,3,2,4,7,6,8\}$

INPUT : range $(0,30,3)$

RESULT : AVL pre$-$order $\{9,3,0,6,21,15,12,18,24,27\}$

INPUT : range $(0,31,3)$

RESULT : AVL pre$-$order $\{9,3,0,6,21,15,12,18,27,24,30\}$

INPUT : range $(0,34,3)$

RESULT : AVL pre$-$order $\{21,9,3,0,6,15,12,18,27,24,30,33\}$

INPUT : range $(10,-10,-2)$

RESULT : AVL pre$-$order $\{4,-4,-6,-8,0,-2,2,8,6,10\}$

INPUT : $(\text{'}$A$\text{'},\text{'}$B$\text{'},\text{'}$C$\text{'},\text{'}$D$\text{'},\text{'}$E$\text{'})$

RESULT : AVL pre$-$order $\{$ B$,$ A$,$ D$,$ C$,$ E $\}$

INPUT : $(1,1,1,1)$

RESULT : AVL pre$-$order $\{1\}$Example #$3$:

for $\_$ in range $(100)$:

case $=$ list $($set $($random$.$randrange $(1,20000)$ for $\_$ in range$(900)))$

tree $=$ AVL $()$

for value in case:

tree.add $($value$)$

if not tree.is$\_$valid$\_$avl$()$:

raise Exception$("$PROBLEM WITH ADD OPERATION"$)$

print$(\text{'}$add$()$ stress test finished'$)$

Output:

add$()$ stress test finishedremove$($self$,$ value: object$)->$ bool:

This method removes the value from the AVL tree. The method returns True if the value is

removed. Otherwise, it returns False. It must be implemented with $O(logN)$ runtime

complexity.

NOTE: See 'Specific Instructions' for an explanation of which node replaces the deleted

node.

Example #$1$:

test$\_$cases

$((1,2,3),1),$ # no AVL rotation

$((1,2,3),2),$ # no AVL rotation

$((1,2,3),3),$ # no AVL rotation

$((50,40,60,30,70,20,80,45),0),$

$((50,40,60,30,70,20,80,45),45),$ # no AVL rotation

$((50,40,60,30,70,20,80,45),40),$ no AVL rotation

$((50,40,60,30,70,20,80,45),30),$ # no AVL rotation

for case, del$\_$value in test$\_$cases:

tree $=$ AVL $($case$)$

print$(\text{'}$INPUT :$\text{'},$ tree, "DELETE:", del$\_$value$)$

tree.remove $($del$\_$value$)$

print $(\text{'}$RESULT :$\text{'},$ tree$)$

Output:

INPUT : AVL pre$-$order $\{2,1,3\}$ DEL: $1$

RESULT : AVL pre$-$order $\{2,3\}$

INPUT : AVL pre$-$order $\{2,1,3\}$ DEL: $2$

RESULT : AVL pre$-$order $\{3,1\}$

INPUT : AVL pre$-$order $\{2,1,3\}$ DEL: $3$

RESULT : AVL pre$-$order $\{2,1\}$

INPUT : AVL pre$-$order $\{50,30,20,40,45,70,60,80\}$ DEL: $0$

RESULT : AVL pre$-$order $\{50,30,20,40,45,70,60,80\}$

INPUT : AVL pre$-$order $\{50,30,20,40,45,70,60,80\}$ DEL: $45$

RESULT : AVL pre$-$ordeExample #$2$:

test$\_$cases Example #$3$