himport random

from queue$\_$and$\_$stack import Queue, Stack

from bst import BSTNode, BST

class AVLNode$($BSTNode$)$:

$"""$

AVL Tree Node class. Inherits from BSTNode

DO NOT CHANGE THIS CLASS IN ANY WAY

$"""$

def $\_\_$init$\_\_($self$,$ value: object$)->$ None:

$"""$

Initialize a new AVL node

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

# call $\_\_$init$\_\_()$ from parent class

super$().\_\_$init$\_\_($value$)$

# new variables needed for AVL

self.parent $=$ None

self.height $=0$

def $\_\_$str$\_\_($self$)->$ str:

$"""$

Override string method

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

return 'AVL Node: $\{\}\text{'}.$format$($self$.$value$)$

class AVL$($BST$)$:

$"""$

AVL Tree class. Inherits from BST

$"""$

def $\_\_$init$\_\_($self$,$ start$\_$tree$=$None$)->$ None:

$"""$

Initialize a new AVL Tree

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

# call $\_\_$init$\_\_()$ from parent class

super$().\_\_$init$\_\_($start$\_$tree$)$

def $\_\_$str$\_\_($self$)->$ str:

$"""$

Override string method

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

values $=[]$

super$().\_$str$\_$helper$($self$.\_$root, values$)$

return "AVL pre$-$order $\{"+",".$join$($values$)+"\}"$

def is$\_$valid$\_$avl$($self$)->$ bool:

$"""$

Perform pre$-$order traversal of the tree. Return False if there

are any problems with attributes of any of the nodes in the tree.

This is intended to be a troubleshooting 'helper' method to help

find any inconsistencies in the tree after the add$()$ or remove$()$

operations. Review the code to understand what this method is

checking and how it determines whether the AVL tree is correct.

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

stack $=$ Stack$()$

stack.push$($self$.\_$root$)$

while not stack.is$\_$empty$()$:

node $=$ stack.pop$()$

if node:

# check for correct height $($relative to children$)$

left $=$ node.left.height if node.left else $-1$

right $=$ node.right.height if node.right else $-1$

if node.height $!=1+$ max$($left$,$ right$)$:

return False

if node.parent:

# parent and child pointers are in sync

if node.value $<$ node.parent.value:

check$\_$node $=$ node.parent.left

else:

check$\_$node $=$ node.parent.right

if check$\_$node $!=$ node:

return False

else:

# NULL parent is only allowed on the root of the tree

if node $!=$ self.$\_$root:

return False

stack.push$($node$.$right$)$

stack.push$($node$.$left$)$

return True

# $------------------------------------------------------------------$ #

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

$"""$

TODO: Write your implementation

$"""$

pass

def remove$($self$,$ value: object$)->$ bool:

$"""$

TODO: Write your implementation

$"""$

pass

# Experiment and see if you can use the optional #

# subtree removal methods defined in the BST here in the AVL. #

# Call normally using self $->$ self.$\_$remove$\_$no$\_$subtrees$($parent$,$ node$)$ #

# You need to override the $\_$remove$\_$two$\_$subtrees$()$ method in any case. #

# Remove these comments. #

# Remove these method stubs if you decide not to use them. #

# Change this method in any way you'd like. #

def $\_$remove$\_$two$\_$subtrees$($self$,$ remove$\_$parent: AVLNode, remove$\_$node: AVLNode$)->$ AVLNode:

$"""$

TODO: Write your implementation

$"""$

pass

# It's highly recommended to implement #

# the following methods for balancing the AVL Tree. #

# Remove these comments. #

# Remove these method stubs if you decide not to use them. #

# Change these methods in any way you'd like. #

def $\_$balance$\_$factor$($self$,$ node: AVLNode$)->$ int:

$"""$

TODO: Write your implementation

$"""$

pass

def $\_$get$\_$height$($self$,$ node: AVLNode$)->$ int:

$"""$

TODO: Write your implementation

$"""$

pass

def $\_$rotate$\_$left$($self$,$ node: AVLNode$)->$ AVLNode:

$"""$

TODO: Write your implementation

$"""$

pass

def $\_$rotate$\_$right$($self$,$ node: AVLNode$)->$ AVLNode:

$"""$

TODO: Write your implementation

$"""$

pass

def $\_$update$\_$height$($self$,$ node: AVLNode$)->$ None:

$"""$

TODO: Write your implementation here

def $\_$rebalance$($self$,$ node: AVLNode$)->$ None:

$"""$

pass

de

$""$

TODO: Writ