3.3. Binary Search Trees¶
3.3.1. Binary Search Trees¶
3.3.1.1. Binary Search Trees¶
3.3.1.2. BST as a Dictionary (1)¶
3.3.1.3. BST as a Dictionary (2)¶
3.3.1.8. .¶
.
3.3.1.9. BST Analysis¶
Find: \(O(d)\)
Insert: \(O(d)\)
Delete: \(O(d)\)
\(d =\) depth of the tree
\(d\) is \(O(\log n)\) if the tree is balanced.
What is the worst case cost? When?
