We turn now to the next data structure: binary search trees. A binary search tree is a binary tree with the property that its left subtree contains records no larger than the root record, its right subtree contains records no smaller than the root record, and its left and right subtrees are also binary search trees. This is a recursive definition.
A binary tree fails to be a binary search tree if even one node contains a record in its left subtree or its right subtree that is, respectively, larger or smaller than the record stored at the node. Figure 9.7 has three examples of binary search trees containing the same fifteen records.
Note that a binary search tree need not be a heap, and that a heap need not be a binary search tree. In general, they are different kinds of binary trees. There are many binary trees that can store the same records. Any binary tree with n nodes can store n records in such a way that the tree is a binary search tree. (Just do an inorder traversal of the binary tree and insert the records in sorted order.)
9.4.1 Searching the Search Trees
9.4.2 Growing the Search Tree "Simply"
9.4.3 The Shape of Simple Binary Search Trees
9.4.4 Deleting a Record Simply
9.4.7 Access By Order in AVL Trees
9.4.8 Binary Search Tree Overview