-
Notifications
You must be signed in to change notification settings - Fork 105
Chapter 6: Binary Trees: Infinity in the Palm of your Hand
The following are the code listings for Chapter 6. [book.py]
- Listing 6-1. Recursive and iterative functions to sum the values in a linked list
- Listing 6-2. Expression data structure to represent mathematical expressions
- Listing 6-3. Structure of a binary search tree
- Listing 6-4. BinaryTree class to improve usability of binary search tree
- Listing 6-5. Determining whether a BinaryTree contains a value
- Listing 6-6. Removing minimum value
- Listing 6-7. Removing a value from a BinaryTree
- Listing 6-8. Generator that iterates over values in binary search tree in ascending order
- Listing 6-9. Structure of AVL binary node
- Listing 6-10. Modify _insert() to compute height properly
- Listing 6-11. Helper functions that choose appropriate rotation strategy
- Listing 6-12. Rotating nodes when an unbalanced node is detected
- Listing 6-13. Updating _remove() to maintain AVL property
- Listing 6-14. Updated BinaryNode when using binary tree to store symbol table
- Listing 6-15. Updated BinaryNode when using binary tree to store priority queue
- Listing 6-16. PQ class provides enqueue() and dequeue() functions
- Listing 6-17. Enhance the _insert() method to return description of what happened
class Node:
def __init__(self, val, rest=None):
self.value = val
self.next = rest
def sum_iterative(n):
total = 0 ❶
while n:
total += n.value ❷
n = n.next ❸
return total
def sum_list(n):
if n is None: ❹
return 0
return n.value + sum_list(n.next) ❺❶ Initialize total to 0 to prepare for computation.
❷ For each node, n, in linked list, add its value to total.
❸ Advance to the next node in the linked list.
❹ Base case: the sum of a nonexistent list is 0.
❺ Recursive case: the sum of a linked list, n, is the sum of its value added to the sum of the rest of the list.
class Value: ❶
def __init__(self, e):
self.value = e
def __str__(self):
return str(self.value)
def eval(self):
return self.value
class Expression: ❷
def __init__(self, func, left, right):
self.func = func
self.left = left
self.right = right
def __str__(self): ❸
return '({} {} {})'.format(self.left, self.func.__doc__, self.right)
def eval(self): ❹
return self.func(self.left.eval(), self.right.eval())
def add(left, right): ❺
"""+"""
return left + right❶ A Value stores a numeric value. It can return its value and string representation.
❷ An Expression stores a function, func, and left and right sub-expressions.
❸ Provides built-in __str()__ method to recursively produce strings with
parentheses around expressions.
❹ Evaluate an Expression by evaluating left and right children and
passing those values to func.
❺ Function to perform addition; mult() for multiplication is similar. The docString __doc__ for the function contains the operator symbol.
class BinaryNode:
def __init__(self, val):
self.value = val ❶
self.left = None ❷
self.right = None ❸❶ Each node stores a value.
❷ Each node's left subtree, if it exists, contains values ≤ value.
❸ Each node's right subtree, if it exists, contains values ≥ value.
class BinaryTree:
def __init__(self):
self.root = None ❶
def insert(self, val): ❷
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if node is None:
return BinaryNode(val) ❸
if val <= node.value: ❹
node.left = self._insert(node.left, val)
else: ❺
node.right = self._insert(node.right, val)
return node ❻❶ self.root is the root node of the BinaryTree (or None if empty).
❷ Use _insert() helper function to insert val into tree rooted at self.root.
❸ Base case: to add val to an empty subtree, return a new BinaryNode.
❹ If val is smaller than or equal to node's value, set node.left to be the subtree that results when inserting val into subtree node.left.
❺ If val is larger than node value, set node.right to be the subtree that results when inserting val into subtree node.right.
❻ This method must return node to uphold its contract that it returns the root of the subtree into which val was inserted.
class BinaryTree:
def __contains__(self, target):
node = self.root ❶
while node:
if target == node.value: ❷
return True
if target < node.value: ❸
node = node.left
else:
node = node.right ❹
return False ❺❶ Start the search at the root.
❷ If target value is same as node's value, return True for success.
❸ If target is smaller than node's value, set node to its left subtree to continue search in that subtree.
❹ If target had been larger than node's value, continue search in right subtree.
❺ If the search runs out of nodes to inspect, the value does not exist in the tree, so return False.
def _remove_min(self, node):
if node.left is None: ❶
return node.right
node.left = self._remove_min(node.left) ❷
return node ❸❶ Base case: if node has no left subtree, then it is the smallest
value in the subtree rooted at node; to remove it, just "lift up" and return its right subtree (which could be None).
❷ Recursive case: remove the minimum value from left subtree, and the returned subtree becomes new left subtree for node.
❸ _remove_min() completes the recursive case by returning the node whose left subtree may have been updated.
def remove(self, val):
self.root = self._remove(self.root, val) ❶
def _remove(self, node, val):
if node is None: return None ❷
if val < node.value:
node.left = self._remove(node.left, val) ❸
elif val > node.value:
node.right = self._remove(node.right, val) ❹
else: ❺
if node.left is None: return node.right
if node.right is None: return node.left ❻
original = node ❼
node = node.right
while node.left: ❽
node = node.left
node.right = self._remove_min(original.right) ❾
node.left = original.left ❿
return node❶ Use _remove() helper function to remove val from tree rooted at self.root.
❷ Base case: attempting to remove val from nonexistent tree returns None.
❸ Recursive case #1: if value to be removed is smaller than node.value, set node.left to be the subtree that results from removing val from node.left.
❹ Recursive case #2: if value to be removed is larger than node.value, set node.right to be the subtree that results from removing val from node.right.
❺ Recursive case #3: it may be that node is root of subtree and contains value to be removed, so there's work to be done.
❻ Handle easy cases first. If node is a leaf, then None is returned. If it has just one child, then return that child node.
❼ Remember original reference to node, since we don't want to lose track of node's original left and right subtrees, both of which must exist.
❽ Start with node = node.right to find the smallest value in the subtree rooted at node.right: as long as node has a left subtree, then it does not contain the smallest value, so iteratively locate the node with no left subtree--this is the smallest value in the right subtree of original.
❾ node will become the new root to the left and right children of original. Here I set node.right to the subtree that results from removing the minimum value from original.right. You might notice that this recursive method essentially repeats the process of the while loop, but this code is much easier to understand than trying to do everything in just one pass.
❿ Stitch the subtree rooted at node back together.
class BinaryTree:
def __iter__(self):
for v in self._inorder(self.root): ❶
yield v
def _inorder(self, node):
if node is None: ❷
return
for v in self._inorder(node.left): ❸
yield v
yield node.value ❹
for v in self._inorder(node.right): #<5>
yield v❶ Yield all values that result from the in order traversal of binary search tree rooted at self.root.
❷ Base case: nothing to generate for a nonexistent subtree.
❸ To generate all values in order, first generate all values in order from the subtree rooted at node.left.
❹ Now it is node's turn to yield its value.
❺ Finally, generate all values in order from the subtree rooted at node.right.
class BinaryNode:
def __init__(self, val):
self.value = val ❶
self.left = None
self.right = None
self.height = 0 ❷
def height_difference(self): ❸
left_height = self.left.height if self.left else -1 ❹
right_height = self.right.height if self.right else -1
return left_height - right_height ❺
def compute_height(self): ❻
left_height = self.left.height if self.left else -1
right_height = self.right.height if self.right else -1
self.height = 1 + max(left_height, right_height)❶ Structure of a BinaryNode is essentially the same as a binary search tree.
❷ Record the height for each BinaryNode.
❸ Helper function that computes the height difference between left and right subtree.
❹ Set left_height to +++—1+++ for nonexistent left subtree, or its proper height.
❺ Return height difference, which must be left_height subtracting right_height.
❻ Helper function that updates the height for a node assuming that the height of its respective left and right subtrees (if they exist) have accurate height values.
def _insert(self, node, val):
if node is None:
return BinaryNode(val) ❶
if val <= node.value:
node.left = self._insert(node.left, val)
else:
node.right = self._insert(node.right, val)
node.compute_height() ❷
return node❶ For the base case, when a newly created leaf node is returned, its height is already 0 by default.
❷ When the recursive case completes, val has been inserted into either
node.left or node.right. This means the height for node needs to be recomputed.
def resolve_left_leaning(node): ❶
if node.height_difference() == 2:
if node.left.height_difference() >= 0: ❷
node = rotate_right(node)
else:
node = rotate_left_right(node) ❸
return node #<7>
def resolve_right_leaning(node):
if node.height_difference() == -2: ❹
if node.right.height_difference() <= 0: ❺
node = rotate_left(node)
else:
node = rotate_right_left(node) ❻
return node #<7>❶ A node leans to the left when height difference is +2.
❷ Detects the rotate_right case by confirming that node's left subtree is partially leaning left.
❸ Otherwise, node's left subtree is partially leaning right, meaning a rotate_left_right is in order.
❹ A node leans to the right when height difference is –2.
❺ Detects the rotate_left case by confirming that node's right subtree is partially leaning right.
❻ Otherwise, node's right subtree is partially leaning left, meaning a rotate_right_left is in order.
❼ Be sure to remember to return node of (potentially rebalanced) subtree.
def _insert(self, node, val):
if node is None:
return BinaryNode(val)
if val <= node.value:
node.left = self._insert(node.left, val)
node = resolve_left_leaning(node) ❶
else:
node.right = self._insert(node.right, val)
node = resolve_right_leaning(node) ❷
node.compute_height()
return node❶ If left subtree is now left-leaning, resolve it.
❷ If right subtree is now right-leaning, resolve it.
def _remove_min(self, node):
if node.left is None: return node.right
node.left = self._remove_min(node.left)
node = resolve_right_leaning(node) ❶
node.compute_height()
return node
def _remove(self, node, val):
if node is None: return None
if val < node.value:
node.left = self._remove(node.left, val)
node = resolve_right_leaning(node) ❷
elif val > node.value:
node.right = self._remove(node.right, val)
node = resolve_left_leaning(node) ❸
else:
if node.left is None: return node.right
if node.right is None: return node.left
original = node
node = node.right
while node.left:
node = node.left
node.right = self._remove_min(original.right)
node.left = original.left
node = resolve_left_leaning(node) ❹
node.compute_height()
return node❶ Removing the minimum value from a subtree rooted at node.left could make node right-leaning; rotate to rebalance as needed.
❷ Removing a value from the left subtree of node could make node right-leaning; rotate to rebalance as needed.
❸ Removing a value from the right subtree of node could make node left-leaning; rotate to rebalance as needed.
❹ After the minimum has been removed from the subtree returned to be node.right, node could be left-leaning; rotate to rebalance as needed.
class BinaryNode:
def __init__(self, k, v):
self.key = k ❶
self.value = v ❷
self.left = None
self.right = None
self.height = 0❶ The key is used to navigate the binary search tree.
❷ The value contains arbitrary data that is irrelevant to the operation of the binary search tree.
class BinaryNode:
def __init__(self, v, p):
self.value = v ❶
self.priority = p ❷
self.left = None
self.right = None
self.height = 0❶ The value contains arbitrary data that is irrelevant to the operation of the binary search tree.
❷ The priority is used to navigate the binary search tree.
class PQ:
def __init__(self):
self.tree = BinaryTree() ❶
self.N = 0
def __len__(self):
return self.N
def is_empty(self):
return self.N == 0
def is_full(self):
return False
def enqueue(self, v, p):
self.tree.insert(v, p) ❷
self.N += 1
def _remove_max(self, node): ❸
if node.right is None:
return (node.value, node.left) ❹
(value, node.right) = self._remove_max(node.right) ❺
node = resolve_left_leaning(node) ❻
node.compute_height() ❼
return (value, node)
def dequeue(self): ❽
(value, self.tree.root) = self._remove_max(self.tree.root)
self.N -= 1
return value ❾❶ Use a balanced binary search tree for storage.
❷ To enqueue a (v, p) pair, insert that pair into the binary search tree and increment N count.
❸ The _remove_max() helper method both removes the node with maximum priority from the subtree rooted at node and returns its value and the node of the resulting subtree as a tuple.
❹ Base case: with no right subtree, this node has maximum priority; return both the value in the node being deleted and the left subtree that will eventually take its place.
❺ Recursive case: retrieve removed value and root of updated subtree.
❻ If node is out of balance (it could now lean left), fix with rotations.
❼ Compute node height before returning it along with value that was removed.
❽ The dequeue() method removes node with maximum priority from the binary search tree and returns its value.
❾ After decrementing count, N, return the value that had been associated with highest priority.
class BinaryNode:
def __init__(self, val):
self.value = val
self.left = None
self.right = None
class SpeakingBinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
(self.root,explanation) = self._insert(self.root, val,
'To insert `{}`, '.format(val))
return explanation
def _insert(self, node, val, sofar):
"""
Return (node,explanation) resulting from inserting val into subtree
rooted at node.
"""All content drawn from Learning Algorithms: A Programmer’s Guide to Writing Better Code (c) 2021