Part $2-$ Summary and Specific Instructions

$1.$ Implement the AVL class $($a subclass of BST$)$ by completing the provided skeleton

code in the file avl.py$.$ Once completed, your implementation will include overridden

version of the following methods:

add$(),$ remove$()$

And it will inherit the following methods from BST:

contains$(),$ inorder$\_$traversal$(),$

find$\_$min$(),$ find$\_$max$()$

is$\_$empty$(),$ make$\_$empty$()$

$2.$ When reviewing the provided skeleton code, please note that the AVLNode class $($a

subclass of BSTNode$)$ has two important added attributes: parent $($to store a pointer

to the parent of the current node$)$ and height $($to store the height of the subtree

rooted at the current node$).$ Your implementation must correctly maintain all three

node pointers $($left$,$ right, and parent$),$ as well as the height attribute of each

node. Your tree must use the AVLNode class.

$3.$ The number of objects stored in the tree will be between $0$ and $900$ inclusive.

$4.$ When removing a node with two subtrees, replace it with the leftmost child

of the right subtree $($i$.$e$.$ the inorder successor$).$ You do not need to recursively

continue this process. If the deleted node only has one subtree $($either right or left$),$

replace the deleted node with the root node of that subtree.

$5.$ The variables in AVLNode are not private. You are allowed to access and change

their values directly. You do not need to write any getter or setter methods for them.

The AVL skeleton code includes some suggested helper methods.

$6.$ RESTRICTIONS: You are NOT allowed to use ANY built$-$in Python data structures

and$/$or their methods. Your solutions should not call double underscore $($dunder$)$

methods. In case you need $$helper$$ data structures in your solution, the skeleton

code includes prewritten implementations of Queue and Stack classes, which are in

separate files and imported in bst$.$py and avl.py$.$ You are allowed to create and use

objects from those classes in your implementation.

You are NOT allowed to directly access any variables of the Queue or Stack classes.

All work must be done only by using class methods.

$7.$ Ensure that your methods meet the specified runtime requirements.

Table of Contents Page $17$ of $24$

CS$261$ Data Structures Assignment $4$: BST$/$AVL Tree Implementation

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$($log N$)$ 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\}$

Page $18$ of $24$

CS$261$ Data Structures Assignment $4$: BST$/$AVL Tree Implementation

Example #$2$:

test$\_$cases $=($

$(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$)$

Output:

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\}$

Table of Contents Page $19$ of $24$

CS$261$ Data Structures Assignment $4$: BST$/$AVL Tree Implementation

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 finished

Page $20$ of $24$

CS$261$ Data Structures Assignment $4$: BST$/$AVL Tree Implementation

remove$($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$($log N$)$ runtime

complexity.

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

node.

Example #

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

$"""$

TODO: Write your implementation

$"""$

pass