7.4 Binary Trees
To locate a record with a particular information field in a linked list, one starts at the head of the list and traces through successive records, one at a time. This process can take a long time, even with sorted lists. to reduce the time, we would like to avoid inspecting many records. The binary tree data structure permits faster searches than linked lists, but requires more space because it has more link fields in each record.
In a binary tree, each record is stored in a node. For each node X, at most one node Y is the left child of X and at most one node Z is the right child of X. In other words, any node X may have 0, 1, or 2 children. X is the common parent of nodes Y and Z. There is one node in the tree with no parent; it is called the root of the tree.
In the following tree, each record has a link that points to its left child and a link that points to its right child. (For some applications the implementation of the binary tree could include a pointer from each node to its parent.) Bobby is the left child of David, and Ellen is the right child of David. David is the parent of both Bobby and Ellen. Frank is the root of the tree.
Notice the arrangement of names in this tree. All names in the left subtree of any node are lexicographically less than the name at that node; that is, they would occur earlier in an alphabetic sort. All names in the right subtree are lexicographically greater. For instance, the left subtree of Frank is the tree rooted at David, and all names in this subtree are lexicographically less than Frank. Thus the location of a record in the tree expresses its relationship to other records.
This arrangement of names permits rapid insertion of new records. Starting at the root of the tree, compare the new name with the name at the current node. If the new name is "smaller," then proceed to the left child; if the new name is "larger," then proceed to the right child. For example, to insert Harry into the tree, inspect Frank, Janet, and Garth in that order and then make Harry the right child of Garth. In similar fashion one can search the tree for a specific name.
If a tree with n records is well balanced, then the maximum number of records inspected during an insertion is approximately log2n. In contrast, for linear lists this maximum number would be n. The references describe techniques for keeping trees well balanced after both insertions and deletions.