6.13. Binary Search Trees¶
6.13.1. Binary Search Trees¶
6.13.1.1. Binary Search Trees¶
6.13.1.2. BST as a Dictionary (1)¶
6.13.1.3. BST as a Dictionary (2)¶
6.13.1.8. .¶
.
6.13.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?
