Binary search trees
A binary search tree (BST) is a special kind of binary tree. It is one of the most important and commonly used data structures in computer science applications. A binary search tree is a tree that is structurally a binary tree, and stores data in its nodes very efficiently. It provides very fast search, insertion, and deletion operations.
A binary tree is called a binary search tree if the value at any node in the tree is greater than the values in all the nodes of its left subtree, and less than (or equal to) the values of all the nodes of the right subtree. For example, if K1, K2, and K3 are key values in a tree of three nodes (as shown in Figure 6.22), then it should satisfy the following conditions:
- The key values K2<=K1
- The key values K3>K1
The following figure depicts the above condition of the binary search tree:
Figure 6.22: An example of a binary search tree