534
Graphs and Trees
A binary search tree, by the way it is constructed, has the property that
the value at each node is greater than all values in its left subtree (the subtree
rooted at its left child) and less than all values in its right subtree. A binary
tree search compares item x with a succession of nodes beginning with the
root. If x equals the node item, the algorithm terminates; if x is less than the
item, the left child is checked next; if x is greater than the item, the right
child is checked next. If no child exists, the algorithm terminates because x
is not in the list. Thus the binary search tree, except for the leaves, becomes
the decision tree for the binary tree search algorithm. (Here is a case where
the algorithm itself is described in terms of a tree.) The worst-case number of
comparisons equals the depth of the tree plus 1 (for the missing leaves). However, a binary search tree for a given set of data is not unique; the tree (and
hence the depth of the tree) depends on the order in which the data items are
inserted into the tree.
The actions performed in a binary tree search certainly resemble those in
the “regular” binary search algorithm; in both cases the procedure is to make a
comparison and, if unsuccessful, to look left or right (in the tree if it is a binary
tree search or in the list if it is a binary search). It is possible to order the data for a
binary tree search such that the search tree built from these data matches the decision tree (minus the leaves) for a binary search of the same data in sorted order.
This match is illustrated in Example 35 (note that the tree was not built from data
items in sorted order). Here the binary search tree has the minimum depth and
requires the least amount of work in the worst case.
The depth of a binary search tree for a given set of data items can vary. The
depth of the tree in Figure 6.54 is 4, while that of Figure 6.55 is 2. Thus the worstcase number of comparisons to search for an item can also vary. The tree-building
process can be modified to keep the tree more “balanced,” that is, short and wide
rather than tall and skinny; such a modification reduces the depth of the tree and
therefore the search time. Of course, we know from the theorem on the lower
bound for searching that a certain minimum amount of work is required no matter
how clever we are in building the tree.
example 35
The data in Example 34 entered in the order
9, 12, 10, 5, 8, 2, 14
produce the binary search tree of Figure 6.55.
9
12
5
2
8 10
14
Figure 6.55
Graphs and Trees
A binary search tree, by the way it is constructed, has the property that
the value at each node is greater than all values in its left subtree (the subtree
rooted at its left child) and less than all values in its right subtree. A binary
tree search compares item x with a succession of nodes beginning with the
root. If x equals the node item, the algorithm terminates; if x is less than the
item, the left child is checked next; if x is greater than the item, the right
child is checked next. If no child exists, the algorithm terminates because x
is not in the list. Thus the binary search tree, except for the leaves, becomes
the decision tree for the binary tree search algorithm. (Here is a case where
the algorithm itself is described in terms of a tree.) The worst-case number of
comparisons equals the depth of the tree plus 1 (for the missing leaves). However, a binary search tree for a given set of data is not unique; the tree (and
hence the depth of the tree) depends on the order in which the data items are
inserted into the tree.
The actions performed in a binary tree search certainly resemble those in
the “regular” binary search algorithm; in both cases the procedure is to make a
comparison and, if unsuccessful, to look left or right (in the tree if it is a binary
tree search or in the list if it is a binary search). It is possible to order the data for a
binary tree search such that the search tree built from these data matches the decision tree (minus the leaves) for a binary search of the same data in sorted order.
This match is illustrated in Example 35 (note that the tree was not built from data
items in sorted order). Here the binary search tree has the minimum depth and
requires the least amount of work in the worst case.
The depth of a binary search tree for a given set of data items can vary. The
depth of the tree in Figure 6.54 is 4, while that of Figure 6.55 is 2. Thus the worstcase number of comparisons to search for an item can also vary. The tree-building
process can be modified to keep the tree more “balanced,” that is, short and wide
rather than tall and skinny; such a modification reduces the depth of the tree and
therefore the search time. Of course, we know from the theorem on the lower
bound for searching that a certain minimum amount of work is required no matter
how clever we are in building the tree.
example 35
The data in Example 34 entered in the order
9, 12, 10, 5, 8, 2, 14
produce the binary search tree of Figure 6.55.
9
12
5
2
8 10
14
Figure 6.55