A binary search tree is a data sorted structure where each record can be linked with a máximum of two other records. We are going to pay special attention to binary search trees, as they are very popular and widely used in databases. As I anticipated in the previous post, binary trees are of order 2, that is, each node can have a maximum of two children. Additionally, for being a search tree, all nodes have to meet the following conditions:
- if the node has a left child, the value of it has to be smaller than the value of the father.
- if the node has a right child, the value of it has to be higher than the value of the father.
This forces that the data we are saving are sortable, so we can determine if one is bigger or smaller than another. Given the conditions above that a binary search tree has to meet, duplicates are not allowed, they have to be unique data.
Let’s look at it with a simple example where data are integers. The binary search tree for our example is:
