A tree is called a binary search tree if all the nodes contain some information (key) and have the following properties:
- The key of a node is greater than or equal to the key of all children on its left;
- The key of a node is smaller than all the key of all its right children.
A balanced binary search tree is a tree in which every node has the same number of descendants to its left and right.
The following is a (non-balanced) binary search tree:
As their name suggest, binary search trees are particularly useful for searching for an element in a data collection. The complexity of this operation is log(N) because of the way the nodes are arranged in a binary search tree. Let’s now look at some of the basic operations that can be performed using this data structure.
- Insertion can be performed with the following steps:
- Start with the root. Consider the root is the current node.
- Compare the key of the current node with the key of the node to be inserted.
- If the key of the node to be inserted is smaller than or equal to the key of the current node go left.
- If the key of the node to be inserted is greater than the key of the current node go right.
- Repeat step b for all the nodes until a free space is found.
- Place the element in the free space.
For example, if we were inserting ‘11’ in the binary search tree above, after the insertion the tree would look as follows:
We start with the root and compare 10 to 11. 11 > 10, so we move right. Then 11 < 12, so we move left, where a free space is found. The element is then inserted at the free space.
- Searching for an element in the tree is done in a similar fashion. We start at the root and at each step we compare the key of the current node with the value we are looking for, moving left and right according to the result of this comparison. For example, searching for ‘8’ in the tree above would only take 2 steps, as we move left and right from the root. The value we are looking for is not in the tree if there is nowhere to go. For example, if we were looking for ‘13’ we would go from 10 to 12 and then stop because there is nothing on the right.
- The deletion operation needs to take into account the following cases:
- if the node we are trying to delete is a leaf, then just mark it as ‘NULL’ (delete it).
- if the node has only one direct child then delete it and bring the child to its original location. For example, deleting ‘12’ in the tree above only requires replacing the node with ‘11’.
- if the node has two children things become a little more complicated:
- We firstly delete the information in the node, but keep the node.
- Place the largest value in the left sub-tree in the node whose information we have just deleted.
- Delete the node containing the largest value in the left sub-tree.
Let’s see what happens if we are trying to delete ‘10’ from the tree given as an example. We firstly delete ‘10’, but keep the node, as follows:
Then we notice the largest value in the left sub-tree is 8. Generally, this can easily be determined, because we only need to go right in the left sub-tree to find the largest value. We then place 8 in the empty space and delete the node that contained it initially. The final tree is as follows:
There are three ways of traversing a binary search tree. We will list them and give an example based on our initial tree from above (before deletion):
- Inorder traversal – recursively list the key of the node in the order left – root – right. For example, in the tree above we start from the root, move left and repeat the process for the left sub-tree (write down the left part of the root first – 5, then the root itself – 7 and then the right key – 8). The result is 5 7 8 10 11 12. Not that the inorder traversal of a binary search tree always results in the sorted keys, in ascending order.
- Pre-order traversal: similar to inorder, but the order is now root – left – right. For the tree above we would obtain 10 7 5 8 12 11.
- Post-order traversal: also similar to inorder, with the order left – right – root. For the tree above, this type of traversal gives 7 8 7 11 12 10. The root is always the last element.
Binary Search Tree Data Structure in Java
Binary Search Tree Data Structure in PHP
Binary Search Tree Data Structure in C++
Binary Search Tree Data Structure in Python
Binary Search Tree Data Structure in Ruby