Create A Program to Implement Trees in Python Assignment Solution

Instructions

Objective

Write a python assignment program to implement trees.

Requirements and Specifications

Source Code

AVL # Name: # OSU Email: # Course: CS261 - Data Structures # Assignment: # Due Date: # Description: 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: """ Overrides 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 DO NOT CHANGE THIS CLASS IN ANY WAY """ 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: """ Return content of AVL in human-readable form 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: if self.root is None: new_node = AVLNode(value) new_node.height = 1 self.root = new_node else: self.__add_step(self.root, value) def __add_step(self, curr, value): if curr.value > value: if curr.left is None: new_node = AVLNode(value) curr.left = new_node new_node.parent = curr else: self.__add_step(curr.left, value) elif curr.value < value: if curr.right is None: new_node = AVLNode(value) curr.right = new_node new_node.parent = curr else: self.__add_step(curr.right, value) else: return self.update_height(curr) if abs(self.balance_factor(curr)) > 1: self.rebalance(curr) def remove(self, value: object) -> bool: if self.root is None: return False return self.__remove_step(self.root, value) def __remove_step(self, curr, value): if curr is None: return False if curr.value > value: self.__remove_step(curr.left, value) elif curr.value < value: self.__remove_step(curr.right, value) else: parent = curr.parent if curr.left is None: if curr.right is not None: curr.right.parent = parent if parent is None: self.root = curr.right elif parent.left == curr: parent.left = curr.right else: parent.right = curr.right elif curr.right is None: if curr.left is not None: curr.left.parent = parent if parent is None: self.root = curr.left elif parent.left == curr: parent.left = curr.left else: parent.right = curr.left else: left_most = curr.right while left_most.left is not None: left_most = left_most.left curr.value = left_most.value self.__remove_step(curr.right, curr.value) self.update_height(curr) if abs(self.balance_factor(curr)) > 1: self.rebalance(curr) return True # ------------------------------------------------------------------ # ################################################################ # It's highly recommended, though not required, # to implement these methods for balancing the AVL Tree. ################################################################ def balance_factor(self, curr): if curr is None: return 0 lh = -1 if curr.left is not None: lh = curr.left.height rh = -1 if curr.right is not None: rh = curr.right.height return rh - lh def update_height(self, curr): if curr is None: return lh = -1 if curr.left is not None: lh = curr.left.height rh = -1 if curr.right is not None: rh = curr.right.height curr.height = 1 + max(lh, rh) def rotate_left(self, curr): r_node = curr.right curr.right = r_node.left if r_node.left is not None: r_node.left.parent = curr r_node.parent = curr.parent if curr.parent is None: self.root = r_node elif curr == curr.parent.left: curr.parent.left = r_node else: curr.parent.right = r_node r_node.left = curr curr.parent = r_node self.update_height(curr) self.update_height(r_node) def rotate_right(self, curr): l_node = curr.left curr.left = l_node.right if l_node.right is not None: l_node.right.parent = curr l_node.parent = curr.parent if curr.parent is None: self.root = l_node elif curr == curr.parent.right: curr.parent.right = l_node else: curr.parent.left = l_node l_node.right = curr curr.parent = l_node self.update_height(curr) self.update_height(l_node) def rebalance(self, curr): if curr is None: return bf = self.balance_factor(curr) if bf > 0: if self.balance_factor(curr.right) < 0: self.rotate_right(curr.right) self.rotate_left(curr) else: self.rotate_left(curr) elif bf < 0: if self.balance_factor(curr.left) > 0: self.rotate_left(curr.left) self.rotate_right(curr) else: self.rotate_right(curr) # ------------------------------------------------------------------ # ################################################################ # Use the methods as a starting point if you'd like to override. # Otherwise, the AVL can simply call any BST method. ################################################################ ''' def contains(self, value: object) -> bool: """ TODO: Write your implementation """ return super().contains(value) def inorder_traversal(self) -> Queue: """ TODO: Write your implementation """ return super().inorder_traversal() def find_min(self) -> object: """ TODO: Write your implementation """ return super().find_min() def find_max(self) -> object: """ TODO: Write your implementation """ return super().find_max() def is_empty(self) -> bool: """ TODO: Write your implementation """ return super().is_empty() def make_empty(self) -> None: """ TODO: Write your implementation """ super().make_empty() ''' # ------------------- BASIC TESTING ----------------------------------------- if __name__ == '__main__': print("\nPDF - method add() example 1") print("----------------------------") test_cases = ( (1, 2, 3), # RR (3, 2, 1), # LL (1, 3, 2), # RL (3, 1, 2), # LR ) for case in test_cases: tree = AVL(case) print(tree) print("\nPDF - method add() example 2") print("----------------------------") test_cases = ( (10, 20, 30, 40, 50), # RR, RR (10, 20, 30, 50, 40), # RR, RL (30, 20, 10, 5, 1), # LL, LL (30, 20, 10, 1, 5), # LL, LR (5, 4, 6, 3, 7, 2, 8), # LL, RR (range(0, 30, 3)), (range(0, 31, 3)), (range(0, 34, 3)), (range(10, -10, -2)), ('A', 'B', 'C', 'D', 'E'), (1, 1, 1, 1), ) for case in test_cases: tree = AVL(case) print('INPUT :', case) print('RESULT :', tree) print("\nPDF - method add() example 3") print("----------------------------") for _ in range(100): case = list(set(random.randrange(1, 20000) for _ in range(900))) tree = AVL() for value in case: tree.add(value) if not tree.is_valid_avl(): raise Exception("PROBLEM WITH ADD OPERATION") print('add() stress test finished') print("\nPDF - method remove() example 1") print("-------------------------------") test_cases = ( ((1, 2, 3), 1), # no AVL rotation ((1, 2, 3), 2), # no AVL rotation ((1, 2, 3), 3), # no AVL rotation ((50, 40, 60, 30, 70, 20, 80, 45), 0), ((50, 40, 60, 30, 70, 20, 80, 45), 45), # no AVL rotation ((50, 40, 60, 30, 70, 20, 80, 45), 40), # no AVL rotation ((50, 40, 60, 30, 70, 20, 80, 45), 30), # no AVL rotation ) for case, del_value in test_cases: tree = AVL(case) print('INPUT :', tree, "DEL:", del_value) tree.remove(del_value) print('RESULT :', tree) print("\nPDF - method remove() example 2") print("-------------------------------") test_cases = ( ((50, 40, 60, 30, 70, 20, 80, 45), 20), # RR ((50, 40, 60, 30, 70, 20, 80, 15), 40), # LL ((50, 40, 60, 30, 70, 20, 80, 35), 20), # RL ((50, 40, 60, 30, 70, 20, 80, 25), 40), # LR ) for case, del_value in test_cases: tree = AVL(case) print('INPUT :', tree, "DEL:", del_value) tree.remove(del_value) print('RESULT :', tree) print("\nPDF - method remove() example 3") print("-------------------------------") case = range(-9, 16, 2) tree = AVL(case) for del_value in case: print('INPUT :', tree, del_value) tree.remove(del_value) print('RESULT :', tree) print("\nPDF - method remove() example 4") print("-------------------------------") case = range(0, 34, 3) tree = AVL(case) for _ in case[:-2]: print('INPUT :', tree, tree.root.value) tree.remove(tree.root.value) print('RESULT :', tree) print("\nPDF - method remove() example 5") print("-------------------------------") for _ in range(100): case = list(set(random.randrange(1, 20000) for _ in range(900))) tree = AVL(case) for value in case[::2]: tree.remove(value) if not tree.is_valid_avl(): raise Exception("PROBLEM WITH REMOVE OPERATION") print('remove() stress test finished') print("\nPDF - method contains() example 1") print("---------------------------------") tree = AVL([10, 5, 15]) print(tree.contains(15)) print(tree.contains(-10)) print(tree.contains(15)) print("\nPDF - method contains() example 2") print("---------------------------------") tree = AVL() print(tree.contains(0)) print("\nPDF - method inorder_traversal() example 1") print("---------------------------------") tree = AVL([10, 20, 5, 15, 17, 7, 12]) print(tree.inorder_traversal()) print("\nPDF - method inorder_traversal() example 2") print("---------------------------------") tree = AVL([8, 10, -4, 5, -1]) print(tree.inorder_traversal()) print("\nPDF - method find_min() example 1") print("---------------------------------") tree = AVL([10, 20, 5, 15, 17, 7, 12]) print(tree) print("Minimum value is:", tree.find_min()) print("\nPDF - method find_min() example 2") print("---------------------------------") tree = AVL([8, 10, -4, 5, -1]) print(tree) print("Minimum value is:", tree.find_min()) print("\nPDF - method find_max() example 1") print("---------------------------------") tree = AVL([10, 20, 5, 15, 17, 7, 12]) print(tree) print("Maximum value is:", tree.find_max()) print("\nPDF - method find_max() example 2") print("---------------------------------") tree = AVL([8, 10, -4, 5, -1]) print(tree) print("Maximum value is:", tree.find_max()) print("\nPDF - method is_empty() example 1") print("---------------------------------") tree = AVL([10, 20, 5, 15, 17, 7, 12]) print("Tree is empty:", tree.is_empty()) print("\nPDF - method is_empty() example 2") print("---------------------------------") tree = AVL() print("Tree is empty:", tree.is_empty()) print("\nPDF - method make_empty() example 1") print("---------------------------------") tree = AVL([10, 20, 5, 15, 17, 7, 12]) print("Tree before make_empty():", tree) tree.make_empty() print("Tree after make_empty(): ", tree) print("\nPDF - method make_empty() example 2") print("---------------------------------") tree = AVL() print("Tree before make_empty():", tree) tree.make_empty() print("Tree after make_empty(): ", tree) BST import random from queue_and_stack import Queue, Stack 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: """ Overrides string method DO NOT CHANGE THIS METHOD IN ANY WAY """ return 'BST Node: {}'.format(self.value) class BST: """ Binary Search Tree class DO NOT CHANGE THIS CLASS IN ANY WAY """ 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: """ Return content of BST in human-readable form using pre-order traversal 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 add(self, value: object) -> None: new_node = BSTNode(value) if self.root is None: self.root = new_node return curr = self.root while True: curr_val = curr.value if curr_val <= value: if curr.right is None: curr.right = new_node return else: curr = curr.right elif curr_val > value: if curr.left is None: curr.left = new_node return else: curr = curr.left else: return def remove(self, value: object) -> bool: curr = self.root parent = None while True: if curr is None: return False curr_val = curr.value if curr_val < value: parent = curr curr = curr.right elif curr_val > value: parent = curr curr = curr.left else: break if curr.left is None: if parent is None: self.root = curr.right elif parent.left == curr: parent.left = curr.right else: parent.right = curr.right elif curr.right is None: if parent is None: self.root = curr.left elif parent.left == curr: parent.left = curr.left else: parent.right = curr.left else: left_most = curr.right if left_most.left is None: left_most.left = curr.left else: lp = left_most left_most = left_most.left while left_most.left is not None: lp = left_most left_most = left_most.left lp.left = left_most.right left_most.right = curr.right left_most.left = curr.left if parent is None: self.root = left_most elif parent.left == curr: parent.left = left_most else: parent.right = left_most return True def contains(self, value: object) -> bool: curr = self.root while True: if curr is None: return False curr_val = curr.value if curr_val < value: curr = curr.right elif curr_val > value: curr = curr.left else: return True def inorder_traversal(self) -> Queue: q = Queue() self.__inorder_step(self.root, q) return q def __inorder_step(self, curr, queue): if curr is None: return self.__inorder_step(curr.left, queue) queue.enqueue(curr.value) self.__inorder_step(curr.right, queue) def find_min(self) -> object: if self.is_empty(): return None curr = self.root while curr.left is not None: curr = curr.left return curr.value def find_max(self) -> object: if self.is_empty(): return None curr = self.root while curr.right is not None: curr = curr.right return curr.value def is_empty(self) -> bool: return self.root is None def make_empty(self) -> None: self.root = None # ------------------- BASIC TESTING ----------------------------------------- if __name__ == '__main__': print("\nPDF - method add() example 1") print("----------------------------") test_cases = ( (1, 2, 3), (3, 2, 1), (1, 3, 2), (3, 1, 2), ) for case in test_cases: tree = BST(case) print(tree) print("\nPDF - method add() example 2") print("----------------------------") test_cases = ( (10, 20, 30, 40, 50), (10, 20, 30, 50, 40), (30, 20, 10, 5, 1), (30, 20, 10, 1, 5), (5, 4, 6, 3, 7, 2, 8), (range(0, 30, 3)), (range(0, 31, 3)), (range(0, 34, 3)), (range(10, -10, -2)), ('A', 'B', 'C', 'D', 'E'), (1, 1, 1, 1), ) for case in test_cases: tree = BST(case) print('INPUT :', case) print('RESULT :', tree) print("\nPDF - method add() example 3") print("----------------------------") for _ in range(100): case = list(set(random.randrange(1, 20000) for _ in range(900))) tree = BST() for value in case: tree.add(value) print('add() stress test finished') print("\nPDF - method remove() example 1") print("-------------------------------") test_cases = ( ((1, 2, 3), 1), ((1, 2, 3), 2), ((1, 2, 3), 3), ((50, 40, 60, 30, 70, 20, 80, 45), 0), ((50, 40, 60, 30, 70, 20, 80, 45), 45), ((50, 40, 60, 30, 70, 20, 80, 45), 40), ((50, 40, 60, 30, 70, 20, 80, 45), 30), ) for case, del_value in test_cases: tree = BST(case) print('INPUT :', tree, "DEL:", del_value) tree.remove(del_value) print('RESULT :', tree) print("\nPDF - method remove() example 2") print("-------------------------------") test_cases = ( ((50, 40, 60, 30, 70, 20, 80, 45), 20), ((50, 40, 60, 30, 70, 20, 80, 15), 40), ((50, 40, 60, 30, 70, 20, 80, 35), 20), ((50, 40, 60, 30, 70, 20, 80, 25), 40), ) for case, del_value in test_cases: tree = BST(case) print('INPUT :', tree, "DEL:", del_value) tree.remove(del_value) print('RESULT :', tree) print("\nPDF - method remove() example 3") print("-------------------------------") case = range(-9, 16, 2) tree = BST(case) for del_value in case: print('INPUT :', tree, del_value) tree.remove(del_value) print('RESULT :', tree) print("\nPDF - method remove() example 4") print("-------------------------------") case = range(0, 34, 3) tree = BST(case) for _ in case[:-2]: print('INPUT :', tree, tree.root.value) tree.remove(tree.root.value) print('RESULT :', tree) print("\nPDF - method contains() example 1") print("---------------------------------") tree = BST([10, 5, 15]) print(tree.contains(15)) print(tree.contains(-10)) print(tree.contains(15)) print("\nPDF - method contains() example 2") print("---------------------------------") tree = BST() print(tree.contains(0)) print("\nPDF - method inorder_traversal() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree.inorder_traversal()) print("\nPDF - method inorder_traversal() example 2") print("---------------------------------") tree = BST([8, 10, -4, 5, -1]) print(tree.inorder_traversal()) print("\nPDF - method find_min() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree) print("Minimum value is:", tree.find_min()) print("\nPDF - method find_min() example 2") print("---------------------------------") tree = BST([8, 10, -4, 5, -1]) print(tree) print("Minimum value is:", tree.find_min()) print("\nPDF - method find_max() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree) print("Maximum value is:", tree.find_max()) print("\nPDF - method find_max() example 2") print("---------------------------------") tree = BST([8, 10, -4, 5, -1]) print(tree) print("Maximum value is:", tree.find_max()) print("\nPDF - method is_empty() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print("Tree is empty:", tree.is_empty()) print("\nPDF - method is_empty() example 2") print("---------------------------------") tree = BST() print("Tree is empty:", tree.is_empty()) print("\nPDF - method make_empty() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print("Tree before make_empty():", tree) tree.make_empty() print("Tree after make_empty(): ", tree) print("\nPDF - method make_empty() example 2") print("---------------------------------") tree = BST() print("Tree before make_empty():", tree) tree.make_empty() print("Tree after make_empty(): ", tree)