preface

Recently in view of the Internet company interview asked knowledge points, summed up the Java programmer interview involves most of the interview questions and answers to share with you, I hope to help you review before the interview and find a good job, but also save you on the Internet to search for information time to learn.

Content covers: Java, MyBatis, ZooKeeper, Dubbo, Elasticsearch, Memcached, Redis, MySQL, Spring, SpringBoot, SpringCloud, RabbitMQ, Kafka, Linux and other technology stacks.

Full version Java interview questions address: Java backend questions integration

The introduction

Inoculant: red black tree is the basic algorithm in the difficulty, so it is suggested to read this article a little preparation psychology or knowledge matting, did not contact RBT and directly read this article, absolutely meng force.

In order to facilitate the query, addition and deletion of data, the system introduces a binary search tree, which has the attributes of left node < and node < right node.

Binary search tree, but it depends a lot on the order in which the data is inserted, so if you’re inserting 1234, the binary search tree will degenerate into a linked list.

Linked list. In order to avoid the appearance of linked list structure, researchers also put forward balanced binary tree and red black tree. Balanced binary tree requires that the absolute value of the difference between the left depth and the right depth of any node should not be greater than 1. If the difference exceeds 1 after insertion, the connection changes will be changed through various rotations of left and right, and the requirement that the difference between the left and right depth is not greater than 1 will be finally realized.

The depth requirement of balanced binary tree is too perfect. When a large number of additions and deletions are involved, it may take too much time to adjust the balance. In order to balance the ratio of input and output, a red-black tree is designed.

Red-black trees are a bit of a complex data structure, unless you have a face byte that might let you write red-black trees by hand. Usually you just need to say the five logic behind red-black tree construction and show the depth and breadth of your understanding of the underlying data structure.

This article will not focus on the process of adding and deleting red black trees, because you baidu look at the authoritative tutorial or source code, and then follow the track to know the general process, this article will say why red black tree design, it has what connection with 2-3 trees.

The tree

define

In order to keep the search tree balanced, we need some flexibility, so we allow a node in the tree to hold multiple keys.

2 node: contains one key and two links, the left link points to the key of the 2-3 tree is smaller than this node, the right link points to the key of the 2-3 tree is larger than this node.

3 node: contains two keys and three links. All the keys in the 2-3 tree to which the left link points are smaller than this node, all the keys in the 2-3 tree to which the middle link points are between the two keys of this node, and all the keys in the 2-3 tree to which the right link points are larger than this node.

Four nodes: contains three keys and four links, similar to three nodes. It should be noted that in a 2-3 tree, four nodes exist temporarily and will be converted into two or three nodes.

To find the

To determine whether a key is in the tree, we compare it to the key at the root. If it’s equal to any of them, the search hits. Otherwise we find the link to the corresponding interval based on the result of the comparison and recursively continue the search in the subtree to which it points. If this is an empty link and the lookup fails, you can see that it is similar to a simple binary tree lookup.

insert

To insert a new node into a 2-3 tree, we can do the same thing as a binary lookup tree by doing a missed lookup and then hanging the new node at the bottom of the tree. But it’s not going to be perfectly balanced. The main reason for using a 2-3 tree is that it continues to balance after insertion.

If the missed lookup ends at a 2 node: simply replace the 2 node with a 3 node where the key to be inserted is stored. Insert new data into a 3-node tree: we can create a temporary 4-node tree and convert it to a 2-3 tree of 3 2-nodes

Only a 3-node tree inserts data

Insert a new key into a 3 node whose parent is 2: at this point, a temporary 4 node will be formed first, and then the middle number will be raised and merged with the parent into a 3 node, so that the height of the tree does not change.

Insert a new key 4 into a 3 node whose parent is 3: do the same as above, keep pushing up the median until you reach a 2 node, or reach the root node and split.

Insert summary:

Find the insert node first, if the node is 2, insert directly. If node 3, insert to temporarily accommodate the element, then split the node and move the intermediate element to its parent. Do the same for the parent. (The middle bond continues to move up until it finds a vacancy, in which case it makes a temporary one and then splits.) The essence of the 2-3 tree insertion algorithm is that these transformations are local: there is no need to modify or examine the rest of the tree except for the associated nodes and links. In each transformation, the number of links that change does not exceed a small constant. All local transformations do not affect the order and balance of the whole tree.

delete

The deletion of 2-3 trees can be divided into two cases.

If the element to be deleted is at node 3, the element can be removed directly without causing a height change.

Delete data on three nodes

When the element to be deleted is at node 2, the deletion of this element will cause the node 2 to lose the unique element and cause the height of a path in the tree to change. In order to maintain balance, there are two methods.

Delete first and then balance the 2-3 trees.

Find a way to make it impossible for the deleted element to appear in the 2-node. If two nodes in the element tree are found to be deleted, an element is borrowed from the sibling or parent node, the current two nodes become three or temporary four nodes, and then the target data is deleted.

Delete target data 2 in the 2-node scenario

structure

Instead of a standard binary search tree growing from the top down, 2-3 trees grow from the bottom up.

insert

Advantages and disadvantages

Advantages:

2-3 trees still perform well in the worst case. Each operation takes no more than a small constant to process each node, and both operations access nodes on only one path, so the cost of any lookup or insert is certainly not more than logarithmic.

Perfectly balanced 2-3 trees are much more flat. For example, a 2-3 tree with 1 billion nodes is only between 19 and 30 in height. We only need to access 30 nodes at most to do any lookup or insert in a billion keys.

Disadvantages:

There are two different types of nodes to maintain, lookup and insert operations require a lot of code to implement, and the extra overhead they incur can make the algorithm slower than a standard binary lookup tree.

The original intention of balancing a tree was to eliminate the worst case, but we wanted as little code as possible and as simple as possible, and obviously 2-3 trees were not a good fit either.

Now that we know the implementation of 2-3 trees, we’re going to make a slight variation of 2-3 trees to be red-black trees, and you can think of red-black trees as essentially an implementation of the conceptual model of 2-3-4 trees.

Red and black tree

The tree is associated with a red-black tree

Since direct transformation between different nodes would cause large overhead, we chose to add a color attribute to the attributes of the binary tree to represent different nodes in 2-3 trees based on the binary tree.

Two nodes in a 2-3 tree correspond to black nodes in a red-black tree.

The non-2 nodes in the 2-3 tree exist in the form of red node + black node. The meaning of the red node is combined with the black parent node to express the 3 and 4 nodes in the 2-3 tree. Some books say red as red link, but also always understand the method.

Let’s look at the node transformation from a 2-3 tree to a red-black tree. 2 nodes are directly transformed into black nodes. Three nodes can be represented in two ways, red left node or red right node. The four nodes are forced to transform into a black father with two red sons on the left and right.

23 tree to red black tree because you can turn left or right when you turn 3, if you look at the algorithm books, you’ll see that for the sake of simplicity, all of the algorithm books say only left red black trees.

When a red-black tree is converted to a 2-3 tree, it can be considered as a whole by raising the red node 45 degrees clockwise to balance it with its parent.

When a red-black tree is transformed into a 2-3 tree, it can be found that only the black nodes really increase the height of the 2-3 tree. Therefore, the perfect balance of the red-black tree is actually equivalent to the distance between the root node and the leaf node of the 2-3 tree. So red-black trees are an implementation of the conceptual model of 2-3 or 2-3-4 trees.

In the introduction to the algorithm red-black tree tree based on two-three-four tree realization.

In algorithm 4, the red-black tree tree is realized based on 2-3 trees, and 3 nodes must be represented by left-leaning red nodes in the red-black tree.

Two or three trees are definitely easier than two or three trees, so I’m going to focus on two or three trees.

Red black tree base definition with rotation

5 rules

There are two types of nodes: black and red: why there are red nodes is explained in 2-3 trees.

The root node must be black: in a 2-3 tree, if the root node is 2, it is black, if the root node is 3, it is black, and if the root node is small, it is left red.

The leaf nodes store no data and are all black: mainly for easy operation during insertion and deletion.

Any node to the leaf node of the node number is the same: black in the red and black tree binding, red and black is parent node in the 2-3 tree layer was the same, only black node real contribution in the 2-3 tree height, because of the 2-3 tree any node to null links distance is the same, so the reaction in the red-black tree is black perfect balance.

There will be no consecutive red nodes: it is stipulated that there are no four nodes in 2-3 trees. Although there are four nodes in 2-3-4 trees, it should be reflected in red-black trees as one black node with two red sons, distributed left and right, so there will be no consecutive red nodes.

Left and right

Red-black tree requires that the color of the newly inserted data be red, and black is the result of the change. The core of a red-black tree is left and right.

Left and right

Left-leaning red-black tree insertion

There are three possible scenarios for left-leaning red-black tree insertion.

The element to be inserted is larger than the black parent and inserted to the right of the black parent, while the red child is to the left of the black parent. This situation results in right-leaning red nodes in red-black trees. Or black father left is empty will also appear to the right.

Insert the 20

The element to be inserted is smaller than the red parent, and the red parent itself is left-leaning. The data to be inserted is smaller than the left node of the red parent, forming a continuous red node.

Perform a right rotation on the parent node of the red parent.

Change the data to state processing for case 1.

Insert the 14

The element to be inserted is larger than the red parent, and the red parent is itself left-leaning. The data to be inserted is larger than the left node of the red parent, resulting in a right skew. By turning left, it becomes case 2.

Insert 17 In general, the insertion of a left-leaning red-black tree is just going back and forth between these three things, and it’s going to balance out.

Left – leaning red – black tree removed

The deletion idea is not to delete the target data, but to find the precursor node or successor node of the target data, and then copy the data to the target data for overwriting. Then turn to deleting the precursor or successor. Delete and then repair the balance.

From a macro point of view, the search starts from the root node and adjusts the red-black tree layer by layer with 2-3 tree thinking in the whole process. Ensure that the current node tree 2-3 has no 2 nodes each time. If it is non-2 nodes, look at the next layer; if it is 2 nodes, adjust it according to the sibling nodes.

The sibling node is a 2-node node. It borrows data from the parent node to form a temporary 4-node with the current node and its siblings.

Sibling nodes are non-2-nodes. Sibling nodes go up by one and parent nodes go down by one.

Delete target 1 after deletion involves data balance repair, or according to the 2-3 tree repair balance, the road may encounter red right-leaning nodes, encounter a left turn can be.

2-3 Tree repair work

Industrial red black trees increased

In fact, here is mainly referring to the article of geek time Little Brother, say the operation of adding and deleting red black trees in the actual project, the increase mainly includes three situations:

Case 1: the attention node is A and its uncle node D is red:

Set the colors of the parent node B and the uncle node D of focus node A to black.

Set the color of the grandfather node C that focuses on node A to red.

The concern node becomes the grandfather node C of A to realize the migration of the concern node.

Skip to case 2 or case 3.

Case 2: The attention node is A, its uncle node D is black, and the attention node A is the right child of its parent node B:

Note that the node becomes the parent node B of node A.

Turn left around the new focus node B.

Jump to case 3.

Case 3: If the attention node is A, its uncle node D is black, and the attention node A is the left child node of its parent node B, we perform the following operations in sequence:

Dextrally rotates around the grandfather node C of focus node A.

Switch the colors of parent node B and brother node C of node A, and the adjustment is complete.

Industrial red black tree removed

Deleting is much harder than inserting! The core idea is to identify the focus and adjust it according to certain rules according to the focus and the surrounding node layout characteristics. There are two main steps:

After adjustment for the deleted node, the path from node to leaf node still contains the same black node.

Second adjustment for the concerned nodes to prevent two red nodes.

In the introduction to the algorithm, it is stated that if the black node X is deleted, the black balance is broken, and the child nodes of X become black-black or red-black. If you delete a black node, you will inevitably destroy the black balance on the path with the black node, which is represented by the absence of a black node in the path, so you need to find a way to add a black node (denoted by a black circle below). At the same time, if a node can be both red and black, it is represented by two components.

Delete the first step

Case 1: The node to be deleted is A, which has only one child node B:

Delete node A and replace node B with node A, this part of the operation is the same as the normal binary search tree deletion operation.

Node A can only be black, node B can only be red, otherwise it does not meet the definition of a red-black tree. Change node B to black. The second adjustment is not required.

Case 2: The node a to be deleted has two non-empty child nodes and its successor is the right child node C of node A:

If the successor of node A is right child c, then C must have no left subtree. Change the color of C to the color of A, and overlay A with C.

If node C is black, add a black circle to the right child node D of node C in order not to violate the principle of the same path in red-black tree, then node D becomes red-black or black-black.

At this point, the attention node becomes node D, and the adjustment operation in the second step will be performed for the attention node.

Case 3: The node to be deleted is node A, which has two non-empty child nodes, and the successor of node A is not the right child of node A:

Find the successor node D and delete it. Refer to CASE 1 for the process of deleting the successor node D.

Replace A with D, and the color of D is set to the same color as A.

If node D is black, add a black to the right child node C of node D in order not to violate the principle of the same path in red-black tree, then node C becomes red-black or black-black.

At this point, the attention node becomes node C, and the adjustment operation in the second step will be done for the attention node.

Delete step 2

After initial adjustments, the focus nodes become red-black or black-black nodes. In view of this concern node, the second adjustment is carried out in four cases. The secondary adjustment is made so that there are no adjacent red nodes in the red-black tree.

Case 1: the concerned node is A, and its sibling node C is red, so we perform the following operations in turn:

Rotate left around the parent node B of focus node A.

Note that the parent node B and the grandfather node C of node A swap colors.

Focus on the same node, continue to choose the appropriate rule from the four cases to adjust.

Case 2: Focus on node A, its sibling node C is black, and the left and right child nodes D and E of node C are black:

Change the color of c, the sibling of node A, to red, because then the black circle moves up, so c is darker than A.

If a black is removed from node A, node A is simply red or black.

Add a black color to the parent node B of node A, and node B becomes red-black or black-black

Watch the node change from A to its parent b, and continue to adjust by selecting the rule that matches the four cases.

Case 3: The node concerned is A, its sibling c is black, the left child D of C is red, and the right child E of C is black:

Dextrally rotates around c, the sibling of focus node A.

Nodes C and D switch colors.

Pay attention to the same node, go to situation 4, continue to adjust.

Case 4: Notice that the sibling node C of node A is black, and the right child node of c is red, so we proceed as follows:

Rotate left around the parent node B of focus node A.

Copy the color of B to C, because C is taking the place of B.

Set the color of the parent node B that focuses on node A to black.

If a black is removed from the focus node A, node A becomes simply red or black.

Set node E, which is concerned with node A, to black.

At this point, the depth of A and D is the same. Since it is impossible to tell whether AD is red, B is directly set to black. At this time, E is raised by one degree and also set to black to maintain balance.

Delete the understanding

Drawing more pictures, not drawing more pictures just looking at the code for a while makes me dizzy.

Both insertion and deletion algorithms use recursion, such as case 1. After case 1 is inserted, the focus node changes from itself to its grandfather red node, which is recursion to the root node. But once you’ve dealt with case 1, you don’t have to go to case 2 or case 3, you might still be in case 1. In case 1, go all the way to the root node, because the current node is always red, so you have to black out the root node at the end. And as soon as we go to case 2 and case 3, we’ll do something similar.

Remember that all subtrees, except the subtree of the node in question, are themselves red black trees that satisfy all the characteristics of a red black tree. When the attention node recurses to the root node, the subtree of the attention node already satisfies the definition of red-black tree, so we don’t have to pay special attention to the characteristics of the subtree. Just pay attention to the part above the node. This will simplify the problem and make you think more clearly.

When it comes to deleting algorithms, notice why red-black and black-black exist, and why they both end up in the same place as their siblings to achieve the final balance.

The purpose of deleting case 1 is simply to get into the next three cases.

Delete case 2 is another recursion, focusing on the node recursion to the root node, so that the left and right subtrees meet the definition of red-black tree. Because the right subtree has a black node, it turns the sibling of the concerned node red.

Case 3 was deleted to enter case 4, and the reason for early discoloration was the same as case 2, in order to satisfy the same black depth. Again, inductive reasoning. Remember, all of the other subtree nodes in all of the cases meet the definition of a red-black tree, and all of the things we need to categorize and talk about are in all of these cases.

Maybe you saw the deletion of the red-black tree today and you had an Epiphany. After half a month, you were confused again. Don’t be afraid! Because being scared doesn’t help. Watch it again. Learning red black tree itself is not to interview bytes to write, but to learn thinking, exercise thinking, complex problems to simplify, of course, can also be installed in a good hand B.

conclusion

The focus of this paper is not to explain the entire process of deletion and insertion of industrial red-black trees, but just hope that through the addition and deletion of 2-3 trees and left-leaning red-black trees, let everyone understand the operation source of red-black trees from the essence. The industrial deletion part has been agreed by the little brother, if you understand the above content, then you can see the operation of the industrial red black tree.