Section 12.4. An All-Purpose Binary Tree

12.4. An All-Purpose Binary Tree

Dynamic memory management is fundamental to the implementation of dynamic data structures such as linked lists and trees. In Chapter 10 we presented a simple linked list (see Figure 10-1). The advantage of linked lists over arrays is that new elements can be inserted and existing members removed quickly. However, they also have the drawback that you have to search through the list in sequential order to find a specific item.

A binary search tree (BST), on the other hand, makes linked data elements more quickly accessible. The data items must have a key value that can be used to compare and sort them. A binary search tree combines the flexibility of a linked list with the advantage of a sorted array, in which you can find a desired data item using the binary search algorithm.