The concept of red black tree

Special binary search tree , There are storage bits on each node to indicate that the color of the node is red (Red) Or black (Black). The time complexity is O(lgn), Efficient .

characteristic :

（1） Each node is either black , Or red .

**（2） The root node is black .**

**（3） Every leaf node （NIL） It's black .（ Only empty (NIL or null) The node of ）**

**（4） If a node is red , Then its child nodes must be black .（ Black nodes can be continuous , Red nodes are not continuous ）**

**（5） All paths from a node to its children contain the same number of black nodes .**

Theorem ：** A tree contains n The height of a node's red black tree is at most 2log(n+1)**.

prove ： Mathematical induction proves its converse proposition “ The height is h The red black trees in China have at least 2^(h/2 )-1 Nodes ”

Black node height bh(x) >= h/2,So prove it“ The height is h The red black trees in China have at least 2^bh(x)-1 A black node ”

# The rotation of the red black tree

### left-handed

** In the left “ Left ”, signify “ The node being rotated will become a left node ”**.

LEFT-ROTATE(T, x)

y ← right[x] // Premise ： It is assumed that x The right child of y. Let's start the formal operation

right[x] ← left[y] // take “y The left child ” Set to “x The right child ”, namely take β Set to x The right child

p[left[y]] ← x // take “x” Set to “y The father of the left child ”, namely take β My father is set as x

p[y] ← p[x] // take “x Father ” Set to “y Father ”

if p[x] = nil[T]

then root[T] ← y // situation 1： If “x Father ” It's an empty node , Will y Set as root

else if x = left[p[x]]

then left[p[x]] ← y // situation 2： If x It's the left child of its parent node , Will y Set to “x The left child of the parent node of ”

else right[p[x]] ← y // situation 3：(x It's the right child of its parent ) take y Set to “x The right child of the parent node of ”

left[y] ← x // take “x” Set to “y The left child ”

p[x] ← y // take “x Parent node ” Set to “y”

### Right hand

** On the right “ Right ”, signify “ The node being rotated will become a right node ”**.

RIGHT-ROTATE(T, y)

x ← left[y] // Premise ： It is assumed that y The left child of x. Let's start the formal operation

left[y] ← right[x] // take “x The right child ” Set to “y The left child ”, namely take β Set to y The left child

p[right[x]] ← y // take “y” Set to “x The father of the right child ”, namely take β My father is set as y

p[x] ← p[y] // take “y Father ” Set to “x Father ”

if p[y] = nil[T]

then root[T] ← x // situation 1： If “y Father ” It's an empty node , Will x Set as root

else if y = right[p[y]]

then right[p[y]] ← x // situation 2： If y It's the right child of its parent , Will x Set to “y The left child of the parent node of ”

else left[p[y]] ← x // situation 3：(y It's the left child of its parent node ) take x Set to “y The left child of the parent node of ”

right[x] ← y // take “y” Set to “x The right child ”

p[y] ← x // take “y Parent node ” Set to “x”

# Basic operation of red and black tree

### add to

**step1: The binary search tree inserts nodes , The key values are ordered .**

**step2： The inserted node means " Red ".** This doesn't violate the characteristics 5, The fewer cases that need to be dealt with .

**step3: Rotate or recolor , Adjust to red black tree .**

** Realization **

RB-INSERT(T, z)

y ← nil[T] // The new node “y”, take y Set to null node .

x ← root[T] // set up “ Red and black trees T” The root node of is “x”

while x ≠ nil[T] // Find the node to insert “z” In the binary tree T Position in “y”

do y ← x

if key[z] < key[x]

then x ← left[x]

else x ← right[x]

p[z] ← y // Set up “z Father ” by “y”

if y = nil[T]

then root[T] ← z // situation 1： if y It's an empty node , Will z Set as root

else if key[z] < key[y]

then left[y] ← z // situation 2： if “z The values contained ” < “y The values contained ”, Will z Set to “y The left child ”

else right[y] ← z // situation 3：(“z The values contained ” >= “y The values contained ”) take z Set to “y The right child ”

left[z] ← nil[T] // z The left child of is set to blank

right[z] ← nil[T] // z Set the right child to blank . thus , It has been completed and will “ node z Insert into a binary tree ” It's in .

color[z] ← RED // take z Color it as “ Red ”

RB-INSERT-FIXUP(T, z) // adopt RB-INSERT-FIXUP Color modification and rotation of red black tree nodes , Let the tree T It's still a red black tree

RB-INSERT-FIXUP(T, z)

while color[p[z]] = RED // if “ Current node (z) The parent node of is red ”, Then proceed to the following processing .

do if p[z] = left[p[p[z]]] // if “z Parent node ” yes “z The grandfather node of the left child ”, Then proceed to the following processing .

then y ← right[p[p[z]]] // take y Set to “z The uncle node of (z The grandfather node of the right child )”

if color[y] = RED // Case 1 Conditions ： Uncle is red

then color[p[z]] ← BLACK ▹ Case 1 // (01) take “ Parent node ” Set to black .

color[y] ← BLACK ▹ Case 1 // (02) take “ Uncle node ” Set to black .

color[p[p[z]]] ← RED ▹ Case 1 // (03) take “ Grandfather node ” Set to “ Red ”.

z ← p[p[z]] ▹ Case 1 // (04) take “ Grandfather node ” Set to “ Current node ”( Red nodes )

else if z = right[p[z]] // Case 2 Conditions ： Uncle is black , And the current node is the right child

then z ← p[z] ▹ Case 2 // (01) take “ Parent node ” As “ New current node ”.

LEFT-ROTATE(T, z) ▹ Case 2 // (02) With “ New current node ” Rotate left for the fulcrum .

color[p[z]] ← BLACK ▹ Case 3 // Case 3 Conditions ： Uncle is black , And the current node is the left child .(01) take “ Parent node ” Set to “ black ”.

color[p[p[z]]] ← RED ▹ Case 3 // (02) take “ Grandfather node ” Set to “ Red ”.

RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) With “ Grandfather node ” Right rotation for the fulcrum .

else (same as then clause with "right" and "left" exchanged) // if “z Parent node ” yes “z The grandfather node of the right child ”, Put the above operation into “right” and “left” Swap places , And then execute one after the other .

color[root[T]] ← BLACK

Depending on the parent of the inserted node , Can be " When node z Colored as a red node , And insert the binary tree " There are three situations to deal with .

① Description ： The inserted node is the root node .

processing method ： Paint this node black directly .

② Description ： The parent of the inserted node is black .

processing method ： Nothing needs to be done . After the node is inserted , It's still the red and black tree .

③ Description ： The parent of the inserted node is red .

processing method ： that , The situation is similar to that of the red black tree “ characteristic (5)” Conflict . In this case , The inserted node must have a non empty grandparent node ; Go further , The inserted node must also have an uncle node ( Even if the uncle node is empty , We also see it as being , An empty node itself is a black node ). After understanding this , We rely on " Uncle node ", Divide this situation into 3 In this case (Case).

**Case 1 Uncle is red **

(01) take “ Parent node ” Set to black .

(02) take “ Uncle node ” Set to black .

(03) take “ Grandfather node ” Set to “ Red ”.

(04) take “ Grandfather node ” Set to “ Current node ”( Red nodes ); namely , Then go on to “ Current node ” To operate .

**Case 2 Uncle is black , And the current node is the right child **

(01) take “ Parent node ” As “ New current node ”.

(02) With “ New current node ” Rotate left for the fulcrum .

**Case 3 Uncle is black , And the current node is the left child **

(01) take “ Parent node ” Set to “ black ”.

(02) take “ Grandfather node ” Set to “ Red ”.

(03) With “ Grandfather node ” Right rotation for the fulcrum .

Case 3 After processing , And then we put nodes "120" As the current node , It becomes Case 2 The situation of .

Three situations (Case) The core idea of dealing with problems is ：** Move the red node to the root node ; then , Set the root node to black .**

### Delete

**step1****： Two pronged search tree delete node .**

3 In this case ：

① The deleted node is a leaf node , Delete the node directly .

② The deleted node has only one child , Delete the node directly , And replace its position with the only child of the node .

③ The deleted node has two children , First, find out its subsequent nodes , And then put “ The content of its successor node ” Copy to “ The content of this node , Then consider deleting “ Its successor node ”. " The successor node of this node " Or no son , Or just one son . If there is no son , Then press " situation ① " To deal with ; If there's only one son , Then press " situation ② " To deal with .

**step2： Rotate and recolor the red black tree .**

RB-DELETE(T, z)

if left[z] = nil[T] or right[z] = nil[T]

then y ← z // if “z The left child ” or “z The right child ” It's empty , Will “z” Assign a value to “y”;

else y ← TREE-SUCCESSOR(z) // otherwise , take “z Successor node ” Assign a value to “y”.

if left[y] ≠ nil[T]

then x ← left[y] // if “y The left child ” Not empty , Will “y The left child ” Assign a value to “x”;

else x ← right[y] // otherwise ,“y The right child ” Assign a value to “x”.

p[x] ← p[y] // take “y Parent node ” Set to “x Parent node ”

if p[y] = nil[T]

then root[T] ← x // situation 1： if “y Parent node ” It's empty , Is set “x” by “ The root node ”.

else if y = left[p[y]]

then left[p[y]] ← x // situation 2： if “y It's the left child of its parent node ”, Is set “x” by “y The left child of the parent node of ”

else right[p[y]] ← x // situation 3： if “y It's the right child of its parent ”, Is set “x” by “y The right child of the parent node of ”

if y ≠ z

then key[z] ← key[y] // if “y Value ” Assign a value to “z”. Be careful ： This is just a copy z The value of y, Without a copy z The color of the ！！！

copy y's satellite data into z

if color[y] = BLACK

then RB-DELETE-FIXUP(T, x) // if “y Black node ”, Call

return y

RB-DELETE-FIXUP(T, x)

while x ≠ root[T] and color[x] = BLACK

do if x = left[p[x]]

then w ← right[p[x]] // if “x” yes “ The left child of its parent node ”, Is set “w” by “x My uncle ”( namely x For the right child of its parent node )

if color[w] = RED // Case 1: x yes “ black + black ” node ,x The sibling node of is red .( here x And x The child nodes of the brother nodes are all black nodes ).

then color[w] ← BLACK ▹ Case 1 // (01) take x The brother node of is set to “ black ”.

color[p[x]] ← RED ▹ Case 1 // (02) take x The parent of is set to “ Red ”.

LEFT-ROTATE(T, p[x]) ▹ Case 1 // (03) Yes x The parent node of .

w ← right[p[x]] ▹ Case 1 // (04) After the left-hand , To reset x Brother node of .

if color[left[w]] = BLACK and color[right[w]] = BLACK // Case 2: x yes “ black + black ” node ,x My brother node is black ,x The two children of the brother node are black .

then color[w] ← RED ▹ Case 2 // (01) take x The brother node of is set to “ Red ”.

x ← p[x] ▹ Case 2 // (02) Set up “x Parent node ” by “ new x node ”.

else if color[right[w]] = BLACK // Case 3: x yes “ black + black ” node ,x My brother node is black ;x The brother node of the left child is red , The right child is black .

then color[left[w]] ← BLACK ▹ Case 3 // (01) take x The left child of the sibling node is set to “ black ”.

color[w] ← RED ▹ Case 3 // (02) take x The brother node is set to “ Red ”.

RIGHT-ROTATE(T, w) ▹ Case 3 // (03) Yes x Right hand rotation of the brother node of .

w ← right[p[x]] ▹ Case 3 // (04) Right after the , To reset x Brother node of .

color[w] ← color[p[x]] ▹ Case 4 // Case 4: x yes “ black + black ” node ,x My brother node is black ;x The right child of the brother node is red .(01) take x Parent node color Assign a value to x Brother node of .

color[p[x]] ← BLACK ▹ Case 4 // (02) take x The parent node is set to “ black ”.

color[right[w]] ← BLACK ▹ Case 4 // (03) take x The right child of the sibling node is set to “ black ”.

LEFT-ROTATE(T, p[x]) ▹ Case 4 // (04) Yes x The parent node of .

x ← root[T] ▹ Case 4 // (05) Set up “x” by “ The root node ”.

else (same as then clause with "right" and "left" exchanged) // if “x” yes “ The right child of its parent node ”, Put the above operation into “right” and “left” Swap places , And then execute one after the other .

color[x] ← BLACK

We are going to " Delete the nodes in the red black tree " There are roughly two steps , In the first step " Look up the red black tree as a binary tree , Delete node " after , Possible violation " characteristic (2)、(4)、(5)" Three characteristics . The second step is to solve the above three problems , And then keep all the characteristics of the red black tree .

For the convenience of analysis , We assume that "x Contains an extra black "(x The original color still exists ), So it won't violate " characteristic (5)". Why? ？

adopt RB-DELETE Algorithm , We know ： Delete node y after ,x Occupied the original node y The location of . Now that it's deleted y(y It's black ), It means one less black node ; that , Add a black color to the position . such , When we assume that "x Contains an extra black ", It just makes up for " Delete y The missing black node ", It would not violate " characteristic (5)". therefore , hypothesis "x Contains an extra black "(x The original color still exists ), So it won't violate " characteristic (5)".

Now? ,x Not only does it contain its original color properties ,x There's also an extra black . namely x The color attribute of is " red + black " or " black + black ", It violates " characteristic (1)".

Now? , The problem we face , By solving " It's against the characteristics (2)、(4)、(5) Three characteristics " Transformed into " Resolve violation features (1)、(2)、(4) Three characteristics ".RB-DELETE-FIXUP What we need to do is to restore the characteristics of the red black tree through the algorithm (1)、(2)、(4).RB-DELETE-FIXUP The idea is ： take x The extra black it contains keeps moving up the tree ( Move to the root ), Until the gesture below ：

a) x Point to one " red + black " node . here , take x Set as a " black " The node can be .

b) x Point to the root . here , take x Set as a " black " The node can be .

c) Not the first two postures .

Put the posture above , Can be summed up as 3 In this case .

① Description ：x yes “ red + black ” node .

processing method ： Put... Directly x Set to black , end . At this time, all the properties of the red black tree are restored .

② Description ：x yes “ black + black ” node , And x It's a root .

processing method ： Don't do anything? , end . At this time, all the properties of the red black tree are restored .

③ Description ：x yes “ black + black ” node , And x It's not a root .

processing method ： This situation can be divided into 4 Seed situation . this 4 The seeds are shown in the table below ：

(Case 1)x yes " black + black " node ,x The sibling node of is red

(01) take x Brother node of D Set to “ black ”.

(02) take x Parent node B Set to “ Red ”.

(03) Yes x Parent node B To carry on the left-hand .

(04) After the left-hand , To reset x Brother node of .

(Case 2) x yes " black + black " node ,x My brother node is black ,x The two children of the brother node are black

(01) take x The brother node of is set to “ Red ”.

(02) Set up “x Parent node ” by “ new x node ”.

**(Case 3)x yes “ black + black ” node ,x My brother node is black ;x The brother node of the left child is red , The right child is black **

(01) take x The left child of the sibling node is set to “ black ”.

(02) take x The brother node is set to “ Red ”.

(03) Yes x Right hand rotation of the brother node of .

(04) Right after the , To reset x Brother node of .

(Case 4)x yes “ black + black ” node ,x My brother node is black ;x The right child of the brother node is red ,x The brother node of the left child of any color

(01) take x Parent node color Assign a value to x Brother node of .

(02) take x The parent node is set to “ black ”.

(03) take x The right child of the sibling node is set to “ black ”.

(04) Yes x The parent node of .

(05) Set up “x” by “ The root node ”.

## Trees - Red and black trees （R-B Tree） More articles about

- 2-3 Trees / Red and black trees （red-black tree）
2-3 tree 2-3 Tree node : null node ,null The distance from the node to the root node is the same , therefore 2-3 Numbers are balance trees 2 Cross node , There are two branches , There is an element in the node , The left tree element is smaller , The element node of the right tree is larger 3 Cross node , There are three sub trees ...

- AVL Trees , Red and black trees
AVL Trees https://baike.baidu.com/item/AVL%E6%A0%91/10986648 In computer science ,AVL Tree is the first self balanced binary search tree . stay AVL The height of two subtrees of any node in the tree ...

- Written test algorithm problem （51）： brief introduction - Red and black trees （RedBlack Tree）
Red and black trees (Red-Black Tree) Red black tree is a kind of BST, But adding a memory bit to each node indicates the color of the node (R perhaps B): From any one of them root To leaf The display of node coloring mode on the path of , The red black tree ensures that all paths are ...

- Talking about AVL Trees , Red and black trees ,B Trees ,B+ Tree principle and application （ turn ）
come from :https://blog.csdn.net/whoamiyang/article/details/51926985 background : I'm looking at < High performance Mysql>, When you see creating high-performance indexes , Book ...

- B Trees 、B- Trees 、B+ Trees 、B* Trees Red and black trees
Reprinted from :http://blog.csdn.net/quitepig/article/details/8041308 B Trees The binary search tree : 1. All non leaf nodes have at most two sons (Left and Right): ...

- Talking about AVL Trees , Red and black trees ,B Trees ,B+ Tree principle and application
background : I'm looking at < High performance Mysql>, When you see creating high-performance indexes , The book says mysql Storage engine for InnoDB The index type used is B+Tree, that , Do you have such a question , For data indexing , Why should we make ...

- C# Linked list Binary tree Balanced binary trees Red and black trees B-Tree B+Tree The index to achieve
Linked list => Binary tree => Balanced binary trees => Red and black trees =>B-Tree=>B+Tree 1. Linked list Linked list structure is composed of many nodes , Each node has two parts : Data section : Save the actual data of the node . The earth ...

- data structure （ One ） Binary tree & avl Trees & Red and black trees & B- Trees & B+ Trees & B* Trees & R Trees
Reference documents : avl Trees :http://lib.csdn.net/article/datastructure/9204 avl Trees :http://blog.csdn.net/javazejian/artic ...

- B Trees B+ Trees Red and black trees
B-Tree(B Trees ) Before the specific explanation , A little bit , Again :B- Trees , That is to say B Trees . because B The original English name of the tree is B-tree, And many people in China like to put B-tree translation B- Trees , Actually , This is a very bad literal translation , It's easy to misunderstand . ...

## Random recommendation

- ps Tutorial links
course 1:http://www.68ps.com/jc/ps_tp.asp course 2:http://www.3lian.com/edu/photoshop/

- Title Case a Sentence
Solutions Convert string to lowercase Split a string into an array of strings Loop array capitalizes every word Convert all elements of the array to a string The first method function titleCase(str) { str=str ...

- iPad Development
get view: self.categoryItem.customView Set control to start : stay POP ver The size in self.preferredContentSize = The firm trilogy 1. By setting ...

- Xshell And securecrt Between different
Now the more popular terminal simulator software is xshell and securecrt 了 , Now let's objectively analyze the two kinds of software , In order to better choose . One . Functional comparison 1.1Xshell function Support layout switching Adjustable execution sequence Provide multi label function Yes ...

- opengl Basic learning project ( 3、 ... and ) Several styles of polygon drawing
Digression The reason why smart people don't succeed , It's because of their lack of tenacity . —— Isaac · Newton (1643 year 1 month 4 Japan —1727 year 3 month 31 Japan ) The British Maybe it can be understood as When you want to go a step further , insist , Hard work and intelligence are indispensable . Keep your back straight and straight ...

- Amazon Kindle Device is hiring in Beijing Shanghai and Shenzhen!
This is Angela from recruitment team of Amazon Kindle Device Software & Applications, we are exp ...

- MongoDB 2.6.x Installation and deployment of
1. download mongodb 2.6.x Version of zip package , stay D Disk create directory MongoDB, Unzip to D:\MongoDB Catalog . Create database directory D:\MongoDB\data, Next, open the command line window , Switch to D:\M ...

- UVA - 11882 Biggest Number(dfs+bfs+ Strong pruning )
The main idea of the topic : Give a grid matrix , There are numbers in the matrix 0~9, Choose any grid as the starting point , Connect the numbers you have passed to form a number , Find the biggest number , You can only walk once per grid . Topic analysis :DFS. Pruning plan : In the current situation , Find out all that's still available ...

- Java My summer job
Java Summer homework One .< malice > Reading notes < malice > It is one of the inferential novels written by Japanese writer keigo dono . After reading it, I can't help but be shocked by Mr. Dongye's peculiar writing technique and the ugliness of human nature displayed in the book . I think this book compares with < ...

- java jackson Ignore nonexistent property fields and According to the attribute name json
@JsonAutoDetect(fieldVisibility = Visibility.ANY, getterVisibility = Visibility.NONE, isGetterVisibi ...