Those data structures can not learn from leet code— Red-black tree(1)

Compared to Treap, it is more “stable” (grantee balanced)

Continuing with advanced DSA topic: Skip list, B Tree Step by Step, Treap.

In this post, I will go over the process of building a Red-black tree (inserting process) step by step.

First, What defines a red-black tree?

Red-Black tree definition

1. It is a self-balanced BST. (Binary Search Tree)
2. Every node has a color (black or red)
3. Root is black
4. When Parent’s color is red then the child MUST be black
5. From the current node to the leaf, the “black nodes on each path” is the same
6. On every leaf, there are 2 “None” nodes, color is black

What you need to take note of are Rules #4 and #5. They are the 2 important ones contributing to “self-balancing”. (Explained below)

Now we know the rules. Let’s talk about the Search/Insert/Delete Operations

Search is simple. It is BST. which is O(LogN)

Insert

[10, 20, 30, 15, 25, 12, 5, 3, 8]

Inserting 10

There is only 1 node which is the root. Rule #3, it must be black.

Inserting 20