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 ··················

Reply after attention 「1024」, Access to massive learning resources

版权声明

本文为[One go, two three li]所创，转载请带上原文链接，感谢

https://cdmana.com/2021/04/20210422062253155X.html