编程知识 cdmana.com

Complete the deployment and release of distributed structure services and java video resources in three minutes

Two 、 Interview questions

Noodles : Test your knowledge of red and black trees ??

  1. In which scenarios are the data structures of red and black trees used , What are the benefits ?
  2. What is the time complexity of red black trees ?
  3. How to keep balance when inserting new nodes into a red black tree ?

Noodles :2-3 The trees are not looking , Go back and wait for the news !

3、 ... and 、2-3 The equivalence of tree and red black tree

Red and black tree rules

1.  The root node is black 
2.  The nodes are red, black or black 
3.  All cotyledon nodes are black ( Leaves are NIL node , It is not drawn by default )
4.  Each red node must have two black child nodes ( It also indicates that a link cannot have red nodes of the link )
5.  Black high , From any node to every leaf node , The paths that pass through contain the same number of black nodes 


     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.

that , How are these rules summed up and defined ? Next, we will analyze and explain step by step .

1. Why there are 2-3 Black trees need mangroves

First 2-3 Trees ( How to read : Two or three trees ) It's a node that has 1 A or 2 Elements , But in fact 2-3 Tree to red black tree is a conceptual model 2-3-4 Trees Transformed from .-4 fork It's a node with 3 Elements , This is in 2-3 The tree will be adjusted , But it will be preserved in the conceptual model .

although 2-3-4 Trees Also have 2-3 Trees The same characteristics of balanced trees , But if you directly code such a model, it will be very troublesome , And low efficiency , The complications here include ;

  1. 2- fork 、3- fork 、4- fork , Node types of three structures , The complexity of mutual conversion is high
  2. 3- fork 、4- fork , Nodes need to compare data multiple times , Unlike 2- Cross node , Direct boolean type comparison is OK Either the left or right
  3. Code implementation for each difference , All need extra code , The rules are not standardized enough

therefore , Hope to find a balance , Both maintain 2-3 Trees balance and O(logn) Characteristics of , It can be more convenient in code implementation , Then red and black trees were born .

2. Simple 2-3 Trees turn red and black

2-3 Trees Turn the red and black tree , It can also be said that red and black trees are 2-3 Trees and 2-3-4 Trees Another form of expression of , In other words, it is more conducive to the form of coding implementation .

Simple conversion example ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer

As can be seen from the above figure ,2-3-4 The transformation relationship between tree and red black tree , Include ;

  1. 2- Cross node , The conversion is simple , Just convert the original node to a black node
  2. 3- Cross node , It includes 2 Elements , First connect the two nodes with a red line , And then split it out , Finally, adjust the height The black nodes are on
  3. 4- Cross node , It includes 3 Elements , Connect them with red and black wires respectively , And then split it up and pull it up . The pull-up process and 2-3 The trees are aligned , Just added color

Sum up , Namely 2-3-4 Tree node transformation , Summed up the rules , as follows ;

  1. take 2-3-4 Trees , In the form of a binary tree
  2. 3- fork 、4- Cross node , Use red 、 Black wire to connect
  3. in addition ,3- There are two cases of cross nodes , Causes the conversion to a binary tree , There's left leaning and right leaning

3. complex 2-3 Trees turn red and black

stay Simple 2-3 Black tree conversion In the process of , Learn a basic conversion rule, right-handed definition , Now we're going to do a little bit more complicated 2-3 Trees The corresponding relationship with red and black trees , Here's the picture ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_02

The picture above is a little more complicated 2-3 Trees , The process of converting to a red black tree , Is this a picture that makes you feel more about red and black trees , At the same time, it also satisfies the following conditions ;

  1. From any node to leaf node , The same number of black nodes passed through
  2. Black nodes keep the overall balance , That is to make the whole red black tree close to O(logn) Time complexity
  3. Other characteristics of red and black trees are also satisfied , It can be compared with the characteristics of red and black trees

Four 、 Red and black trees

1. Balance operation

Through the last chapter 2-3 Tree learning , When inserting a node, it does not insert into an empty position , It's about merging and adjusting with existing nodes , Keep the whole tree in balance .

And the red and black trees are 2-3-4 A conceptual model of tree is transformed from , When inserting nodes, they are connected by a red link , That is to insert a red node . Adjust after insertion , To keep the tree close to balance .

that , In order to balance the red and black trees , It mainly includes dyeing 、? Spin around 、 These practices are actually from 2-3 Trees evolved . Next, we will explain the evolution of several rules , In order to better understand the balance operation of red and black trees .

1.1 Left rotation

Left handed definition : Link a red node to the right (2-3 Trees ,3- Cross double element node ), Convert to left link .

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _03

background : Insert elements in sequence ,1、2、3,2-3 Trees keep balance , The red and black trees are leaning to the right for the time being .

Next, we compare the balancing operations of the two tree structures ;

  1. 2-3 Trees , All inserted nodes remain on one node , Then by adjusting the node position , balance .
  2. Red and black trees , You need to rotate through the left side of the node , Put the element 2 Pull it up , Elements 1 And elements 3, They are left and right child nodes respectively .

The left rotation of red and black trees , Only deal with the corresponding 2-3 Tree node to operate , It doesn't change the whole thing .

1.2 Right rotation

Right handed definition : Connect a red node that tilts to the left (2-3 Trees ,3- Cross double element node ), Convert to right link .

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_04

background : Insert elements in sequence ,3、1、1,2-3 Trees keep balance , The red and black trees are leaning to the left for the time being .

Next, we compare the balancing operations of the two tree structures ;

  1. 2-3 Trees , All inserted nodes remain on one node , Then by adjusting the node position , balance .
  2. Red and black trees , You need to rotate through the right side of the node , Put the element 2 Pull it up , Elements 1 And elements 3, They are left and right child nodes respectively .

You'll find that , Left and right rotation are corresponding to each other , But in 2-3 It's the same in the tree

1.3 Comprehensive use of left and right rotation

left-handed 、 Right hand , We have a basic concept , So let's look at another one that can combine left and right rotation and corresponding 2-3 The case of tree evolution , as follows ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _05

The above examples demonstrate three cases of an element insertion , as follows ;

  1. 1、3, Insert 0, Insert at the bottom of the left side , And 2-3 Trees are compared to , You need to turn right to balance
  2. 1、3, Insert 2, Insert in the middle , First, rotate left to adjust the element position , And then right-handed to balance the tree
  3. 1、3, Insert 5, Insert right position , At this point, the tree is in balance , There is no need to adjust

1.4 dyeing

stay 2-3 In the tree , Insert a node , In order to keep the tree balanced, it is not inserted into the empty position , When the node is inserted, the number of elements is 3 After that, you need to adjust the middle element upward , To keep the tree in balance . The corresponding red and black trees need to adjust their colors , To ensure the balance of red and black trees , Specific reference is as follows ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The backend development _06

2. rotate + Dyeing application cases

Next, we will explain the above rotate dyeing , In a practical case , Here's the picture ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _07

  • Start with the left side , It's a red black tree produced by inserting it in sequence , Insertion order ;7、2、8、1、4、3、5
  • α, Insert elements into the current red black tree 6, After insertion, there are three red nodes in the lower right corner ;3、5、6.
  • β, Because the lower right corner meets the dyeing condition , After transformation ; Black node (3、5)、 Red nodes (4、6).
  • γ, Then look at the nodes linked by the red line 7、4、2, The smallest node is in the middle , Left handed equilibrium tree structure .
  • δ, When the left turn is done , Red link 7、4、2 To do the tilt order node , So you need to do a right-handed operation .
  • ε, left-handed 、 Right hand , After adjustment , It also satisfies the dyeing operation . Here we restore the balance of the red and black trees .

Be careful , All connected to the red nodes , It's all red . In this way with 2-3 Trees do the corresponding .

3. Delete operation

according to 2-3-4 Tree model of the red black tree , When deleting, it is basically in accordance with 2-3 Method to delete , It's just that in this process you need to dye and rotate , To keep the tree in balance . The deletion process can be divided into four cases as shown in the figure , as follows ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _08

3.1 Delete cotyledon red node

The deletion of red cotyledon nodes does not break the tree balance , It doesn't affect the tree height , So delete it directly , as follows ;

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The backend development _09

3.2 Delete the left node

3.2.1 The abridged brother is black & With right child nodes

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_10

3.2.2 The abridged brother is black & With left child nodes

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_11

3.2.3 The abridged brother is black & There are two nodes ( red )

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The backend development _12

3.2.4 The abridged brother is black & No child nodes

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _13

3.2.5 The abridged brother is black & With double black nodes ( black )

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_14

3.3. Delete the right node

3.3.1 The abridged brother is black & With left child nodes

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The backend development _15

3.3.2 The abridged brother is black & With right child nodes

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The backend development _16

3.3.3 The abridged brother is black & There are two nodes ( red )

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_17

3.2.4 The abridged brother is black & No child nodes

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_18

3.2.5 The abridged brother is black & With double black nodes ( black )

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_19

Finally, summarize my interview experience

2021 In the blink of an eye , It's a good opportunity for many people to change jobs , It's not as difficult as we think , Set your mind , To prepare , You can do that, too .

in addition , If you don't have any questions in the interview, try to talk about your own ideas , Because some questions are not about our programming ability , It's about logical thinking and expression ; Finally, self analysis and evaluation should be carried out at ordinary times , Make a career plan , Trial and error , Improve your programming ability and abstract thinking ability .

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _20

BAT The interview experience

Practical series :Spring Family bucket +Redis etc.

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_21

Other related e-books : Source code + tuning

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _22

The real question of the interview :

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _Java_23

 Complete the deployment and release of distributed structure services in three minutes ,Java Video resources _ The programmer _24

This article has been  CODING Open source project :【 A big factory Java Analysis of interview questions + Core summary learning notes + The latest explanation video + Actual project source code 】 Included

版权声明
本文为[SDK integrated development]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211002011430047v.html

Scroll to Top