Dictionaries & Binary Search
Trees
CSC263 Week 3
The course slides, worksheets, and modules
are based on the CSC263 Winter 2021
offering and were developed by Michelle Craig
(with some help from Samar Sabie)
Wednesday Welcome Back
• W2 Module grades are posted on Quercus & MarkUs
• Worth 2% in total
• Check and email for any issues
• W3 Module
• Dropped Q2 from the Describe quiz so marks are out of 23 not 25
• Need to update grades
• Beware of leaving browser open to an unfinished quiz
• PS1 Instructions and Q2 are posted
• Everything else will be posted by Thursday morning
• Piazza thread for finding a partner (if you want one)
W2 Review
www.menti.com
Mentimeter
Dictionary ADT
• Insert (S, x)
• Search (S, k)
• Delete (S, x)
• Today we will examine a number of different data-structures to
implement this ADT. Each time we will consider the worst-case
complexity of each operation.
Data Structure Search Insert Delete
Unsorted array
Sorted array
Unsorted linked list
Sorted linked list
Direct-access table
Hash table
Binary Search Tree
Balanced Search Tree
Time for Insert is in addition to the time to first Search for the element
Approach 1: An unsorted ArrayChalk Talk
Data Structure Search Insert Delete
Unsorted array
Approaches 2-4Worksheet
In your breakout groups, discuss the algorithms for the next
three approaches in the table (Q1-3) and fill in their runtime.
Put any questions here: https://tinyurl.com/csc2635
Data Structure Search Insert Delete
Sorted array
Unsorted linked list
Sorted linked list
Approach 5: A Direct-access Table
5
37
54 58
60
78
Data Structure Search Insert Delete
Direct-access table
Approach 5: A Direct-access Table
• Everything else we have considered takes O(n) space
• Direct-access tables need one location per possible key
Approach 6: Hash Table
Data Structure Search Insert Delete
Hash table
• Map all possible keys onto a smaller set of actual keys
from which you do direct access
Approach 6: Hash Table
• But wait? Does that actually work? What if two items I
want to store in the dictionary have keys that map to
the same new key?
Data Structure Search Insert Delete
Hash table
• Worst case could be:
Approach 7: A Binary Search Tree
Data Structure Search Insert Delete
Binary Search Tree
Approach 8: A Balanced Binary Search Tree
Data Structure Search Insert Delete
Balanced Search Tree
Dictionary using Binary Search Trees
• BST = binary tree with “BST ordering” (fully sorted): for every node,
• dictionary S stores only S.root (also S.size usually)
• TreeNode has members
• .item (element stored in node)
• .left and .right (children)
• Recursive code for operations.
INSERT(S, x):
# Helper may need to modify root itself: have it return value.
S.root <- TREE-INSERT(S.root, x)
TREE-INSERT(root, x):
if root is NIL: # x.key not already in S
# Found insertion point: create new node with empty children.
root <- TreeNode(x)
else if x.key < root.item.key:
root.left <- TREE-INSERT(root.left, x)
else if x.key > root.item.key:
root.right <- TREE-INSERT(root.right, x)
else: # x.key == root.item.key
root.item <- x # just replace root's item with x
return root
Reviewing Binary Search Tree InsertWorksheet
Questions 4-6 from the worksheet
Put questions and solutions here: https://tinyurl.com/csc2635
https://tinyurl.com/csc2635
Question 4Worksheet Solutions
Question 5Worksheet Solutions
Question 6Worksheet Solutions
{0, 1, ……, 8, 9, 10}
SEARCH(S, k):
return TREE-SEARCH(S.root, k)
TREE-SEARCH(root, k):
# Compare against root.item.key to determine if k belongs in left or
# right subtree. Return node with node.item.key = k.
if root is NIL: # k not in S
pass
else if k < root.item.key:
root <- TREE-SEARCH(root.left, k)
else if k > root.item.key:
root <- TREE-SEARCH(root.right, k) else: # x.key == root.item.key pass # root is the node we want return root Reviewing Binary Search Tree SearchWorksheet Questions 7 – 9 from the worksheet on expected number of calls to TREE-SEARCH under different assumptions about the input and different BST. Put questions and solutions here: https://tinyurl.com/csc2635 https://tinyurl.com/csc2635 DELETE(S, x): # Helper may need to modify root itself: have it return value. S.root <- TREE-DELETE(S.root, x) TREE-DELETE(root, x): if root is NIL: # x.key not in S -- should not happen! pass # nothing to remove else if x.key < root.item.key: root.left <- TREE-DELETE(root.left, x) else if x.key > root.item.key:
root.right <- TREE-DELETE(root.right, x)
else: # x.key == root.item.key so Remove root.item.
if root.left is NIL:
root <- root.right # NIL if both children missing
else if root.right is NIL:
root <- root.left
else:
# Root has two children: remove element with smallest key in right subtree and
# move it to root. Assumption: DELETE-MIN returns two values: element removed
# from right subtree and root of resulting subtree (in case root.right changes).
root.item, root.right <- DELETE-MIN(root.right)
return root
DELETE-MIN(root):
# Remove element with smallest key in root's subtree;
# return element removed and root of resulting subtree.
if root.left is NIL:
# Root stores item with smallest key; replace with right child.
return root.item, root.right
else:
# Left subtree not empty: root not the smallest.
item, root.left <- DELETE-MIN(root.left)
return item, root
Meta-lessons to Remember
• When we delete a node, we need a strategy to restore the remaining
nodes to a valid BST.
• Worst-case running time for delete is:
• Major drawback?
E[calls to tree search]
What if we allowed duplicate keys?
• Our definition of Dictionaries had keys that were distinct, but what if
we alllowed duplicates?
• We will consider ways to change your algorithm to allow a BST to hold
duplicate values
For each strategy:
• change pseudo code
• Analyze total time taken to insert n identical items into an empty tree
INSERT(S, x):
# Helper may need to modify root itself: have it return value.
S.root <- TREE-INSERT(S.root, x)
TREE-INSERT(root, x):
if root is NIL: # x.key not already in S
# Found insertion point: create new node with empty children.
root <- TreeNode(x)
else if x.key < root.item.key:
root.left <- TREE-INSERT(root.left, x)
else if x.key > root.item.key:
root.right <- TREE-INSERT(root.right, x)
else: # x.key == root.item.key
root.item <- x # just replace root's item with x
return root
Approach 1: Always go right
Analysis of Approach 1
Chalk Talk
Approaches 2-4Worksheet
Worksheet Questions 10-12
2. Strictly alternate using a flag to keep track
3. Randomly pick a side
4. Keep a chain of values inside the node
Things to take away
Final Reminders