Dictionaries

BST

AVL

search: $\theta(height)$

insert: $\theta(height)$

delete: $\theta(height)$

Worst case cost for all operations is $\theta(height) = \theta(log \space n)$

Other Dictionary Implementations

Dictionary ADT

• Unordered array or linked list: $\theta(1)$ insert, $\theta(n)$ search and delete
• Ordered array: $\theta(log n)$ search, $\theta(n)$ insert and delete
• Binary Search Trees: $\theta(height)$ search, insert, delete
• Balanced BST (AVL): $\theta(log \space n)$ search, insert, and delete

Skip Lists

Expected Space: O(n)

Expected height: O(log n)

search: O(log n)

insert: O(log n)