Instructions
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)