Algorithms and Data Structures (INF1, Autumn'05)
Lecture 9
Main topic: Symbol tables.
Lecture Plan
- symbol table ADT
- linked list implementation + heuristics
- binary search trees
Reading
-
Sections 7.1, 7.2, 7.3, 7.4, 7.5 and 6.2 (deletion)
of Algorithms and Data Structures: Design, Correctness and Analysis
by Jeffrey H. Kingston.
(You may safely skip the mathematics in the text. Read it only if you are
interested in knowing the justification for the average complexity of
the operations.)
- Have a look at this graphical
demonstration of searching in BST.