Previous Section
 < Free Open Study > 
Next Section


Chapter 8: Binary Search Trees

Goals

After studying this chapter, you should be able to

So far, we have discussed some of the advantages of using a linear linked list to store sorted information. One drawback of using a linear linked list, however, is the time it takes to search a long list. A sequential or linear search of (possibly) all the nodes in the entire list is an O(N) operation. In Chapter 3, we saw how a binary search could find an element in a sorted list stored sequentially in an array; this kind of search is an O(log2N) operation. It would be nice if we could binary search a linked list, but no practical way exists to find the midpoint of a linked list of nodes. We can, however, reorganize the list's elements into a linked structure that is just perfect for binary searching: the binary search tree. The binary search tree provides us with a structure that retains the flexibility of a linked list but allows for quicker O(log2N) access to any node in the list.

This chapter introduces some basic tree vocabulary and then develops the algorithms and implementations of the operations needed to use a binary search tree.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)