10.6. Binary Search Trees¶
10.6.1. Binary Search Trees¶
10.6.1.1. Binary Search Trees¶
10.6.1.2. BST as a Dictionary (1)¶
10.6.1.3. BST as a Dictionary (2)¶
10.6.1.4. BST findhelp¶
10.6.1.5. BST inserthelp¶
10.6.1.6. BST deletemax¶
10.6.1.7. BST removehelp¶
10.6.1.8. .¶
.
10.6.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?
