Instructions
Requirements and Specifications
- BST
- Linked list
- Sorting techniques
- Different techniques for evaluation
BST
"""
-------------------------------------------------------
Linked version of the BST ADT - Exam
-------------------------------------------------------
Author: Prasa Pirabagaran
ID: 200183490
Email: pira8349@mylaurier.ca
__updated__ = "2022-08-09"
-------------------------------------------------------
"""
# pylint: disable=protected-access
# Imports
from copy import deepcopy
class BST:
def _turn_right(self, parent):
"""
-------------------------------------------------------
Turns the parent node to its right around its left child.
Updates the heights of the turned nodes.
Use: parent = self._turn_right(parent)
-------------------------------------------------------
Parameters:
parent - the pivot node to rotate around (_BST_Node)
Returns:
updated - the node that replaces the parent node (_BST_Node)
-------------------------------------------------------
"""
new_root = parent._right
parent._right = new_root._left
new_root._left = parent
return new_root
def max_height(self):
"""
---------------------------------------------------------
Returns the maximum height of a bst.
Use: height = bst.max_height()
---------------------------------------------------------
Returns:
height - the length of the longest path from the
root node to the base of a tree (int)
---------------------------------------------------------
"""
height = self._max_height_aux(self._root)
return height
def _max_height_aux(self, node):
"""
---------------------------------------------------------
Private auxiliary method for 'max_height'.
Returns the maximum height of node.
Use: height = self._max_height_aux(node)
---------------------------------------------------------
Parameters:
node - a BST node (_BST_Node)
Returns:
height - the maximum height of node (int)
---------------------------------------------------------
"""
if node is None:
return 0
return 1 + max(self._max_height_aux(node._left), self._max_height_aux(node._right))
def max_path(self):
"""
---------------------------------------------------------
Returns a list of nodes in the longest path of a bst.
Use: path = bst.max_path()
---------------------------------------------------------
Returns:
path - a list of nodes of the longest path from the
root node to the base of a tree (list of _BST_Node)
---------------------------------------------------------
"""
path = self._max_path_aux(self._root) # your parameters here
return path
def _max_path_aux(self, node):
"""
---------------------------------------------------------
Private auxiliary method for 'max_path'.
Returns a list of the nodes in the longest path from node to the
base of a tree.
Use: path = self._max_height_aux( node )
---------------------------------------------------------
Parameters:
node - a binary tree node (_BST_Node)
Returns:
path - a list of the nodes in the longest path from node
to the base of a tree (list of _BST_Node)
---------------------------------------------------------
"""
if node is None:
return []
left_path = self._max_path_aux(node._left)
right_path = self._max_path_aux(node._right)
result = left_path
if len(right_path) > len(left_path):
result = right_path
result.insert(0, node)
return result
def flip(self):
"""
---------------------------------------------------------
Changes the current BST into a flipped image of itself. All nodes
are swapped with nodes on the other side of a tree. Nodes may take
the place of an empty spot. The resulting tree is a flipped image
of the original tree. (Note that the flipped tree is not a BST.)
Use: bst.flip()
---------------------------------------------------------
Returns:
None
---------------------------------------------------------
"""
self._flip_aux(self._root)
return
def _flip_aux(self, node):
"""
---------------------------------------------------------
Changes the current subtree into a flipped image of itself. All nodes
are swapped with nodes on the other side of a tree. Nodes may take
the place of an empty spot. The resulting subtree is a flipped image
of the original subtree.
Use: self._flip_aux(node)
---------------------------------------------------------
Parameters:
node - a binary tree node (_BST_Node)
Returns:
None
---------------------------------------------------------
"""
if node._left is not None:
self._flip_aux(node._left)
if node._right is not None:
self._flip_aux(node._right)
sw = node._left
node._left = node._right
node._right = sw
return
# DO NOT CHANGE CODE BELOW THIS LINE
# =======================================================================
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty BST.
Use: bst = BST()
-------------------------------------------------------
Returns:
A BST object (BST)
-------------------------------------------------------
"""
self._root = None
self._count = 0
def insert(self, value):
"""
-------------------------------------------------------
Inserts a copy of value into bst. Values may appear
only once in a tree.
Use: b = bst.insert(value)
-------------------------------------------------------
Parameters:
value - data to be inserted into bst (?)
Returns:
inserted - True if value is inserted into bst,
False otherwise. (boolean)
-------------------------------------------------------
"""
self._root, inserted = self._insert_aux(self._root, value)
return inserted
def _insert_aux(self, node, value):
"""
-------------------------------------------------------
Inserts a copy of value into node.
Private recursive operation called only by insert.
Use: node, inserted = self._insert_aux(node, value)
-------------------------------------------------------
Parameters:
node - a bst node (_BST_Node)
value - data to be inserted into the node (?)
Returns:
node - the current node (_BST_Node)
inserted - True if value is inserted into node,
False otherwise. (boolean)
-------------------------------------------------------
"""
if node is None:
# Base case: add a new node containing the value.
node = _BST_Node(value)
self._count += 1
inserted = True
elif value < node._value:
# General case: check the left subtree.
node._left, inserted = self._insert_aux(node._left, value)
elif value > node._value:
# General case: check the right subtree.
node._right, inserted = self._insert_aux(node._right, value)
else:
# Base case: value is already in the BST.
inserted = False
if inserted:
# Update the node height if any of its children have been changed.
node._update_height()
return node, inserted
def retrieve(self, key):
"""
-------------------------------------------------------
Retrieves a copy of a value matching key in bst. (Iterative)
Use: v = bst.retrieve(key)
-------------------------------------------------------
Parameters:
key - data to search for (?)
Returns:
value - value in the node containing key, otherwise None (?)
-------------------------------------------------------
"""
node = self._root
value = None
while node is not None and value is None:
if node._value > key:
node = node._left
elif node._value < key:
node = node._right
elif node._value == key:
# for comparison counting
value = deepcopy(node._value)
return value
def inorder(self):
"""
-------------------------------------------------------
Generates a list of the contents of the tree in inorder order.
Use: a = bst.inorder()
-------------------------------------------------------
Returns:
a - copy of the contents of the tree in inorder (list of ?)
-------------------------------------------------------
"""
a = []
self._inorder_aux(self._root, a)
return a
def _inorder_aux(self, node, a):
"""
---------------------------------------------------------
Traverses node subtree in inorder. a contains the contents of
node and its children in inorder.
Private recursive operation called only by inorder.
Use: self._inorder_aux(node, a)
---------------------------------------------------------
Parameters:
node - an BST node (_BST_Node)
a - target list of data (list of ?)
Returns:
None
---------------------------------------------------------
"""
if node is not None:
self._inorder_aux(node._left, a)
a.append(deepcopy(node._value))
self._inorder_aux(node._right, a)
return
def preorder(self):
"""
-------------------------------------------------------
Generates a list of the contents of the tree in preorder order.
Use: a = bst.preorder()
-------------------------------------------------------
Returns:
a - copy of the contents of the tree in preorder (list of ?)
-------------------------------------------------------
"""
a = []
self._preorder_aux(self._root, a)
return a
def _preorder_aux(self, node, a):
"""
---------------------------------------------------------
Traverses node subtree in preorder. a contains the contents of
node and its children in preorder.
Private recursive operation called only by preorder.
Use: self._preorder_aux(node, a)
---------------------------------------------------------
Parameters:
node - an BST node (_BST_Node)
a - target of data (list of ?)
Returns:
None
---------------------------------------------------------
"""
if node is not None:
a.append(deepcopy(node._value))
self._preorder_aux(node._left, a)
self._preorder_aux(node._right, a)
return
def _node_height(self, node):
"""
---------------------------------------------------------
Helper function to determine the height of node - handles empty node.
Private operation called only by _is_valid_aux.
Use: h = self._node_height(node)
---------------------------------------------------------
Parameters:
node - the node to get the height of (_BST_Node)
Returns:
height - 0 if node is None, node._height otherwise (int)
---------------------------------------------------------
"""
if node is None:
height = 0
else:
height = node._height
return height
def is_valid(self):
"""
---------------------------------------------------------
Determines if a tree is a is_valid BST, i.e. the values in all left nodes
are smaller than their parent, and the values in all right nodes are
larger than their parent, and height of any node is 1 + max height of
its children.
Use: b = bst.is_valid()
---------------------------------------------------------
Returns:
valid - True if tree is a BST, False otherwise (boolean)
---------------------------------------------------------
"""
valid = self._is_valid_aux(self._root, None, None)
return valid
def _is_valid_aux(self, node, min_node, max_node):
"""
---------------------------------------------------------
Private recursive method to determine the BST validity of node,
used only by is_valid.
Use: valid = self._is_valid_aux(node, min_node, max_node)
---------------------------------------------------------
Parameters:
node - a binary tree node (_BST_Node)
min_node - the node with the minimum value for the current tree (_BST_Node)
max_node - the node with the maximum value for the current tree (_BST_Node)
Returns:
valid - True if node is root of a valid BST, False otherwise (boolean)
---------------------------------------------------------
"""
if node is None:
valid = True
elif min_node is not None and node._value <= min_node._value:
# print("BST left value violation at value: {}".format(node._value))
valid = False
elif max_node is not None and node._value >= max_node._value:
# print("BST right value violation at value: {}".format(node._value))
valid = False
elif node._height != max(self._node_height(node._left), self._node_height(node._right)) + 1:
# print("BST height violation at value: {}".format(node._value))
valid = False
else:
# node becomes max node of left tree, min node of right tree
valid = self._is_valid_aux(node._left, min_node, node) \
and self._is_valid_aux(node._right, node, max_node)
return valid
class _BST_Node:
def __init__(self, value):
"""
-------------------------------------------------------
Initializes a BST node containing value. Child pointers
are None, height is 1.
Use: node = _BST_Node(value)
-------------------------------------------------------
Parameters:
value - value for the node (?)
Returns:
A _BST_Node object (_BST_Node)
-------------------------------------------------------
"""
self._value = deepcopy(value)
self._left = None
self._right = None
self._height = 1
self._count = 0
def _update_height(self):
"""
-------------------------------------------------------
Updates the height of the current node. _height is 1 plus
the maximum of the node's (up to) two child heights.
Use: node._update_height()
-------------------------------------------------------
Returns:
None
-------------------------------------------------------
"""
if self._left is None:
left_height = 0
else:
left_height = self._left._height
if self._right is None:
right_height = 0
else:
right_height = self._right._height
self._height = max(left_height, right_height) + 1
return
def __str__(self):
"""
USE FOR TESTING ONLY
-------------------------------------------------------
Returns node height and value as a string - for debugging.
-------------------------------------------------------
"""
return f"h: {self._height}, v: {self._value}"
LINKED LIST
"""
-------------------------------------------------------
Linked version of the list ADT.
-------------------------------------------------------
Author: Prasa Pirabagaran
ID: 200183490
Email: pira8349@mylaurier.ca
__updated__ = "2022-08-09"
-------------------------------------------------------
"""
# pylint: disable=protected-access
from copy import deepcopy
from random import randint
class List:
def append_list(self, source):
"""
-------------------------------------------------------
Private helper method to append the entire source List to the
rear of the target List.
Either the source List or the target List may be empty.
The source list becomes empty.
Use: target.append_list(source)
-------------------------------------------------------
Parameters:
source - an linked list (List)
Returns:
None
-------------------------------------------------------
"""
while not source.is_empty():
self._move_front_to_rear(source)
return
def split_sq(self):
"""
-------------------------------------------------------
Splits source into two parts. target1 contains the first half,
target2 the second half. Current (source) List becomes empty.
Uses Slow/Quick algorithm.
Use: target1, target2 = source.split_sq()
-------------------------------------------------------
Returns:
target1 - a new List with >= 50% of the original List (List)
target2 - a new List with <= 50% of the original List (List)
-------------------------------------------------------
"""
size1 = (len(self) + 1) // 2
target1 = List()
target2 = List()
for _ in range(size1):
target1._move_front_to_rear(self)
while not self.is_empty():
target2._move_front_to_rear(self)
return target1, target2
def randomize(self):
"""
-------------------------------------------------------
Moves nodes from source to target in random order.
All data is preserved, order is not. source is empty when
finished.
Use: target = source.randomize()
-------------------------------------------------------
Returns:
target - a new List with randomly ordered values from source (List)
-------------------------------------------------------
"""
target = List()
while not self.is_empty():
n = randint(0, len(self)-1)
if n > 0:
node = self._front
for _ in range(n-1):
node = node._next
self._swap(None, node)
target._move_front_to_rear(self)
return target
# DO NOT CHANGE CODE BELOW THIS LINE
# =======================================================================
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty list.
Use: lst = List()
-------------------------------------------------------
Returns:
a new List object (List)
-------------------------------------------------------
"""
self._front = None
self._rear = None
self._count = 0
def is_empty(self):
"""
-------------------------------------------------------
Determines if the list is empty.
Use: b = lst.is_empty()
-------------------------------------------------------
Returns:
True if the list is empty, False otherwise.
-------------------------------------------------------
"""
return self._front is None
def __len__(self):
"""
-------------------------------------------------------
Returns the number of values in the list.
Use: n = len(lst)
-------------------------------------------------------
Returns:
the number of values in the list.
-------------------------------------------------------
"""
return self._count
def prepend(self, value):
"""
-------------------------------------------------------
Adds a copy of value to the front of the List.
Use: lst.prepend(value)
-------------------------------------------------------
Parameters:
value - a data element. (?)
Returns:
None
-------------------------------------------------------
"""
# Create the new node.
node = _List_Node(value, self._front)
if self._rear is None:
# List is empty - update the rear of the List..
self._rear = node
# Update the front of the List.
self._front = node
self._count += 1
return
def append(self, value):
"""
---------------------------------------------------------
Adds a copy of value to the end of the List.
Use: lst.append(value)
-------------------------------------------------------
Parameters:
value - a data element (?)
Returns:
None
-------------------------------------------------------
"""
# Create the new node.
node = _List_Node(value, None)
if self._front is None:
# list is empty - update the front of the List.
self._front = node
else:
self._rear._next = node
# Update the rear of the List.
self._rear = node
self._count += 1
return
def _move_front_to_front(self, source):
"""
-------------------------------------------------------
Moves the front node from the source List to the front
of the current List. Private helper method.
Use: self._move_front_to_front(source)
-------------------------------------------------------
Parameters:
source - a non-empty linked List (List)
Returns:
The current List contains the old front of the source List and
its count is updated. The source List front and count are updated.
-------------------------------------------------------
"""
assert source._front is not None, \
"Cannot move the front of an empty List"
node = source._front
# Update the source list
source._count -= 1
source._front = source._front._next
if source._front is None:
# Clean up source list if empty.
source._rear = None
# Update the target list
node._next = self._front
self._front = node
if self._rear is None:
# Target list is empty
self._rear = node
self._count += 1
return
def _move_front_to_rear(self, source):
"""
-------------------------------------------------------
Moves the front node from the source List to the rear
of the current List. Private helper method.
Use: self._move_front_to_rear(source)
-------------------------------------------------------
Parameters:
rs - a non-empty linked List (List)
Returns:
The current List contains the old front of the source List and
its count is updated. The source List front and count are updated.
-------------------------------------------------------
"""
assert source._front is not None, \
"Cannot move the front of an empty List"
node = source._front
# Update the source list
source._count -= 1
source._front = source._front._next
if source._front is None:
# Clean up source list if empty.
source._rear = None
# Update the target list
if self._rear is None:
self._front = node
else:
self._rear._next = node
node._next = None
self._rear = node
self._count += 1
return
def _swap(self, pln, prn):
"""
-------------------------------------------------------
Swaps the position of two nodes. The nodes in pln.next and prn.next
have been swapped, and all links to them updated.
Use: self._swap(pln, prn)
-------------------------------------------------------
Parameters:
pln - node before list node to swap (_List_Node)
prn - node before list node to swap (_List_Node)
Returns:
None
-------------------------------------------------------
"""
if pln is not prn:
# Swap only if two nodes are not the same node
if pln is None:
# Make r the new front
left = self._front
self._front = prn._next
else:
left = pln._next
pln._next = prn._next
if prn is None:
# Make l the new front
right = self._front
self._front = left
else:
right = prn._next
prn._next = left
# Swap next pointers
# lst._next, r._next = r._next, lst._next
temp = left._next
left._next = right._next
right._next = temp
# Update the rear
if right._next is None:
self._rear = right
elif left._next is None:
self._rear = left
return
def __iter__(self):
"""
USE FOR TESTING ONLY
-------------------------------------------------------
Generates a Python iterator. Iterates through the list
from front to rear.
Use: for v in s:
-------------------------------------------------------
Returns:
yields
value - the next value in the list (?)
-------------------------------------------------------
"""
current = self._front
while current is not None:
yield current._value
current = current._next
class _List_Node:
def __init__(self, value, next_):
"""
-------------------------------------------------------
Initializes a list node that contains a copy of value
and a link to the next node in the list.
Use: node = _List_Node(value, _next)
-------------------------------------------------------
Parameters:
_value - value value for node (?)
_next - another list node (_List_Node)
Returns:
a new _List_Node object (_List_Node)
-------------------------------------------------------
"""
self._value = deepcopy(value)
self._next = next_