Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Red/Black Trees (Stuff Formally Trained Programmers Know)

A continuation of our exploration of binary search trees, and how developers can resolve issues in BST algorithms within their application.

· Big Data Zone ·
Free Resource

Comment (1)

Save
{{ articles[0].views | formatCount}} Views

How to Simplify Apache Kafka. Get eBook.

This post is one in a series of stuff formally trained programmers know – the rest of the series can be found in the series index.

Building off of the Binary Search Tree, we get the red/black tree which aims to solve the problem that a BST can become unbalanced.

The short version of a red/black tree is that it is a BST with a set of rules that help us keep it performing well.

Thinking back to the BST, when we are doing the inserts and deletes, at some point, we need to rebalance the tree to ensure we keep that sweet O(log n) performance for searching. When is the right time to do that rebalancing?

A red/black tree extends a BST by adding one bit of information to each node; for those keeping track, our node now has the data, a key, and a flag.

The flag is either red/black and there are 7 rules a BST should follow (there are 5 official ones that relate to the colors, the first 5 below, but there are two more for the BST itself):

1. Each node is either red or black.
2. The root node is black.
3. All leaves are black. These leaves can be the null points off of a node or they can be explicit nodes.
4. A red node can only have black children.
5. Any path from a node to the leaves contains the same number of black nodes.
6. New nodes added are always red.
7. If the depth of a path is more than twice that of the shorted path we need to do a rotation.

So with these rules, insert and delete get more complex because you need to check these rules and, if the rules do not work you start to correct the issue. What is great with this is that because of the rules you become really efficient at correcting the problems.

So let's look at a really simple BST:

Next, let's make it a red/black tree following our rules above. I am also going to add the leave nodes in this image to help explain it but will take them out the remaining ones.

Note:

• From the root node, you need to go through one black node to reach a leaf node regardless of path.
• All red nodes only have black children.
• A black node can have black children.

Now we are going to add a node with value 11. It is added in the correct place and as a red node.

However, 9 is red and has a red child, so we need to trigger a repaint of it to black. That causes a new issue, that from the root node to the leaves you may go through one black node by going left or two black nodes by going right, so we need to paint the parent of 9 (i.e. 7) to red. Lastly, since 7 is now red, 6 must be repainted to black. Finally, we have a correct red/black tree again.

Lastly, let us add 10, which goes under 11. Immediately, we note that the length from 5 to the leaf of 10 is 4 steps, while the shortest path (the left side) is 2. We know we need to do a rotation.

The rotation is easy, we take the child of the longer side (i.e. 7) and make it root and make the original root (i.e. 5) a child of it. Since 7 has two children already (5 and 9), it's original child 6 moves under 5. Next, we just trigger a repaint, starting with the fact that 7 needs to be black and you end up with the following:

This might seem really expensive to do, but it's not too bad since you are just changing pointers and only a few the performance of the insert becomes O(log n).

## Implementations

Unfortunately, neither Java, .NET, nor JavaScript has out of the box implementations but there are plenty of ones available if you search for it.

Topics:
big data ,binary search tree ,data tree ,tutorial

Comment (1)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.