Red-black trees: short and clear

The story of life. The girl offered her boyfriend programmer to pass a psychological test:

Girl: Draw a tree.
Programmer: (draws a binary tree)
Girl: No, it's different.
Programmer: I can draw a red and black tree.

So, today I want to talk a little bit about red-black trees. The story will be brief, without considering the balancing algorithms when inserting / deleting elements in red-black trees.


Red-black trees refer to balanced binary search trees.

Like a binary tree, red-black has the properties:

1) Both subtrees are binary search trees.
')
2) For each node with a key $$$k$The ordering criteria is satisfied:

keys of all left descendants <= $$$k$<keys of all right descendants

(in other definitions, duplicates should be located on the right side or absent altogether).
This inequality should be true for all descendants of the node, and not just its child nodes.

Properties of red-black trees:

1) Each node is colored either red or black (an additional field appears in the data structure of the node - a bit of color).

2) The root is painted black.

3) The leaves (the so-called NULL-nodes) are painted black.

4) Each red node must have two black child nodes. It should be noted that a black node may have black child nodes. Red nodes as a child can only have black.

5) The paths from the knot to its leaves must contain the same number of black knots (this is black height).

So why is such a tree balanced?

Indeed, red-black trees do not guarantee a strict balance (the height difference between the two subtrees of any node should not exceed 1), as in AVL-trees . But the observance of the properties of the red-black tree allows for the implementation of the operations of insertion, deletion and selection during $$$O (log N)$. And now let's see if this is true.

May we have a red and black tree. Black height equals $$$bh$(black height).

If the path from the root node to the leaf node contains the minimum number of red nodes (ie, zero), then this path is equal to $$$bh$.

If the path contains the maximum number of red nodes ( $$$bh$in accordance with the property $$$4$), then this path will be equal to $$$2bh$.

That is, the path from the root to the leaves can differ by no more than twice ( $$$h <= 2log (N + 1)$where h is the height of the subtree), this is enough for the execution time of operations in this tree to be $$$O (log N)$

How to insert?

Inserting into a red-black tree begins with the insertion of the element, as in the usual binary search tree. Only here elements are inserted into the positions of NULL-leaves. The inserted node is always colored red. Next is the procedure for checking the preservation properties of red-black tree $$$1-5$.

Property 1 is not violated, since the new node is immediately assigned a red color.

Property 2 is violated only if we had an empty tree and the first inserted node (also known as the root) is colored red. Here it is enough just to repaint the root black.

Property 3 is also not violated, since when a node is added, it gets black leafy NULL nodes.

Basically there are 2 other violations:

1) The red node has a red child node (the property is violated $$$4$).

2) Paths in the tree contain a different number of black nodes (the property is violated $$$5$).

Learn more about balancing red-ebony in different cases (there are five, if you include a violation of $$$2$) can be read on the wiki .

Is it generally used somewhere?

Yes! When at the institute in the third year we were read “Algorithms and data structures,” I could not imagine that red-black trees were used somewhere. I remember how we didn’t like the theme of balanced trees. Oh, these kinship ties in red-and-black trees (“uncle”, “grandfather”, “black brother and godfather of the red father”), Santa Barbara is straightforward. Right and left, small and large turns of AVL-trees are solid roller coasters. You also do not like red-black trees? So, just do not know how to cook them. And someone just took it and cooked it. For example, associative arrays in most libraries are implemented precisely through red-black trees.

That's all I wanted to tell.