<< Chapter < Page | Chapter >> Page > |
Consider the following binary tree of Integer objects.
-7
|_ -55| |_ []
| |_ -16| |_ -20
| | |_ []| | |_ []
| |_ -9| |_ []
| |_ []|_ 0
|_ -4| |_ []
| |_ []|_ 23
|_ []|_ []
Notice the following property:
Moreover, this property holds recursively for all subtrees. It is called the binary search tree (BST) property.
In general, instead of Integer objects, suppose we have a set of objects that can be compared for equality with "equal to" and "totally ordered" with an order relation called "less or equal to" . Define "less than" to mean "less or equal to" AND "not equal to". Let T be a BiTree structure that stores such totally ordered objects.
The binary search tree property (BSTP) is defined on the binary tree structure as follows.
We can take advantage of this property when looking up for a particular ordered object in the tree. Instead of scanning the whole tree for the search target, we can compare the search target against the root element and narrow the search to the left subtree or the right subtree if necessary. So in the worst possible case, the number of comparisons is proportional to the height of the binary tree. This is a big win if the tree is balanced . It can be proven that when a tree containing N elements is balanced, its height is at most a constant multiple of logN. For example, the height of a balanced tree containing 10 ^{6} elements is at most a fixed multiple of 6. Here is the definition of what a balanced tree is.
A binary tree with the BST property is called a binary search tree. It can serve as an efficient way for storage/retrieval of data. We are lead to the following question: how to create and maintain a binary search tree?
Suppose we start with an empty binary tree T and a Comparator that models a total ordering in a given set of objects S. Then T clearly has the BST property with respect the Comparator ordering of S. The following algorithm (visitor on binary trees) will allow us to insert elements of S into T and at the same time maintain the BST property for T. This algorithm also works for binary search tree containing Comparable objects.
Notification Switch
Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?