`# Import necessary libraries for performance measurement, random number generation, plotting, and memory profiling.`

`#Implementing a templated Binary Search Tree data structure`

`#Implementing a templated AVL Tree data structure.`

`import time # imports time module for measuring time taken for the operations`

`import random # imports random module for generating random numbers`

`import matplotlib.pyplot as plt # imports matplotlib for plotting graphs`

`import memory_profiler # Importing the memory_profiler module to measure memory usage`

`# Class for the tree node, My Node class for BST and AVL Tree`

`class TreeNode:`

`def __init__(self, value):`

`self.value = value # Value stored in the node`

`self.left = None # Pointer to the left child`

`self.right = None # Pointer to the right child`

`self.height = 1 # Height of the node, used by AVL Tree for balancing`

`# BinarySearchTree class provides BST operations like insertion and deletion.`

`class BinarySearchTree: # my Binary Search Tree Implementation`

`def __init__(self): # Constructor`

`self.root = None # Roots node of the BST`

`def insert(self, value): # Inserts a value into the BST`

`if not self.root: # If the tree is empty, create a new node and set it as the root`

`self.root = TreeNode(value) # Create a new node and set it as the root`

`else: # If the tree is not empty, call the recursive insert method`

`self._insert_recursive(self.root, value) # Calls the recursive insert method`

`def _insert_recursive(self, node, value): # Recursive insert method`

`if value < node.value: # If the value is less than the current node value`

`if not node.left: # If the left child is empty, create a new node and set it as the left child`

`node.left = TreeNode(value) # Create a new node and set it as the left child`

`else: # If the left child is not empty, call the recursive insert method`

`self._insert_recursive(node.left, value) # Calls the recursive insert method`

`elif value > node.value: # If the value is greater than the current node value`

`if not node.right: # If the right child is empty, create a new node and set it as the right child`

`node.right = TreeNode(value) # Create a new node and set it as the right child`

`else: # If the right child is not empty, call the recursive insert method`

`self._insert_recursive(node.right, value) # Call the recursive insert method`

`# Duplicates are not inserted`

`def delete(self, node, value): # Deletes a value from the BST`

`if not node: # If the node is empty, return the node`

`return node # Returns the node`

`if value < node.value: # If the value is less than the current node value`

`node.left = self.delete(node.left, value) # Calls the recursive delete method on the left child`

`elif value > node.value: # If the value is greater than the current node value`

`node.right = self.delete(node.right, value) # Calls the recursive delete method on the right child`

`else: # If the value is equal to the current node value`

`if not node.left: # If the left child is empty`

`return node.right # Returns the right child`

`elif not node.right: # If the right child is empty`

`return node.left # Returns the left child`

`temp = self.find_min(node.right) # Finds the minimum value in the right subtree`

`node.value = temp.value # Sets the current node value to the minimum value`

`node.right = self.delete(node.right, node.value) # Calls the recursive delete method on the right child`

`return node # Returns the node`

`def find_min(self, node): # Finds the minimum value in the BST`

`while node.left: # While the left child is not empty`

`node = node.left # Sets the left child as the current node`

`return node # Returns the current node`

`# Finds the node with the maximum value in the BST.`

`def find_max(self, node):`

`current = node # Sets the current node as the input node`

`while current.right: # While the right child is not empty`

`current = current.right # Sets the right child as the current node`

`return current # Returns the current node`

`# Inorder traversal of the BST.`

`def inorder_traversal(self, node, result=None):`

`if result is None:`

`result = []`

`if node:`

`self.inorder_traversal(node.left, result)`

`result.append(node.value)`

`self.inorder_traversal(node.right, result)`

`return result`

`# Preorder traversal of the BST.`

`def preorder_traversal(self, node, result=None):`

`if result is None:`

`result = []`

`if node:`

`result.append(node.value)`

`self.preorder_traversal(node.left, result)`

`self.preorder_traversal(node.right, result)`

`return result`

`# Postorder traversal of the BST.`

`def postorder_traversal(self, node, result=None):`

`if result is None:`

`result = []`

`if node:`

`self.postorder_traversal(node.left, result)`

`self.postorder_traversal(node.right, result)`

`result.append(node.value)`

`return result`

`#`

`# BONUS - Self-Balancing (AVL) Binary Search Tree`

`# # ################################################# #`

`# AVLTree class extends BinarySearchTree with AVL balancing features.`

`class AVLTree(BinarySearchTree): # My AVL Tree Implementation`

`def insert(self, value): # Inserts a value into the AVL Tree`

`self.root = self._insert_recursive(self.root, value) # Calls the recursive insert method`

`def _insert_recursive(self, node, value): # Recursive insert method`

`if not node: # If the node is empty, create a new node and set it as the root`

`return TreeNode(value) # Creates a new node and set it as the root`

`if value < node.value: # If the value is less than the current node value`

`node.left = self._insert_recursive(node.left, value) # Calls the recursive insert method on the left child`

`elif value > node.value: # If the value is greater than the current node value`

`node.right = self._insert_recursive(node.right, value) # Calls the recursive insert method on the right child`

`else: # If the value is equal to the current node value`

`return node # Return the node`

`node.height = 1 + max(self.get_height(node.left), self.get_height(node.right)) # Updates the height of the current node`

`balance = self.get_balance(node) # Get the balance factor of the current node`

`if balance > 1 and value < node.left.value: # Left Left Case`

`return self.right_rotate(node) # Performs a right rotation`

`if balance < -1 and value > node.right.value: # Right Right Case`

`return self.left_rotate(node) # Performs a left rotation`

`if balance > 1 and value > node.left.value: # Left Right Case`

`node.left = self.left_rotate(node.left) # Performs a left rotation on the left child`

`return self.right_rotate(node) # Performs a right rotation`

`if balance < -1 and value < node.right.value: # Right Left Case`

`node.right = self.right_rotate(node.right) # Performs a right rotation on the right child`

`return self.left_rotate(node) # Performs a left rotation`

`return node # Returns the node`

`def delete(self, node, value): # Deletes a value from the AVL Tree`

`if not node: # If the node is empty, return the node`

`return node # If the node is empty, return the node`

`elif value < node.value: # If the value is less than the current node value`

`node.left = self.delete(node.left, value) # Calls the recursive delete method on the left child`

`elif value > node.value: # If the value is greater than the current node value`

`node.right = self.delete(node.right, value) # Calls the recursive delete method on the right child`

`else: # If the value is equal to the current node value`

`if not node.left: # If the left child is empty`

`temp = node.right # Sets the right child as the temporary node`

`node = None # Sets the current node as None`

`return temp # Returns the temporary node`

`elif not node.right: # If the right child is empty`

`temp = node.left # Sets the left child as the temporary node`

`node = None # Sets the current node as None`

`return temp # Returns the temporary node`

`temp = self.find_min(node.right) # Finds the minimum value in the right subtree`

`node.value = temp.value # Sets the current node value to the minimum value`

`node.right = self.delete(node.right, temp.value) # Call the recursive delete method on the right child`

`if not node: # If the node is empty, return the node`

`return node # Returns the node`

`node.height = 1 + max(self.get_height(node.left), self.get_height(node.right)) # Updates the height of the current node`

`balance = self.get_balance(node) # Gets the balance factor of the current node`

`if balance > 1 and self.get_balance(node.left) >= 0: # Left Left Case`

`return self.right_rotate(node) # Performs a right rotation`

`if balance < -1 and self.get_balance(node.right) <= 0: # Right Right Case`

`return self.left_rotate(node) # Performs a left rotation`

`if balance > 1 and self.get_balance(node.left) < 0: # Left Right Case`

`node.left = self.left_rotate(node.left) # Performs a left rotation on the left child`

`return self.right_rotate(node) # Performs a right rotation`

`if balance < -1 and self.get_balance(node.right) > 0: # Right Left Case`

`node.right = self.right_rotate(node.right) # Performs a right rotation on the right child`

`return self.left_rotate(node) # Performs a left rotation`

`return node # Returns the node`

`def left_rotate(self, node): # Left rotation method`

`y = node.right # Sets the right child as y`

`T2 = y.left`

`y.left = node # Sets the current node as the left child of y`

`node.right = T2 # Sets T2 as the right child of the current node`

`node.height = 1 + max(self.get_height(node.left), self.get_height(node.right)) # Updates the height of the current node`

`y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)) # Updates the height of y`

`return y # Returns y`

`def right_rotate(self, node): # Right rotation method`

`y = node.left # Sets the left child as y`

`T3 = y.right # Sets the right child of y as T3`

`y.right = node # Sets the current node as the right child of y`

`node.left = T3 # Sets T3 as the left child of the current node`

`node.height = 1 + max(self.get_height(node.left), self.get_height(node.right)) # Updates the height of the current node`

`y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)) # Updates the height of y`

`return y # Returns y`

`def get_height(self, node): # Gets the height of a node`

`if not node: # If the node is empty, return 0`

`return 0 # Returns 0`

`return node.height # Returns the height of the node`

`def get_balance(self, node): # Gets the balance factor of a node`

`if not node:`

`return 0`

`return self.get_height(node.left) - self.get_height(node.right) # Returns the balance factor of the node`

`#`

`# BONUS - Performance Analysis of your Binary Tree`

`# # ################################################# #`

`def measure_performance(tree_class, node_counts): # Measures the performance of the BST and AVL Tree`

`insertion_times = [] # List to store the insertion times`

`deletion_times = [] # List to store the deletion times`

`for count in node_counts: # For each number of nodes`

`tree = tree_class() # Create a new tree`

`nodes = random.sample(range(count * 10), count) # Generate a list of random numbers`

`start_time = time.time() # Start the timer`

`for node in nodes: # For each node`

`tree.insert(node) # Inserts the node into the tree`

`insertion_times.append(time.time() - start_time) # Appends the time taken to the insertion times list`

`start_time = time.time() # Starts the timer`

`for node in nodes: # For each node`

`tree.delete(tree.root, node) # Deletes the node from the tree`

`deletion_times.append(time.time() - start_time) # Appending the time taken to the deletion times list`

`return (insertion_times, deletion_times) # Returns the insertion and deletion times`

`def plot_performance(node_counts, bst_times, avl_times, operation="Insertion"): # Plots the performance of the BST and AVL Tree`

`plt.figure(figsize=(10, 5)) # Sets the figure size`

`if operation == "Insertion": # If the operation is insertion`

`plt.plot(node_counts, bst_times[0], 'o-', label='BST') # Plots the BST insertion times`

`plt.plot(node_counts, avl_times[0], 'x-', label='AVL') # Plots the AVL insertion times`

`else:`

`plt.plot(node_counts, bst_times[1], 'o-', label='BST') # Plots the BST deletion times`

`plt.plot(node_counts, avl_times[1], 'x-', label='AVL') # Plots the AVL deletion times`

`plt.xlabel('Number of Nodes') # Sets the x-axis label`

`plt.ylabel(f'Time taken for {operation} (seconds)') # Sets the y-axis label`

`plt.xscale('log') # Sets the x-axis scale to logarithmic`

`plt.yscale('log') # Sets the y-axis scale to logarithmic`

`plt.title(f'{operation} Performance: BST vs AVL (Author: Amoh Eric)' ) # Sets the title`

`plt.legend() # Shows the legend`

`plt.grid(True) # Shows the grid`

`plt.show() # Shows the plot`

`def test_avl(n): # Tests the AVL Tree`

`keys = random.sample(range(n * 10), n) # Generates a list of random numbers`

`avl = AVLTree() # Creates a new AVL Tree`

`start_time = time.time() # Starts the timer`

`for key in keys: # For each key`

`avl.insert(key) # Inserts the key into the AVL Tree`

`insert_time = time.time() - start_time # Calculates the time taken for insertion`

`start_time = time.time() # Starts the timer`

`for key in keys: # For each key`

`avl.delete(avl.root, key) # Deletes the key from the AVL Tree`

`delete_time = time.time() - start_time # Calculates the time taken for deletion`

`mem_usage = memory_profiler.memory_usage()[0] # Measures the memory usage`

`return insert_time, delete_time, mem_usage # Returns the time taken for insertion, deletion, and memory usage`

`def run_tests_avl(): # Runs tests for the AVL Tree`

`node_counts = [100, 1000, 10000, 100000] # Listings of node counts to test`

`print("Measuring performance... This may take a while for larger node counts.") # Prints a message`

`print("Please wait...") # Prints a message`

`if __name__ == '__main__': # My Main function`

`print("Welcome to the Tree Performance Comparison Tool!\n") # Prints a welcome message`

`print("This tool compares the performance of Binary Search Trees (BST) and AVL Trees.\n") # Prints a description of the tool`

`print("We will measure and plot the time taken for insertion and deletion operations for both tree types.\n") # Prints a description of the tool`

`print("Let's get started...\n") # Prints a message`

`node_counts = [100, 1000, 10000, 100000] # Listings of node counts to test # List of node counts to test`

`print("Measuring performance... This may take a while for larger node counts.\n") # Print a message`

`print("Please wait...\n") # Prints a message`

`print('AVL Tree Performance:') # Prints a message`

`print('---------------------\n') # Prints a message`

`print('| Num Nodes | Insert Time | Delete Time | Memory Usage |') # Prints a message`

`print('|-----------|---------------|-------------|--------------|') # Prints a message`

`# BONUS - Performance Analysis of your Binary Tree #`

`# ################################################# #`

`for n in node_counts: # For each number of nodes`

`total_insert_time = 0 # Sets the total insertion time to 0`

`total_delete_time = 0 # Sets the total deletion time to 0`

`total_mem_usage = 0 # Sets the total memory usage to 0`

`for i in range(10): # For each iteration`

`insert_time, delete_time, mem_usage = test_avl(n) # Measures the performance of the AVL Tree`

`total_insert_time += insert_time # Adding the insertion time to the total insertion time`

`total_delete_time += delete_time # Adds the deletion time to the total deletion time`

`total_mem_usage += mem_usage # Adds the memory usage to the total memory usage`

`# inserting_time, delete_time, mem_usage = test_avl(n)`

`# Calculates average metrics`

`avg_insert_time = total_insert_time / 5 # Calculates the average insertion time`

`avg_delete_time = total_delete_time / 5 # Calculates the average deletion time`

`avg_mem_usage = total_mem_usage / 5 # Calculates the average memory usage`

`# Prints the performance metrics for the current number of nodes`

`print(f'| {n:9d} | {insert_time:.6f} | {delete_time:.6f} | {mem_usage:10.4f} |') # Print the performance metrics for the current number of nodes`

`print() # Print a new line`

`# Measures BST performance`

`print("\nMeasuring Binary Search Tree (BST) performance...") # Print a message`

`bst_times = measure_performance(BinarySearchTree, node_counts) # Measures BST performance`

`# Measures AVL performance`

`print("\nMeasuring AVL Tree performance...") # Print a message`

`avl_times = measure_performance(AVLTree, node_counts) # Measures AVL performance`

`# Plots insertion performance`

`print("\nPlotting insertion performance comparison...") # Print a message`

`plot_performance(node_counts, bst_times, avl_times, "Insertion") # Plots the performance of the BST and AVL Tree`

`# Plots deletion performance`

`print("\nPlotting deletion performance comparison...") # Print a message`

`plot_performance(node_counts, bst_times, avl_times, "Deletion") # Plots the performance of the BST and AVL Tree`

`plot_performance(node_counts, bst_times, avl_times, "Insertion") # Plots the performance of the BST and AVL Tree`

`plot_performance(node_counts, bst_times, avl_times, "Deletion") # Plots the performance of the BST and AVL Tree`

`run_tests_avl() # Runs tests for the AVL Tree`

`print("\nThank you for using the Tree Performance Comparison Tool!") # Prints a message`

`print("For any questions or feedback, please contact the developer.") # Prints a message`