6.14. Binary Search Trees¶
6.14.1. Binary Search Trees¶
6.14.1.1. Binary Search Trees¶
6.14.1.2. BST as a Dictionary (1)¶
6.14.1.3. BST as a Dictionary (2)¶
6.14.1.8. .¶
.
6.14.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?
