编程知识 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 ··················

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

版权声明
本文为[One go, two three li]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/04/20210422062253155X.html

Scroll to Top