Trees
For large amounts of input, the linear access time of linked lists is prohibitive. In this chapter we look at a simple data structure for which the running time of most operations is O(log n) on average. We also sketch a conceptually simple modification to this data structure that guarantees the above time bound in the worst case and discuss a second modification that essentially gives an O(log n) running time per operation for a long sequence of instructions.
The data structure that we are referring to is known as a binary search tree. Trees in general are very useful abstractions in computer science, so we will discuss their use in other, more general applications. In this chapter, we will

See how trees are used to implement the file system of several popular operating systems.

See how trees can be used to evaluate arithmetic expressions.

Show how to use trees to support searching operations in O(log n) average time, and how to refine these ideas to obtain O(log n) worstcase bounds. We will also see how to implement these operations when the data is stored on a disk.