Binary search trees (BST)

In this post I will try to explain what a binary search tree is, how they work and how useful they are for many problems. In future posts I plan to analyze a couple of more advanced BSTs.

But first, let's start describing a plain binary tree.

A binary tree is a data structure where we store our items in a hierarchical way, where a parent node can have at most two children.

We can store anything in a binary tree, but in this simple form they are not very useful.

A binary search tree is a binary tree where we add an additional invariant:

Given a node

with value

, all values on the left subtree are smaller than

, and all values on the right subtree are greater than

.

If you analyze any node above, you can see they all follow the rule, for example:

If we were to traverse the tree using

we would get the items ordered from smallest to greatest.

This invariant has another two consequences:

The clue is on the name, binary

trees. They allow to search elements in the tree using binary search. Binary search is fast because in each step half of the elements are discarded. For more details about this operation, please keep reading.

They are also great to implement sets of items, since the properties are great for that use case:

With minimal changes they can be used to implement dictionaries: key value data structures where you can retrieve a data element by a key. For example, we could store a user record with name, email, telephone etc. using a unique id of the user as a key. We would then use this key in the tree operations to decide where to store the data.

Now that we know the invariants we need to maintain we can analyze how the operations work. We will cover the three basic operations: lookup, insertion and deletion.

The way the values are arranged makes the lookup a very simple operation, we can use

directly.

Since we know that for a given node, all values to the left are smaller, and all values to the right are greater, we can eliminate one of the subtrees on each step.

Let's look at an example, lookup of 14 in the following tree.

Now let's lookup for 8, which is not in the tree.

From these examples we can clearly see that we don't have to go through all elements of the tree one by one, exploiting the properties of the BST we can have a result quickly.

To insert an item, we build on top of lookup, making sure we respect the invariant. We can find a couple of different cases.

If the item is already in the tree, we do nothing.

If we reach a node where the lookup algorithm tells us to pick a direction and the node doesn't have a subtree on that direction, we create a subtree on that direction with the node we want to insert.

Deletion also builds on lookup, but it's probably the trickiest operation. We can remove a node on any position of the tree, but to maintain the invariant we may need to rearrange the tree.

Let's go case by case, starting with the easiest, when the value is not in the tree.

We would apply the same lookup algorithm and find out the element is not in tree. Nothing else to do.

If we apply the lookup algorithm and find out the node is a leaf (it doesn't have any children) we can just delete the node.

In the case the node has only one child, we can delete the node and replace it with the child. Let's look at some examples.

A node can have only one child, but its child can be an arbitrarily big subtree. The rule is still just replace the node with its child.

In the case where the element has both children, it's a bit more complex.

We will begin with the simplest case, where both children are leaf. In this case we could replace the node we are deleting with any of the children. We chose to replace it with the right child, but it's an arbitrary decision.

In the general case, where one or both children are arbitrary subtrees, the rule is as follows: We need to find the successor (the next if we follow the order) of the element we want to delete. In a binary search tree this means finding the leftmost element of the right subtree. The right subtree contains all elements greater than the element we want to delete, and the leftmost is the smaller amongst them. Let's call it

.

Once we find it, there are two different cases:

is a leaf

When

is a leaf, we just need to replace the node we want to delete with

.

has a right child

By definition,

can only have a right child, because if it had a left child it wouldn't be the leftmost child. In this case we need to do two things:

Our binary search tree performs really well, allowing us to use binary search, which means all operations are of order

. This means the execution time is proportional to the height of the tree.

But, there is a catch, for this to be true, the tree needs to be balanced. A balanced tree is one where the left and right subtrees of every node differ in height by a max of 1.

Any binary search tree that does not meet that requirement in considered

. To clearly see how this affects the performance, let's look at the next example:

The degenerate tree behaves like a linked list, meaning all operations are

, since in the worst case all elements will be visited.

You can easily run into these cases, the tree from the example is the result of inserting the elements from 1 to 7 using the insertion procedure explained before.

It is so important for binary search tree to be balanced that there are several enhanced tree data structures called self-balancing binary search trees.

and

are two classic examples, each using a different strategy to keep the tree balanced.

In the next post, we'll concentrate on

.