Dictionary

It is an Abstract data type (ADT)

• insert(item)
• delete(item)
• search(key): return item with given key or report doesn't exist.

overwrites any existing key

can be implemented with O(logn) using AVL

Python: Dict

D[key] ~ search

D[key] = val ~ insert

del D[key] ~ delete

item = (key, value)

Motivation

doc dist

database

compilers and interpreters

network routers

network stacks

substring search

string commonalities