preface

Komatsu has not updated the article for a long time recently, is komatsu lazy?

Yes.

Since Komatsu got his hands on the company’s test machine, nearly 5,000 Mi 10 Pros, airPods Pro prizes for dozens of people tweeting inside, and the company’s monthly Q coins and dot coupons, my weekend has been like this.

Come to the company at 10 am, full of confidence ready to learn a day, see mi 10, thought, want to play a king?

The company’s network is also very good, download nearly 5~6m/s, start the whole process with a delay of less than 50, then open the MAC, iQiyi to play 4K Dolby Marvel blockbuster, in the 28-inch screen as the background sound, with airPods, I am the only person in the world, blowing air conditioning, drinking coffee, I bought my favorite heroes and skins with my fingers (I’ve played thousands of Kings and never charged any money).

And suddenly it was noon…

Afternoon, head dizzy, learn and learn, write also can’t write, not equal to see B station!

Binary tree

Ok, without further ado, the following will establish the evolution from binary tree to red black tree, master the process, will not forget, please understand each step along the way.

First of all, why do we build binary trees?

I think the answer is more or less the same, to increase the speed of adding, deleting, checking and changing.

If a tree has only left child nodes, it will be no different from a linked list. Therefore, to build a good binary tree, the balance between nodes is the first thing we need to consider, and the corresponding balanced binary tree has been widely used.

Now we define a balancing operation: with each additional node, the tree is automatically balanced to become a balanced binary tree.

But in practice, if you have to balance every time you add a node, it’s obviously expensive.

Two or three trees

To reduce this consumption, let’s now consider setting up a “two-three tree”.

As shown in the figure above, add a node that can connect three child nodes, and the node itself is composed of two nodes, that is, it can split into two nodes, such as EJ, AC, SX above.

The single-key value node is referred to as 2- and the double-key value node is referred to as 3-.

Now that we have a new tree, what do we do? No brain add delete change check.

To find the

To determine whether a key is in the tree, you just have to start at the root, go to the left, go to the right, and if you go to a node with two keys, you can still compare.

insert

For ordinary binary trees, inserting a new node to hang at the bottom cannot guarantee balance. Only special binary balanced trees can. However, an ordinary binary or three-tree can achieve balance, which can be divided into four situations:

  1. Insert into the node of 2-

    This is too easy, just add the key value to the node, for example, insert k

In this case, it is impossible to upset the balance

  1. Insert into 3-node (contains only one 3-node)

    Imagine mitosis as we learned in elementary school, where we temporarily insert the value directly into the 3-node to form the 4-node

    Then, the 4-node can be split in half, two 2-nodes!

    When splitting, just make sure your left is small and your right big

  2. Insert into 3-node (parent 2-)

    The above two cases are perfectly sufficient, but if the insertion of each 3-node is distributed like the previous one, it will only result in fewer 3-nodes in the tree, and the infinite utilization of the tree must be balanced between 2- and 3-

    If the parent of a 3- node is 2-, then the value inserted into the 3- node becomes 4-, and the value of the middle position of the 4- node can be directly merged into the parent node when the 4- node is split

  3. Insert to 3-node (parent is 3-)

    If the parent node is a 3-node, then doesn’t closing make the parent node a 4-node? So what to do? As you can imagine, of course, it continues to decompose, the principle of small left and large right

    First, the EJ node becomes a 4-node after rule 3

    Then, since its parent M is 2-, we can continue rule 3

The above four cases are rules of insertion. It seems that there are many, but in fact, they are very simple. The first one is simple insertion, and the second to fourth ones are for the analysis of the situation of insertion under the 3-node.

At most, the child nodes are split, at least the parent node is merged.

It is essential that a 4-node is present, and this process has 1+2+3=6 cases depending on the parent node and size.

After the above insertion, you will see that we do not discriminate between the left and right nodes, either no children are generated, or both children are generated, so a two-three tree is, in principle, balanced as long as it is balanced before insertion.

Two or three tree growth process

Remember how binary trees grow? A tree that has a root node and then hangs from top to bottom can be ugly if you’re not careful, but what about two or three trees? It’s bottom-up. How do you go up? After splitting, the key values go up from the middle.

Why do I call binary tree insertion ugly? Because when I was learning Principles of Compilation last year, our teacher compared the top-down LL analysis method with the bottom-up LR analysis method, and he judged the former as “ugly”.

Compared with binary tree and two or three trees, in fact, jump out of the computer, as long as it involves the decision-making process will use trees, and use trees, must be divided into top-down construction and bottom-up construction, this idea is permeated in every field, the road is simple, we need to slowly understand.

Red and black tree

In case you forgot, the goal of this article is red black trees, and I talked about two or three trees for a long time?

Is this me calling a bluff? Of course not, actually

A red-black tree is a binary of two or three trees.

In other words, it has the form of a binary tree and the essence of a binary tree

Why? Because the two-three tree is good, but the implementation is complicated, all kinds of 2-node, 3-node, 4-node easy to mistake, must be unified as 2-node

Nodes become 2-nodes, which means that all 3-nodes have to be split into 2-nodes, and we have to find a way to record that information.

What method? The links between nodes are red and black

Black is normal link, what is red?

Red is a bond, red is a marriage, red,

It’s the connection between the 3-node that we brutally dismantled

In the figure above, the nodes of the second and third tree, AB, are linked in red after being converted to a red-black tree, and then their children are assigned. You may wonder if A can be the root node? And the child is b, right? The answer is no, because red links have to be left links. Why? Rotation will be explained later

Remember the properties of red-black trees? The properties of memorizing and forgetting

  1. All empty chains experience the same number of black chains to the root node

    Nonsense, black links are normal links in two or three trees, and two or three trees themselves are perfectly balanced, of course, the same, and you can imagine red links in red and black trees are all horizontal, because that’s what we’re doing

    In fact, by drawing the red link flat and ignoring it, a red-black tree is a two-three tree

  2. No node is connected to two red links

    This is even more nonsense, with two red chains at the same time, unless it is a 4-node, which in the rules is about to split. (One imagination: chemists can’t combine larger elements because God has made similar rules to maintain balance.)

Even though we drew it in link red, when we actually coded it, obviously, we set it in the node, for example

summary

Red-black trees, because they don’t have 3 minus, even though they’re essentially a two-three tree, and the insertion rules are essentially the insertion rules for two-three trees, they still need some variation

This involves more content, such as color transformation, rotation, etc., shall be limited to space, this article is to explore, as the source of the red-black tree all the properties of red and black tree is in the form of a binary tree to complete two or three rules of the tree, about two or three trees in “binary”, and changed its name to the process of a red-black tree, which he set up rules, we talk to cough up below

This article is from the fourth edition of Algorithms

Author introduction: Komatsu is a new graduate of the Internet company this year, constantly reading progress, wechat public number [Komatsu Walk], share a variety of e-book resources and technical articles and other work, learn together!