当前位置:网站首页>Hard core graphic interview most afraid of red and black trees

Hard core graphic interview most afraid of red and black trees

2020-12-06 19:29:47 Ao Bing

Have feelings , There are dry goods , WeChat search 【 Three Prince Ao Bing 】 Focus on this different programmer .

this paper GitHub https://github.com/JavaFamily Included , There is a complete interview site for a large factory 、 Materials and my series .

notes : This article is hard core, but it's worth reading , You'll get something after reading it

Red black tree is a very classic and difficult knowledge point in the interview , This is the question that interviewers like to ask . Many people will find this knowledge point too difficult , I don't want to spend too much time understanding , Some people think that this data structure is rarely used in daily development , So there's no need to master more .

Here I make some corrections to the above two views : First , The data structure of red black tree is really complex , But it's not at all incomprehensible . Most of the online blogs can not clearly and completely describe the whole system of red and black trees , There is no detailed introduction to the details of red and black balance adjustment , Therefore, it brings great difficulties to study .

secondly , Such as Java in HashMap The underlying implementation of , stay JDK1.8 In order to solve the long list caused by excessive hash conflict , Will turn the list into a red black tree ;Linux At the bottom CFS In the process scheduling algorithm ,vruntime Use red and black trees for storage ; Multiplexing technology Epoll Its core structure is also the red black tree + Double linked list .

We're not going to write a usable red black tree , But understand the structure of red and black trees , It helps us to understand some of the underlying concrete implementations . meanwhile , Red and black trees are also a highly integrated use of tree structure , It's about multitree , Tree balance adjustment , Node rotation and so on , These are the best experiences for the basics of data structure .

In fact, when the interviewer asked this question , Without reference to the answer , He probably can't give a clear definition and operation . But he wanted to start with this question , See your understanding of a data structure , Examine the breadth and depth of your knowledge . Can we give a complete definition of , Can you introduce your knowledge of red and black trees , Can you rotate , Coloring and other operations in a given scene to adjust a red black tree to meet the definition … That's what the interviewer wants from your answers , Asked a circle of interviewers around the big factory friends , It's not very different from what I said .

After reading this article , You will be able to get from the red black tree concept model 2-3-4 The tree set out , Understand the logic behind the five definitions of red black tree . You can also deeply understand the meaning behind the color of red and black nodes , Have a certain understanding of the dynamic changes caused by insertion and deletion , It's no longer a matter of hard memorizing the leveling operation in a certain scene ( Such as : Delete a node , When the uncle node of the node is red , When the left and right child nodes of the uncle node are all black , We should be …). You can master the specific operation of node rotation , Understand the purpose of dyeing .

Last , If you're serious enough , There are clear insert and delete steps in the diagram , You can really turn red and black trees into your own knowledge .

Let's talk about the balanced tree

Do development friends must know the interface of this thing : Defining interfaces , Give the implementation . An interface can have many different implementations , But these implementations will satisfy the declaration in the interface .

for example , We define a mobile phone as a communication tool , As an implementation of it , samsung , Apple , Huawei has launched a variety of products .

The essence of red and black trees is also a conceptual model :2-3-4 Trees An implementation of , So let's focus on 2-3-4 Trees .

2-3-4 Trees are Order by 4 Of B Trees ,B Trees , full name BalanceTree, Balance tree . This structure is mainly used for searching .

About B Trees ( Balance multiple search trees ) The definition of , There are many introductions on the Internet , I won't go into more details here . Its most important feature is balance , This allows us to keep... In the worst case O(LogN) The time complexity of the implementation of the search ( An unbalanced look-up tree may degenerate into a single linked list , The time complexity is going to be O(N)).

I need to remind you that , The definition of balance is that the distance from the empty link to the root node is equal , It's important to understand .( In other words, there will be no empty links in non leaf nodes )

because 2-3-4 A tree is a tree of order 4 Of B Trees , So it will have the following nodes :

  • 2 node
  • 3 node
  • 4 node

2 The node holds a key[X], Two pointers , Respectively point to less than X And is greater than X Child nodes of ;3 Nodes are stored in two key[X,Y], Three pointers , Respectively point to less than X Child nodes of , Be situated between X~Y Between the child nodes and greater than Y Child nodes of ;4 Nodes can be analogized .

 Node Introduction

2-3-4 The transformation from tree to red black tree

Red and black trees are a pair of conceptual models 2-3-4 An implementation of trees , Because the direct conversion between different nodes will cause a lot of overhead , So the choice is based on a binary tree , Add a... To the properties of the binary tree color property To express 2-3-4 Different nodes in the tree .

2-3-4 In the tree 2 The node corresponds to the black node in the red black tree , and 2-3-4 The non in the tree 2 The node is based on Red node + Black node The way , The meaning of the red node is to combine with the black parent node , Expressing 2-3-4 In the tree 3,4 node .

( Red node is also understood here , Red links are good , Depending on personal preference . Many books will say that the red link is pointed out by the black node , The color of the node that the link points to is red .)

We see first 2-3-4 Node conversion from tree to red black tree .2 Nodes are converted directly to black nodes ;3 Node here can have two forms , Left leaning red node or right leaning red node . and 4 Nodes are forced requirement Turn into a black father with two red sons on his left and right .

B The transformation from tree to red black tree

The main body of this paper is 2-3 Trees ( The reason will be given later ), And is 2-3 A special transformation in trees – Left leaning red black tree . seeing the name of a thing one thinks of its function , The left leaning red black tree limits if there are red nodes in the tree , Then this node must be the left son .

Here's how it's transformed :

B The transformation from tree to red black tree

The transformation of a single node may not be obvious enough , I made one Red and black trees turn 2-3 Trees Schematic diagram , It clearly depicts the relationship between them .

Just put the red nodes in the left leaning red black tree Rotate clockwise 45° Make it parallel to the black father , And then think of them as a whole , You'll find out , This is not just a 2-3 Trees ?

B The transformation from tree to red black tree

thus , I think you already understand , Red and black trees are actually conceptual models 2-3 Trees ( perhaps 2-3-4 Trees ) An implementation of .

In the introduction to the algorithm, the red black tree is based on 2-3-4 Tree implementation , among 4 Nodes require balance ( namely 4 The node must be represented by a black father and two red sons on the left and right , Red sons can't be on the same side ).

Algorithm 4 The red and black trees given in are based on 2-3 Tree implementation , And this realization of the red black tree Very special , It requires... In the conceptual model 3 Nodes in a red black tree must be represented by left leaning red nodes . This kind of restriction can greatly reduce the complexity in the adjustment process of red black trees , We'll see that in the next section .

I will Introduction to algorithms and Algorithm 4 The red and black trees in China have looked at it several times , Finally choose the algorithm 4 The red and black trees in the show are the main body of the demonstration .

  • First , Algorithm 4 The red and black trees in China are based on 2-3 Tree conceptual model , Don't have to consider 2-3-4 Complex in the tree 4 Node splitting ;

  • second , Algorithm 4 The red and black trees in China are Left leaning red black tree , Further reduces the difficulty of leveling ;

  • Third , In the introduction to the algorithm, the red and black tree deletion scene is described and Not specific enough , Many key links use “ After a certain amount of rotation and discoloration ” I've come to bring , It's not good for beginners to learn .( It took me a long time to restore the process ).

    Considering that some readers have enough energy to study 2-3-4 Trees Red and black trees for conceptual models , Introducing 2-3 The tree will also bring 2-3-4 The basics of trees , Help the readers who have spare time to understand the red and black tree in the introduction of algorithm .( So if it's not necessary , Just look at 2-3 Just the part of the tree ).

Before we learn about the insertion and deletion of red black trees , You need to know 2-3 Insertion and deletion of trees , In this way, we can understand the meaning behind dyeing and rotation in red and black trees .

Let's take a look at 2-3 Insertion of trees . Our insert operation needs to follow a principle : First try to put this element in In existing nodes , If the node to be stored is 2 node , Then it will become 3 node , If the node to be stored is 3 node , Then it will become 4 node ( temporary ). then , We can generate temporary 4 Nodes are split , Make temporary 4 Nodes disappear .

2-3 Insertion of trees
If you need to 2-3-4 From the tree to 4 Insert elements into nodes , Then it will trigger something like Shown below The splitting process of

2-3-4 Insertion of trees

in fact , This corresponds to the fact that the red black tree will paint the nodes to be inserted red when inserting , Because the meaning of the red node is Associate with the parent node , Form a conceptual model 2-3 In the tree 3 Or temporary nodes 4 node .

The reason why red black trees need to be adjusted after insertion , It's because there may be Temporary in the conceptual model 4 node ( The reaction in red and black trees is double red ).

Imagine being in 2-3 If the node to be inserted in the tree is a 2 node , So it's reflected in the red and black trees , Doesn't it correspond to the black parent node , Add a red son under the black parent node , It really doesn't violate any of the rules of the red black tree , This also corresponds to our direction to 2-3 In the tree 2 The node inserts an element , Just a simple handle 2 The node becomes 3 node .

Now let's take a look at 2-3 Delete tree . about 2-3 Tree deletion we mainly consider the elements to be deleted in 2 Node this situation , Because if the element to be deleted is in 3 node , Then you can delete this element directly , Without breaking 2-3 Any property of a tree ( Deleting this element does not change the height ).

When the element to be deleted is in 2 Node time , Because deleting this element will result in 2 Nodes lose themselves The only element , trigger 2 Deletion of node itself , It will change the height of a path in the tree , The tree becomes out-off-balance .

So we have two solutions to this problem :

  • First option , First delete this 2 node , Then balance the tree .

  • Second option , We try to make it impossible for this deleted element to appear in 2 In nodes .

This paper chooses the second scheme , We are searching the path to this node , Constantly judge whether the current node is 2 node , If it is , Borrow an element from its sibling or its parent , Make the current node from 2 The node becomes a 3 Node or a temporary 4 node ( As the case may be , In the later section of the red and black trees, we will introduce in detail ).

This kind of operation produces a result : Unless the current node is the root node , Otherwise, the parent of the current node must be a non 2 node ( Because the search path is top-down , The parent node has already done this , So it can't be 2 node ), So we can make sure that when we reach the leaf node , It can also borrow elements from parent nodes or sibling nodes , Make yourself wrong 2 node . This allows you to delete an element directly ( Now this element is not in 2 Node in ).

2-3 Delete tree

Look at the red and black trees

 Nodes of the red black tree

Let's look at the five definitions :

1. Node colors are red and black

【2-3 The transformation from tree to red black has been explained 】

2. The root node must be black

【2-3 If the root node in the tree is 2 node , So it is corresponding to the black node in the red and black tree ; If the root node is 3 node , You can also use black nodes to represent the larger element , Then smaller elements exist in the red black tree as left leaning red nodes 】

3. All leaf nodes are black

【 The leaf mentioned here is actually an empty link , Because of the space problem, it's inconvenient to draw all of them 】

####4. The number of black nodes passing from any node to leaf node is the same

【 The red node in the red black tree is bound to the black parent node , stay 2-3 It's the same layer in the tree , Only black nodes are in 2-3 It's true in the tree Contribution height , because 2-3 Any node of the tree has the same distance to the empty link , So the reaction in red and black trees is Black is perfectly balanced

5. There will be no continuous red nodes

【2-3 There is no rule in the tree 4 node ,2-3-4 Although there is 4 node , But the requirement is reflected in the red black tree as a black node with two red sons , Distribution around , So there will be no continuous red nodes 】

Believe in your perspective , Red and black trees are no longer these five rigid definitions , Behind it is a 2-3 Tree conceptual model . Although you already have this understanding , But red and black trees as real Implementation model , We still need to go back to the implementation itself to explore its series of operations . Before the start , I've prepared two basics , I hope I can help you .

1. As a binary search tree

The node of a binary search tree has an element X And two pointer fields , The left pointer is less than X The elements of , The right pointer is greater than X The elements of .

Suppose our insertion sequence is 1~10, Then the tree will evolve into a form with only right links , The height of the tree will increase to 10 layer , At this time, there is no such thing as O(LogN) The search time complexity , Because of this tree degeneration It's a linked list .

Therefore, it is very important to adjust the balance of binary tree , Whether it's AVL Or red and black trees , In essence, they all want to ensure that the elements in the binary search tree are evenly distributed on both sides of the tree as much as possible .

When we insert an element into a binary search tree Y When , We will always size with the nodes in the tree Compare , If Y Less than the current element , Just go left , If Y Larger than the current element , Go right , Until the leaf node is reached , At this time we can put Y Insert this binary search tree .

Because of this insertion , There may be some imbalance in the whole tree , So we need to do it once after insertion Balance adjustment , To bring the whole tree back to equilibrium ( How to adjust , It depends on the trees AVL Or a red black tree or some other balance tree ).

The deletion of binary search tree is an interesting problem , Different from what's inserted is , The element to be deleted is not guaranteed to appear in the leaf node of the tree . It's going to create a tricky situation , That is, we need to take an element from the middle of the tree , And it needs to be adjusted after taking it away The whole tree is balanced The nature of . There are too many scenarios where you take a node directly from the middle of the tree , Too many related nodes are involved , It's hard to do this .

Fortunately, a point has been made , We delete a node in the search tree , In fact, you don't have to change the location of this node . Because of the special properties of the search tree , After deleting an element node , It has two best substitutes , They are in an ordered sequence Precursor and successor elements .

We still use an inclusion element 1~10 Take the binary search tree for example , If we want to delete 5 The node , So let's 4 perhaps 6 It's all possible to replace it . As a precursor element 4, Will be stored in a 5 The most right side of the left subtree of the node ; As a successor element 6, Will be stored in a 5 The left most side of the right subtree of the node .

About this conclusion , It takes only a little thought to understand .

Now let's simplify the problem again , in other words , When you delete a node , Let's first find its precursor or successor ( Pick one at random ), Fill its precursor element directly into the node to be deleted , Then delete its predecessor or successor .

In this case, the problem is to delete a node without a left subtree in the binary search tree ( Or a node without a right subtree ), We just need to delete this node and adjust the balance accordingly ( Even though it still needs leveling , But it's much easier than deleting a node with both left and right sons in the middle of the tree ).

Be careful , It is not emphasized here that in the light of Operation of red black tree , Because of the red and black trees and AVL All are Binary search tree , They all apply this method .

Let's introduce the rotation of the tree

To level out a binary tree , The number of left and right nodes is evenly distributed , You usually choose to rotate . You can think of the left and right subtrees of a node in a binary tree as objects to be weighed on a balance , If which side is heavy , Let's take some from the heavy side , Add it to the light side , In order to keep the relative average .

In a binary tree, the operation of this adjustment is rotation , Here are two examples , I hope you can explore , Rotation is the essence of binary tree leveling .

Let's introduce the rotation of the tree

 Rotation of trees

After understanding these , Go to see the insertion and deletion of red and black trees , You can understand the meaning behind rotation and dyeing .
We choose the algorithm 4 The left leaning red and black trees in the : First of all to see Insert

 The insertion of the left leaning red black tree

As shown in the figure , There are three possible scenarios for the insertion of a left leaning red black tree .

  • The first one is , The element to be inserted is larger than the black parent , It's on the right side of black father , On the left of the black father is the red son . This can lead to right leaning red nodes in red black trees .

    Be careful , This situation corresponds to 2-3 In the tree temporary 4 node , We are 2-3 The processing in the tree is to put this temporary 4 Node splitting , The left and right elements each form a 2 node , The middle element rising Go to the upper level and combine with the parent node . therefore , Our action in the red and black trees is , Black the original red son ( Split left and right ), Dye black father red ( Waiting for the rise to combine ).

     The insertion of the left leaning red black tree

  • The second case , The element to be inserted is smaller than the red parent , And the red Father himself is left leaning . It sounds a little convoluted , Look at the picture and you will see , In fact, the red father and the element to be inserted At the same time, leaning on the left , A continuous red node is formed .

    We need to adjust this situation in two steps . Because we're inserting red nodes , It doesn't break the perfect balance of black , So it's important to note that during the rotation and dyeing process, the species continues to maintain this Perfect black balance .

    First of all, a right-hand rotation of the red father's father , This right spin won't upset the black balance , But it doesn't solve the problem of continuous red .

    The following will 12 The node is related to 15 Switch colors between nodes , The goal is to eliminate the continuous red , And this operation still maintains the black balance . Now we have the situation 1 Scene , Directly by situation 1 Processing can be .

     The insertion of the left leaning red black tree

  • The third case , The element to be inserted is larger than the red parent , And the red Father himself is left leaning .

    That is to say, the inserted node forms a right leaning red node , Yes Right deviation It's easy to deal with , Give the red father a left turn , So that the right leaning red node becomes the left leaning node , Now there are continuous left leaning red nodes , Directly by situation 2 Processing can be .

     The insertion of the left leaning red black tree

When inserting , You can appreciate the benefits of left leaning red and black trees for left leaning restrictions , Because if the original tree meets the definition of red black tree , If the father is red , Then it It must be left , And don't worry about the possible right leaning brothers ( If there is , That means The original tree does not meet the definition of red black tree ).

This limitation eliminates a lot of scenarios to consider , Make insertion easier .

The deletion of left leaning red and black trees

The deletion of left leaning red black trees needs to learn from the above mentioned The general deletion strategy of binary search tree , When we want to delete a node, select its predecessor node or successor node element replace it , Instead, delete its precursor / The subsequent nodes .

In this case , I choose to replace the deleted node with a successor node .

Suppose we need to delete the node, its right subtree is shown in the figure , Then the deletion of the node actually turns to the deletion of 2 The deletion of .

Let's start with the current root node , Good for 2-3 The strategy of merging the black trees is adjusted step by step . Here's how , Ensure that the current node is 2-3 The non in the tree 2 node , If the current node is already not 2 node , So just skip ; If the current node is 2 node , Then adjust according to the status of the sibling nodes :

  • If the brother is 2 node , Then borrow an element from the parent node to the current node , And then, together with the sibling nodes, form a temporary 4 node .

  • If brothers are right and wrong 2 node , So brothers raise an element to the parent node , At the same time, the parent node drops an element to the current node , Make the current node a 3 node .

Such a strategy can ensure that when the node is to be deleted finally , It must be a non 2 node , We can delete its elements directly .

 The deletion of left leaning red and black trees

The next thing to consider is Repair work , Due to the limitation of the definition of red black tree , In the process of adjustment, we have some things that should not have existed Red right node ( Because of the generation of temporary in the conceptual model 4 node ), So we went up in the direction of the search to flash back , If the current node has a right leaning red son , Then we do a left rotation to the current node , At this time, the original right son will come to the current node position , Then the right son is swapped with the current node for color , So we fixed the right leaning red node to the left leaning red node , At the same time, we didn't break the balance of the black nodes .

 The deletion of left leaning red and black trees

Tilt right to tilt left is a very basic operation , We use 35,44 For example , You can put 35 As a black node ,44 As a right leaning red son ; Can also be 44 As a black node ,35 As a left leaning red son . In fact, our restoration of the right tilt is a different kind of Tree form nothing more . All the way back to the current root node , Until the path no longer contains whatever The red right node of , So far, the repair work has been completed .

summary

The purpose of this article is to start with a conceptual model 2-3 The tree starts to introduce the past and present life of a red and black tree . I hope you can jump out of the boring five definitions , More essential understanding of the various operation sources in red and black trees .

Although this article only introduces the relatively simple left leaning red and black trees , But if we can make a clear understanding of the left leaning red and black trees , So ordinary red and black trees are just a few more situations .

For readers who still have the energy to read the introduction to Algorithms , I'll give you a little bit of my own experience :

  • The insertion stage is similar to that of the left leaning red black tree

  • Some nodes in the diagram are not clearly identified , Read again and again

  • Delete phase , The black node will be deleted in the introduction to the algorithm X The resulting black balance disruption is explained as , to X Add an extra layer of black to the child nodes of the , Give Way X The child node of becomes 【 Double black 】 perhaps 【 It's black and red 】 Of .

    I don't really accept this explanation , After considering , I think this expression can be more direct : Now that a black node has been deleted , Then it will certainly destroy the black balance on the path with this black node , It shows that there is no black in the path .

    If you study the four deletion scenarios in the introduction to the algorithm , What they are doing is actually trying to move a black node from the path of the brother node .

    therefore , If you really can't understand 【 Double black 】,【 It's black and red 】, So directly according to “ Some path is not black , So find a way to add a black node ” Think about it in this way !

  • Or delete phase , How to remember the four deleted scenes ? Let's assume that we delete a left leaning node , In fact, three factors determine the scene change : The brother color of this node ; Brother's left and right, son's color ; The color of the parent node of this node . It is roughly estimated that there is 2x2x2x2 common 16 In this case . It's actually going to be a lot less , We start with the color of our brothers . Please note that if the brother is red , So the father and brother's son of the current node are actually black . And when brothers are black , We just need to satisfy the brother that the right son is red , You can achieve balance through one adjustment ( For details, please refer to the introduction to the algorithm ).

    Another reminder is , Be sure to think about the order of memory . Delete leveling in introduction to algorithm 4 In these cases , Only the situation 4 It's the absolute final state , That is to say, after reaching this state, only one adjustment is needed to reach the balance . So our starting point must be from this state , For several other cases , It's not how we want to reach the balance in the end , It's about how to turn it into a situation step by step 4. In this way, your thinking will be much clearer , The pressure of memory will also be reduced . If you are careful , You can recall the order in which this article introduces the insertion of left leaning red and black trees , Why is this order ?

  • A data structure visualization website , Its red and black trees are based on 2-3-4 Treelike , It's basically the same as in the introduction to algorithms ( Except when deleting the precursor / Selection of successor nodes ), You can use it as a test .https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

At the end

Last , If you're asked about the red black tree , Maybe you can try asking the interviewer a question :“ You should know five definitions of red black tree , If I build a red black tree with only black nodes , Is this feasible ? Because it doesn't break any of the rules of red and black trees .”

If his answer works .

Keep asking :“ What do red nodes do in red and black trees ? What is the real meaning of the red node ?”

Your story begins , And your algorithm story and I are just beginning .

Chatter

Ao Bing organized his interview articles into an e-book , common 1630 page !

Dry cargo is full. , The essence of words . Directory as follows , There are also interview questions and resume templates that I summarized when I reviewed , Now it's free .

link :https://pan.baidu.com/s/1ZQEKJBgtYle3v-1LimcSwg password :wjk6

I'm aobing , The more you know , The more you don't know , Thank you for your : give the thumbs-up Collection and Comment on , See you next time !


Articles are constantly updated , You can search through wechat 「 Three Prince Ao Bing 」 First time reading , reply 【 Information 】 I have the interview materials and resume template for the first-line large-scale factory , this paper GitHub https://github.com/JavaFamily Included , A complete interview site for a large factory , welcome Star.

版权声明
本文为[Ao Bing]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206192753556h.html