Writing in the front

Learning and mastering red – black trees is not done overnight. I’ve also seen many excellent red-black tree tutorials, such as:

  1. 30 pictures to help you understand red black trees from top to bottom

  2. What is a red-black tree?

However, the length is too long, resulting in I can not remember a property, so I specifically sorted out the understanding of the nature of red-black trees, to help memory.

Even if you don’t know the red and black tree, you can recite all the properties correctly, and feel that you can gain some advantage in the red and black tree during the interview.

Properties of red-black trees

  • Property 1: “red-black tree”, as the name implies, consists of red nodes and black nodes. Each node is either red or black.

The next few properties are not so much forgettable as forgetful, so I’d like to point out that this red-black tree is a product of scientific research, and one cannot be without the other. Of course, there are no redundant conditions.

Next, this article will try to change one of these properties at a time, and then analyze what is unreasonable? To help you understand. At the end of this paper, we also summarize the “unique memory formula” of red-black tree properties. Hope you can read on patiently, I believe there will be a harvest.

Hypothesis one: the root is red. Is that reasonable?

Let’s say the root is red

Boy, I checked all five properties, except for property two.

When we insert a black node into the red root, it looks like this:

Now, the number of black nodes in the path from root P to right leaf NIL is 1. The number of black nodes in the path from root P to left leaf NIL is 2.

Violation of property 5, need to be adjusted, at this time ** “discoloration” ** can be solved:

Because the root is set to black, the first insertion will require adjustments to the red-black tree, which is not a good sign.

You should know that red-black trees were created to solve the problem of “binary balanced trees” having to adjust the tree every time an element is inserted or deleted, causing poor performance.

Since inserting a black node doesn’t work, what if we insert a red child into the red root node?

The left child of the red root is red, but the right child is black. This does not satisfy the property 4———— every child of every red node is black.

So property 2: the root is black.

Hypothesis two: the leaves are all red, okay?

Let’s say every leaf is red, okay?

By property 4, every child of every red node is black. So the parent of leaf NIL can’t be red.

So if every leaf node is red:

  1. Property 4 is not satisfied if we insert a red child into the root

  2. Property 5 is not satisfied if the root node is inserted with a black child

Remember properties two and three

Property 2: The root is black; Property 3: Every leaf node NIL is black.

So abstraction: black head, black shoe, root is like a black head, leaf NIL is like a pair of black shoes.

Hypothesis three: Can children of red nodes be red?

Property 4 says, every child of every red node must be black.

Let’s say the children of red nodes are allowed to be red, right?

Delete property 4, which means there may be a risk of “red-black tree” chain.

Once this “linked list” structure is formed, the time complexity of the query changes directly from O(log⁡2N\log_2{N}log2N) to O(N).

Red-black trees also lose their balance.

So, in order to prevent a red-black tree from being “linked”, every child of every red node must be black!

A combination of red and black children violates property 5

  • The number of black nodes on the path from the root to the leaf of K is 2

  • The number of black nodes on the path from the root to the leaf of L is 3

Hypothesis 4: The path from any node to a leaf node can contain different numbers of black nodes?

Suppose the path from any node to a leaf can contain a different number of black nodes, right?

Let’s say property 4 is to prevent too many red children from causing the tree structure to be linked

So, property 5 is to prevent black and red intersections, resulting in tree structure linked list

Tree height: The longest path from this node to the leaf node.

Definition reference: height and depth of the tree

Unique memory tips:

Red and black trees, black heads, black shoes. Red son double black, black equal height.

  • Property 1: Red-black tree: every node is either red or black.

  • Property 2: Black head: The root is black

  • Property 3: Wear black shoes/black feet: Each leaf node NIL is black.

  • The nature of the 4; Red child double black: Every child of a red node must be black. (If one is a child and the other is a leaf NIL, also double black)

  • Property 5: Black equal height: The path from any node to leaf node contains the same number of black nodes. (If the height of the black node is 1 and the height of the red node is 0, then the height of each node is the same.)

If you find this article inspiring, give it a thumbs up