Blog: bugstack.cn

Precipitation, share, grow, let yourself and others can gain something! 😄

One, foreword

Red - black tree is a kind of efficient self - balanced binary search tree

Rudolf Bayer invented red-black trees in 1978, which were called symmetric binary B-trees at that time. It was later modified in 1978 by Leo J. Guibas and Robert Sedgewick to the present red-black tree.

Red-black tree has good efficiency. It can complete insert, delete, search and other operations in approximately O(logN) time complexity. Therefore, red-black tree is also widely used in the industry, such as TreeMap in Java. HashMap in JDK 1.8 and map in C++ STL are implemented based on red-black tree structure.

It's hard to learn by rote

The structure and design of red-black trees are excellent, and the implementation also has complex processing logic, including the insertion or deletion of nodes; Color change, rotation operation and other operations. But if only these knowledge points hard back down, when to dye, when to rotate, is not much significance, with not long will also forget. So this part of the study, understanding its root is more important.

2. Interview questions

Thank the plane, test you a few red black tree knowledge 🦀

  1. In what scenarios are red-black tree data structures used and what are the benefits?
  2. What is the time complexity of a red-black tree?
  3. How do I balance new nodes in a red-black tree?

🤥 plane, 2-3 tree is not to see, go back and wait for the news!

3. Equivalence between 2-3 trees and red-black trees

In the previous chapter “Explaining the 2-3 balanced tree”, a large number of legends were used to explain the 2-3 tree, and it was written in the title that it was the predecessor of the red-black tree. It is easier to understand red-black trees after reading.

Red black tree rule

1.The root node is black2.Nodes are red and black or black3.All cotyledon nodes are black (leaves are NIL nodes, not drawn by default)4.Each red node must have two black child nodes.5.The path from any node to every leaf node contains the same number of black nodesCopy the code

So, how do these rules summarize and define? So let’s go through this step by step.

1. Why a red-black tree with a 2-3 tree

First, a 2-3 tree (pronounced “two-three-tree”) is a node with one or two elements, and in fact a 2-3 tree to a red-black tree is a transformation from the conceptual model of a 2-3-4 tree. A -4 cross is a node with three elements in it. This is adjusted in a 2-3 tree, but retained in the conceptual model.

Although two-three-four trees also have the same characteristics of balanced trees as 2-3 trees, it would be very troublesome and inefficient to directly implement such a model with codes. The complex points here include;

  1. The node types of 2-fork, 3-fork, and 4-fork structure have high conversion complexity
  2. 3- fork, 4- fork, node data need to be compared multiple times, unlike 2- fork node, direct Boolean type comparison can beEither the left or right
  3. For each difference in code implementation, additional code is required, and rules are not standardized enough

Therefore, the hope to find a balance relationship, not only maintain the balance of 2-3 trees and O(logn) characteristics, but also more convenient code implementation, so the birth of red black tree.

2. Simple 2-3 tree to red black tree

2-3 tree to red-black tree, or red-black tree is another representation of 2-3 and 2-3-4 trees, which is more convenient for coding implementation.

Simple conversion examples;

It can be seen from the figure above that the conversion relationship between 2-3-4 trees and red-black trees includes;

  1. 2-fork node, the transformation is relatively simple, only the original node is converted to black node
  2. The 3-fork node consists of two elements. The two nodes are first connected with the red line, then separated, and finally the height is adjustedThe black nodes are on
  3. The 4-fork node consists of 3 elements, which are connected by red and black lines respectively, and then split out and pulled up the height.The pull-up process is the same as the 2-3 trees, but with added color

To sum up, it is the node transformation of the two-three-four tree, and the rules are summarized as follows;

  1. I’m going to write a two-three-four tree as a binary tree
  2. The 3-fork and 4-fork nodes are connected by red and black wires
  3. In addition, there are two cases of a 3-fork node, leading to a binary tree, which has left and right skew

3. Turn complex 2-3 trees into red black trees

In the process of converting a simple 2-3 tree into a red-black tree, we learned a basic transformation rule right-handed definition. Next, we will use a slightly more complex 2-3 tree and red-black tree corresponding relationship, as shown in the figure below.

The picture above is a slightly more complicated 2 or 3 tree, the process of converting to a red black tree, but this picture gives you a better feel for a red black tree, and it also satisfies the following conditions;

  1. The same number of black nodes are passed from any node to the leaf node
  2. Black nodes maintain overall balance, that is, keep the whole red-black tree close to O(logn) time
  3. The characteristics of other red black trees are also satisfied, and can be compared with the characteristics of red black trees

Red black tree

1. Balance operation

Through the tree learning in section 2-3 of the previous chapter, nodes are not inserted into empty positions, but are integrated and adjusted with existing nodes to maintain the balance of the whole tree.

And a red-black tree is a conceptual model of a two-three-four tree, which is connected by red links when nodes are inserted, so red nodes are inserted. Adjust after insertion to keep the tree close to balance.

Then, in order to keep a red-black tree in equilibrium, it mainly involves dyeing and rotating left and right, which are actually evolved from 2-3 trees. Next, we will explain the evolution of several rules to better understand the balancing operation of red-black trees.

1.1 left rotation

Left-handed definition: Converts a right-leaning red node link (2-3 tree, 3-fork bielement node) to a left link.

Background: Elements are inserted sequentially, 1, 2, 3, 2-3 trees are balanced, and the red-black tree is temporarily tilted to the right.

Next, we compare the balancing operation of the two tree structures respectively.

  1. 2-3 trees, all inserted nodes will remain on the same node, and then adjust the node position to maintain balance.
  2. In a red-black tree, you need to rotate to the left of the node to pull up element 2, and element 1 and element 3 become the left and right child nodes, respectively.

Left-rotation of red-black trees will only handle the corresponding 2-3 tree nodes, and will not change the whole.

1.2 right

Dextral definition: Converts a left-leaning red join (2-3 tree, 3-fork bielement node) to a right-leaning join.

Background: Elements are inserted sequentially, trees 3, 1, 1, 2-3 are balanced, and red-black trees are temporarily tilted to the left.

Next, we compare the balancing operation of the two tree structures respectively.

  1. 2-3 trees, all inserted nodes will remain on the same node, and then adjust the node position to maintain balance.
  2. In a red-black tree, you need to rotate to the right of the node to pull up element 2, and element 1 and element 3 become the left and right child nodes, respectively.

You’ll see that left and right hand rotation correspond to each other, but they stay the same in a 2-3 tree

1.3 Comprehensive application of left and right rotation

Now that we have a basic concept of left and right rotation, let’s look at an evolutionary case that can synthesize left and right rotation and corresponding 2-3 trees, as follows;

The above example illustrates three cases of an element being inserted, as follows;

  1. 1, 3, insert 0, left bottom insert, compared to 2-3 tree, need right rotation to maintain balance
  2. 1, 3, insert 2, insert the middle position, first rotate left to adjust the element position, then rotate right to balance the tree
  3. 1, 3, insert 5, insert the right position, at this time just keep the tree balance, do not need to adjust

1.4 the dyeing

In the 2-3 tree, insert a node, in order to maintain the balance of the tree is not inserted into the empty position, when the number of elements after inserting the node has 3, adjust the middle element upward, to maintain the balance of the tree. The corresponding red-black tree needs to adjust its color to ensure the balance rule of red-black tree. For details, see the following.

2. Rotation + dyeing application cases

Next, we apply the rotation and dyeing explained above to a practical case, as shown in the figure below.

  • So I’m going to start on the left, and I’m going to have a red-black tree that I’m going to insert in order, insert order; ‘seven, two, eight, one, four, three, five

`

  • α, insert element 6 into the current red-black tree, after insertion there are three red nodes in the lower right corner;Three, five, six.
  • β, because the lower right corner meets the staining condition, after transformation; Black nodes (3, 5) and red nodes (4, 6).
  • Gamma, and then look at the nodes linked by the red lineSeven, four, two, the minimum node is in the middle, left-handed balanced tree structure.
  • Delta, left rotation complete, red link lineSeven, four, twoIn order to do the inclined order node, we need to do the dextral operation.
  • ε, left rotation, right rotation, after adjustment, and meet the dyeing operation. To restore the red-black tree balance.

Notice that all of the red nodes are connected by red lines. That corresponds to a 2-3 tree.

3. Delete the vm

According to the red-black tree of the two-three-four tree model, deletion is basically carried out in a 2-3 way, but dyeing and rotation operations are needed in this process to keep the tree balance. The deletion process can be divided into four situations as shown below.

3.1 Delete red cotyledon nodes

Deletion of red cotyledon nodes will not destroy tree balance or affect tree height, so it can be directly deleted as follows;

3.2 Deleting the Node on the left

3.2.1 The brother of the truncated point is black & contains the right child node

3.2.2 The brother of the truncated point is black & contains the left child node

3.2.3 Brother of truncated point is black & contains twin nodes (red)

3.2.4 The brother of the truncated point is black and does not contain child nodes

3.2.5 Brother of truncated point is black & Contains double black node (black)

3.3. Delete the node on the right

3.3.1 The brother of the truncated point is black & contains the left child node

3.3.2 The brother of the truncated point is black & contains the right child node

3.3.3 Brother of truncated point is black & contains twin nodes (red)

3.2.4 The brother of the truncated point is black and does not contain child nodes

3.2.5 Brother of truncated point is black & Contains double black node (black)

Five, the summary

  • From 2-3 trees to explain the concept of 2-3-4 trees to derive the red black tree, from the elements in the 2-3 tree insertion and deletion contrast to the red black tree to maintain the balance operation, from the principle of analysis to the actual operation, and the vast majority of the content of the red black tree is introduced.
  • Understanding the principles of red-black trees is more important than memorizing concepts. This is a kind of data structure learning, and it is more important to learn technology transfer, rather than memorize several questions for the interview. This learning process may be very brain-burning, but it is suitable for learning the basics.
  • In the preparation of this article, reference to a large number of materials for correction, including excellent articles;
    • Red black tree visualization: www.cs.usfca.edu/~galles/vis…
    • Left-leaning red-black Trees

Six, series recommendation

  • What do interviewers ask me
  • Core knowledge of HashMap, disturbance function, load factor, expansion linked list resolution, deep learning
  • HashMap data insertion, search, delete, traverse, source code analysis
  • Re-learn Java design mode, internal skill heart practice, 22 Real Internet business scenarios
  • DDD domain-driven design practice, domain-level decision tree service design