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