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
- It is a self-balanced BST. (Binary Search Tree)
- Every node has a color (black or red)
- Root is black
- When Parent’s color is red then the child MUST be black
- From the current node to the leaf, the “black nodes on each path” is the same
- 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