What should a node contain?
A traversal is a method that visits every node in a tree once.
def preorder(p):
visit(p)
for child in p.children:
preorder(child)
def postorder(p):
for child in p.children:
postorder(child)
visit(p)
def inorder(p):
for child in p.children[:len(p.children) // 2]:
inorder(child)
visit(p)
for child in p.children[len(p.children) // 2:]:
inorder(child)
What is the minimum a node could contain?
Pseudocode
def search(key):
return search(root, key)
def search(node, key):
if not node:
return False
elif node.data == key:
return True
elif key > node.data:
return search(node.right, key)
else: # key must be < data
return search(node.left, key)
Pseudocode
def insert(key):
insert(root, key)
def insert(node, key):
if not node:
return Node(key)
elif key < node.data:
node.left = insert(
node.left, data
)
elif key > node.data:
node.right = insert(
node.right, data
)
return node
What cases must we consider?
Worst Case? Best Case? Average Case?
Average Case: $\approx 1.39 \log n = O(\log n)$
| Function | Unordered List | Ordered List | BST |
| Search | O(n) | O(log n) | O(h) |
| Insert | O(n) | O(n) | O(h) |
| Delete | O(n) | O(n) | O(h) |
| Min / Max | O(n) | O(1) | O(h) |
| Floor / Ceil | O(n) | O(log n) | O(h) |
| Rank | O(n) | O(log n) | O(h) |
Real-life applications? Hospital Lines!
Cost to implement with ordered lists? Unordered Lists?
An unordered list: $O(1), O(n)$.
Ordered list: $O(n), O(1)$
We can do better.
Heap-ordered complete binary trees
| Implementation | Push | Pop | Peek |
| Unordered Array | 1 | n | n |
| Ordered Array | n | 1 | 1 |
| Binary Heap | log n | log n | 1 |
| d-ary Heap | $\log_d n$ | $\log_d n$ | 1 |
| Fibonacci | 1 | log n | 1 |
| Brodal Queue | 1 | log n | 1 |
| Impossible | 1 | 1 | 1 |
This scheme achieves perfect balance, every path from root to null has same length.