Complete the python program by implementing an AVL class and completing the functions and following the instructions commented in the code of avl.py:

-------------------------------------------------------------------------------------------------------------------------------------------

#avl.py

import 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: {}'.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. 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: """ Adding a new value to tree while maintaining its AVL property """ def recursive_add(node, value): if node is None: node = AVLNode(value) elif value < node.value: node.left = recursive_add(node.left, value) node.left.parent = node elif value > node.value: node.right = recursive_add(node.right, value)

 def remove(self, value: object) -> bool: """ Method to remove value from AVL tree. Returns True is value removed Return False otherwise. Implement with 0(log N) runtime complexity """ pass

 def _remove_two_subtrees(self, remove_parent: AVLNode, remove_node: AVLNode) -> AVLNode: """ remove two subtrees """ pass 

 def _balance_factor(self, node: AVLNode) -> int: """ Method to balance the AVL tree """ pass def _get_height(self, node: AVLNode) -> int: """ Method to get the tree height """ pass def _rotate_left(self, node: AVLNode) -> AVLNode: """ Rotate left within the AVL Tree """ pass def _rotate_right(self, node: AVLNode) -> AVLNode: """ Rotate right within the AVL Tree """ pass def _update_height(self, node: AVLNode) -> None: """ Update the trees height """ pass def _rebalance(self, node: AVLNode) -> None: """ Rebalance the tree """ pass

--------------------------------------------------------------------------------------------------------------------------------

#queue_and_stack.py

class Queue: """ Class implementing QUEUE ADT. Supported methods are: enqueue, dequeue, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self): """Initialize empty queue based on Python list.""" self._data = [] def enqueue(self, value: object) -> None: """Add new element to the end of the queue.""" self._data.append(value) def dequeue(self): """Remove element from the beginning of the queue and return its value.""" return self._data.pop(0) def is_empty(self) -> bool: """Return True if the queue is empty, return False otherwise.""" return len(self._data) == 0 def __str__(self) -> str: """Return content of the queue as a string (for use with print).""" data_str = [str(item) for item in self._data] return "QUEUE { " + ", ".join(data_str) + " }" class Stack: """ Class implementing STACK ADT. Supported methods are: push, pop, top, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self): """Initialize empty stack based on Python list.""" self._data = [] def push(self, value: object) -> None: """Add new element on top of the stack.""" self._data.append(value) def pop(self): """Remove element from top of the stack and return its value.""" return self._data.pop() def top(self): """Return value of top element without removing from stack.""" return self._data[-1] def is_empty(self) -> bool: """Return True if the stack is empty, return False otherwise.""" return len(self._data) == 0 def __str__(self) -> str: """Return content of the stack as a string (for use with print).""" data_str = [str(item) for item in self._data] return "STACK: { " + ", ".join(data_str) + " }"

-------------------------------------------------------------------------------------------------------------------------------------

#bst.py

import random from queue_and_stack import Queue, Stack from typing import Optional, Tuple class BSTNode: """ Binary Search Tree Node class DO NOT CHANGE THIS CLASS IN ANY WAY """ def __init__(self, value: object) -> None: """ Initialize a new BST node DO NOT CHANGE THIS METHOD IN ANY WAY """ self.value = value # to store node's data self.left = None # pointer to root of left subtree self.right = None # pointer to root of right subtree def __str__(self) -> str: """ Override string method DO NOT CHANGE THIS METHOD IN ANY WAY """ return 'BST Node: {}'.format(self.value) class BST: """ Binary Search Tree class """ def __init__(self, start_tree=None) -> None: """ Initialize new Binary Search Tree DO NOT CHANGE THIS METHOD IN ANY WAY """ self._root = None # populate BST with initial values (if provided) # before using this feature, implement add() method if start_tree is not None: for value in start_tree: self.add(value) def __str__(self) -> str: """ Override string method; display in pre-order DO NOT CHANGE THIS METHOD IN ANY WAY """ values = [] self._str_helper(self._root, values) return "BST pre-order { " + ", ".join(values) + " }" def _str_helper(self, node: BSTNode, values: []) -> None: """ Helper method for __str__. Does pre-order tree traversal DO NOT CHANGE THIS METHOD IN ANY WAY """ if not node: return values.append(str(node.value)) self._str_helper(node.left, values) self._str_helper(node.right, values) def get_root(self) -> BSTNode: """ Return root of tree, or None if empty DO NOT CHANGE THIS METHOD IN ANY WAY """ return self._root def is_valid_bst(self) -> bool: """ Perform pre-order traversal of the tree. Return False if nodes don't adhere to the bst ordering property. This is intended to be a troubleshooting method to help find any inconsistencies in the tree after the add() or remove() operations. A return of True from this method doesn't guarantee that your tree is the 'correct' result, just that it satisfies bst ordering. DO NOT CHANGE THIS METHOD IN ANY WAY """ stack = Stack() stack.push(self._root) while not stack.is_empty(): node = stack.pop() if node: if node.left and node.left.value >= node.value: return False if node.right and node.right.value < node.value: return False stack.push(node.right) stack.push(node.left) return True