ACO 101 Study Guide - Final Guide: Binary Search Tree, Hash Function, Binary Search Algorithm
Document Summary
In many applications, we need to maintain a collection of data in which elements have unique identi ers or keys. For example, maybe we need to maintain information about all mcgill students; each student has a unique student id. A collection of pairs of the form (key, information) is often called a dictionary (by analogy with word dictionaries, in which the word is the key and the associated meaning is the information). Optionally, we can also modify the information associated with a given key (but of course, this could be implemented by a delete and insert pair of operations). We will assume that the set of possible keys is ordered and nite (e. g. integers, strings of a nite length, etc). So far, we have discussed several methods that are useful for maintaining dictionaries: arrays, linked lists, and binary search trees (heaps are used for priority queues, and as such, do not support ef cient search of arbitrary keys).
