Exam weight Low
Exam weight Low
Exam weight Low
- BST: every node’s key is larger than all keys in its left subtree and smaller than all in its right.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
- Search: compare and go left or right; cost = depth.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight
High
- Shape depends on insertion order: random → ~1.39 lg N; sorted order → a path (N).
🎯 How this can come up · 1 question
MCQ
Inserting 1, 2, 3, 4, 5 in order into an empty BST gives height:
Correct: 4 (a path).
Exam weight Low
Exam weight Low
Exam weight Low
- BST: average O(log N), worst O(N) for search and insert.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
- Delete min: go left until null left link, replace that node by its right link.
Exam weight
High
- Hibbard deletion: 0 children → remove; 1 child → replace with child; 2 children → replace with successor (min of right subtree).
🎯 How this can come up · 1 question
Written
How do you delete a node with two children from a BST?
Find its successor (the minimum of its right subtree), copy the successor’s key into the node, then delete the successor (which has at most one child).
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
- Hibbard deletion makes trees unbalanced over time (√N height).
Exam weight Low
Exam weight Low
No slides match this filter.