3.30 a. Write an array implementation of self-adjusting lists. In a self-adjusting list, all insertions are performed at the front. A self-adjusting list adds a find operation, and when an element is accessed by a find, it is moved to the front of the list without changing the relative order of the other items. (Not available) b. Write a linked list implementation of self-adjusting lists. (Not available) #c. Suppose each element has a fixed probability, pi, of being accessed. Show that the elements with highest access probability are expected to be close to the front. Sol: This follows well-known statistical theorems. See Sleator and Tarjan's paper in Chapter 11 for references. | |
| View Solution | |
| << Back | Next >> |