## 编程知识 cdmana.com

### How to understand red black tree thoroughly?

author ： Haima

Source ：https://www.cnblogs.com/linzworld/p/13720477.html

Binary tree

A tree satisfying the following two conditions is a binary tree ：

• It's an ordered tree （ If the subtrees of each node in a tree are regarded as ordered from left to right ( That is, it cannot be interchanged ）, The tree is called an ordered tree (Ordered Tree)）.

• The degree of each node in the tree cannot exceed 2, It can only be 0、1 perhaps 2.

Simply understand , Binary tree （Binary tree） There are at most two branches per node （ That is, there is no branching degree greater than 2 The node of ） The tree structure of the . Usually branches are called “ The left subtree ” or “ Right subtree ”.

Binary search tree

Before you know the red black tree , You can't help looking at what a binary search tree is first .

Definition on Wikipedia ： Binary search tree （ English ：Binary Search Tree）, Also known as a binary search tree 、 Ordered binary tree （ordered binary tree） Or sort binary trees （sorted binary tree）, An empty tree or a binary tree with the following properties .

If the left subtree of any node is not empty , Then the values of all nodes on the left subtree are less than the values of its root nodes ; If the right subtree of any node is not empty , Then the value of all nodes on the right subtree is greater than or equal to the value of its root node ; The left side of any node 、 Right subtrees are also binary search trees .

Picture understanding ：

The figure above shows that the search value is 29 The node of , There are the following steps ：

• Look at the root node 41.

• because 41>29, So check 41 The left child 20.

• because 20<29, So check 20 The right child 29, It happens to be the node you want to view .

degeneration

There is a very serious problem with binary search trees , If the data is inserted from large to small , Or from small to large , It will cause the binary lookup tree to degenerate into a single linked list , Be commonly called “ lame person “.

Left lame ： for example , Insert data in the order of {5,4,3,2,1}（ From big to small ）, As shown in the figure below ：

Right lame ： for example , Insert data in the order of {1,2,3,4,5}（ From small to large ）, As shown in the figure below ：

To solve this problem , There are some solutions , Namely balance , Can make the tree tend to balance , This kind of self balancing tree is called balance tree .

Balance tree

Balance tree （Balance Tree,BT） refer to , The height difference of any node's subtree is less than or equal to 1.

The common ones that fit the balance tree are AVL Trees （ Binary balanced search tree ）,B Trees （ Multi balanced search tree ,2-3 Trees ,2-3-4 One of the trees ）, A red-black tree, etc .

AVL Trees

AVL Trees （ By the inventor Adelson-Velsky and Landis The acronym of ）, It means that the height difference between two subtrees of any node does not exceed 1 Balanced tree . It is also called self balanced binary search tree .

AVL The tree can solve the right limp problem in the binary search tree , for example , Insert data in the order of {1,2,3,4,5}（ From small to large ）, As shown in the figure below ：

AVL The tree will adjust the structure that does not conform to the height difference , So that the binary tree tends to balance .

2-3 Trees

2-3 Trees , It refers to every node with children （ Internal node ,internal node） Either there are two child nodes and one data element , Or a self balancing tree with three child nodes and two data elements , All of its leaf nodes have the same height .

Simply speak ,2-3 The non leaf nodes of a tree all have two or three bifurcations , therefore , Referred to as 2 fork -3 Fork trees are easier to understand .

Another way of saying it , A node with two children and one data element is also called 2 node , A node with three children and two data elements is also called 3 node , therefore , The whole tree is called 2-3 Trees .

All the leaf spots are on the same layer of the tree , As high as ：

• nature 1： Satisfy the property of binary search tree .

• nature 2： Nodes can hold one or two elements .

• nature 3： Each node has two or three child nodes .

establish 2-3 The rules of trees

The insertion operation is as follows ：

towards 2- Insert element in node ：

To one that contains only one 3- Insert elements in the tree of the node ：

2-3-4 Trees

The meaning is as follows ：

• 2 node ： Contains two child nodes and one data element .

• 3 node ： It contains three child nodes and one data element .

• 4 node ： Contains four child nodes and a data element .

2-3-4 Trees , Each of its non leaf nodes , Or 2 node , Or 3 node , Or 4 node , And it can balance itself , So called 2-3-4 Trees .

The following rules ：

• The rules 1： When adding a new node , No nodes will be added to the empty location , It's added to the last leaf node .

• The rules 2： Four nodes can be divided into three 2- A tree of nodes , And after decomposition, the root node of the new tree needs to be merged with the parent node upward .

The insert

The original 2-3-4 Trees , Here's the picture ：

For the above 2-3-4 Trees , Insert a node 17, Because of the rules 1, node 17 Will not join nodes [16,18,20] The subtree of , It's merging with the node .

Because of the rules 2, node [16,17,18,20] It's a 4 node , The node is disassembled into a new tree , take 18 Split as the root node of the subtree .

At this point, the tree temporarily lost its balance , We need to merge the root nodes of the split subtree upward .

The same can be , Because of the rules 2, node [6,10,14,18] It's a 4 node , The node is disassembled into a new tree , take 14 Split as the root node of the subtree , It's done 2-3-4 The construction of trees .

This paper summarizes the process of inserting nodes under the network , Just to comply with two rules , that ,2-3 Trees ,2-3-4 All the trees have , Is there also 2-3-4-5 Trees ,2-3-4-5--...-n The existence of trees ？

In fact, there are , People call this kind of tree a name ：B Trees .

B Trees

B Trees , It represents a kind of tree , It allows a node to have more than two children , meanwhile , It's also self balancing , The height of leaf nodes is the same .

therefore , In order to better distinguish one B What kind of trees do trees belong to , We give it a new attribute ： degree （Degree）： How many arrows a node can have pointing to other nodes .

It has a degree of 3 Of B Trees , Indicates that a node has at most three child nodes , That is to say 2-3 The definition of a tree . It has a degree of 4 Of B Trees , Indicates that a node has at most four child nodes , That is to say 2-3-4 The definition of a tree .

The graph is 4 Of B An example of a tree ：

Red and black trees

R-B Tree, The full name is Red-Black Tree, Also known as “ Red and black trees ”, It's a special binary search tree .

Each node of the red black tree has a storage bit representing the color of the node , It can be red （Red） Or black （Black）.

How to understand the red black tree

A classic red black tree , As shown in the figure below （ Leaves are omitted, nodes are black NIL node ）：

As shown in the second picture , Compare the red black tree with the one mentioned above 2-3-4 Tree comparison , Whether found , The red black tree is one 2-3-4 Trees ：

• Each node is either black , Or red .

• The root node is black .

• Every leaf node （NIL） It's black . Be careful ： Here is the leaf node , It means empty （NIL or NULL） Leaf node of ！

• If a node is red , Then its child nodes must be black . Because every node of the red black tree is made up of 2-3-4 Transformed from trees , So the red node can't appear two times in a row , Otherwise it will appear 4 Node situation , Leading to a violation of the rules 2.

And every black node of the red black tree is 3 The middle value in the node , Or is it 2 One of the values in the node .

• All paths from a node to its children contain the same number of black nodes .

reason ： These black nodes in the red black tree 2-3-4 The tree is represented by 1 One of the nodes 2-3-4 Trees , and 2-3-4 The tree is the same subtree, the depth is the same , The balance of , So all paths from a node to its descendants contain the same number of black nodes .

As shown in the figure below , Blue means black nodes ：

Note the following ：

• characteristic （3） Leaf node in , It's just empty （NIL or null） The node of .

• characteristic （5）, Make sure that no path is twice as long as the others . thus , The red black tree is a relatively balanced binary tree .

• Although the red black tree is essentially a binary search tree , But it adds coloring and related properties on the basis of binary search tree to make the red black tree relatively balanced , So as to ensure the search of red and black trees 、 Insert 、 The time complexity of deletion is the worst O(log n).

As shown in the example above , We just need to think of the red black tree as 2-3-4 Trees to deal with , And the corresponding color is changed or left-handed and right-handed operation is carried out , To achieve the goal of balancing the red and black trees .

How to keep the structure of the red black tree

When we insert a new node , How to ensure that the structure of the red black tree can still meet the above five characteristics ？

The rotation of the tree is divided into left rotation and right rotation , With the help of the figure, we will introduce the two operations of left rotation and right rotation .

① left-handed

The original state ：

Process chart ：

End chart ：

As shown in the figure above , When at a target node E On , When doing a left-handed operation , Let's suppose its right child S No NIL.

Turn left to S To E The chain between them is “ Trunnion ” Conduct , It makes S Become the new root of the subtree , and S The left-hand child becomes E The right child .

② Right hand

The original state diagram ：

Process chart ：

End chart ：

It's like left-handed , When at a target node S On , When doing a right-handed operation , Let's suppose its right child S No NIL.

Turn left to S To E The chain between them is “ Trunnion ” Conduct , It makes S Become the new root of the subtree , and S The left-hand child becomes E The right child .

application

Mangrove is widely used , It is mainly used to store orderly data , Its time complexity is O(logn), It's very efficient .

for example ,Java In the collection TreeSet and TreeMap,C++ STL Medium set、map, as well as Linux Virtual memory management , It's all realized through the red and black tree .

·················· END ··················