## Thursday, April 10, 2014

### Find the appropriate data structure

Lets see if you have solutions to the standard problems. Lets define the suitable data structures.

Guess the data structues between the 2 data structures provided (in italics).
1. Operations are Insert, DeleteMax, and DeleteMin.
balanced tree or sorted doubly-linked list
The balanced tree is better since all operations take O(log n) time. The sorted doubly-linked list is O(1) for DeleteMax and DeleteMin, but Insert is O(n); thus, the average time per operation is O(n).
2. Operations are Insert and FindMedian.
(The median is the item m such that half the items are less than m and half are greater than m.)
red-black trees or sorted array
You can use two red-black trees plus an additional variable to hold the median, one red-black tree for items less than the median and one for items greater than the median. When you insert, you can keep track of the median by moving items from one tree to the other. With this scheme, Insert takes O(log n) time and FindMedian take O(1) time. The sorted array takes O(n) time for Insert.
3. You have a dictionary containing the keywords of the Pascal programming language.
ordered array or red-black tree
In this situation the ordered array is best. Both data structures take time O(log n) to find an item. An ordered array takes longer to insert or delete, but we don't expect to be creating or destroying keywords, so there shouldn't be any insertion or deletion. The ordered array is simpler to program and takes less space.
4. You have a dictionary that can contain anywhere from 100 to 10,000 words.