Previous Section
 < Free Open Study > 
Next Section


Summary

In this chapter, we saw how we can use a binary tree to structure sorted information so as to reduce the search time for any particular element. For applications requiring direct access to the elements in a sorted structure, the binary search tree is a very useful data type. If the tree is balanced, we can access any node in the tree with an O(log2N) operation. The binary search tree combines the advantages of quick random access (like a binary search on a linear list) with the flexibility of a linked structure.

We also saw that we can implement the tree operations very elegantly and concisely using recursion. This result makes sense, because a binary tree is itself a "recursive" structure: Any node in the tree is the root of another binary tree. Each time we move down a level in the tree, taking either the right or the left path from a node, we cut the size of the (current) tree in half, a clear case of the smaller-caller. We also saw cases of iteration that replaced recursion (InsertItem and DeleteItem).



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