Please help implement the AVL class by completing the functions and following the instructions commented in the code:

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

#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: """ Method adds new value to tree while maintaining its AVL property Duplicate values are not allowed. If value is already in tree, method should not change the tree Implement with 0(log N) runtime complexity """ pass def remove(self, value: object) -> bool: """ Method removes value from the AVL tree. Returns True if the value removed, otherwise False 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: """ balance 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