mplement 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.$ The BST method, print$\_$tree$(),$ is inherited by the AVL class. AVL tree structures

may also be printed out by this method for testing and debugging purposes.

$7.$ 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.

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

Table of Contents Page $19$ of $27$