Data structure analysis [red black tree]

Preface

​ R-B Tree, The full name is Red-Black Tree, also called “ Red and black trees ”, It's a balanced binary 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).

characteristic

1. Each node is either red or black
2. There can't be red dots connected together
3. The root nodes are all black root
4. The two child nodes of each red node are black .
5. Leaf nodes are all black ： The degree of 0 If the properties are satisfied, we can approximate the equilibrium , Red and black numbers are not necessary , Can be for other .

Practical example

​ Java stay JDK1.8 Red black trees were introduced in , The actual reason is because when HashMap in hash When the function insertion calculation reaches the repeated position and the linked list is too long , It will cause the query to be too slow .

When the list is too long

To solve this problem , And the introduction of red and black trees , Because the query of binary tree is similar to Binary query Fast .

Introduce the red black tree

Balance rule

All inserted points are red by default

1. Color change

   Of the current node Father is red , And the other child node of its grandfather node is also red （ Uncle node ）.

   1. Set the parent node to black
   2. Set the uncle node to black
   3. Set the grandfather node to red
   4. Define the pointer to the grandfather node and set it as the current operation

2. left-handed

   At present The parent node is red , Uncle node is black When , And The current node is the right subtree . Take the parent node as the left rotation point

3. Right hand

   At present The parent node is red , Uncle node is black When , And The current node is the left subtree .

   1. Turn the parent node black
   2. Turn grandpa's node into red
   3. Rotate at the same time

Example

1. Color change
   

2. left-handed
   

3. Right hand
   

Java The use of

jdk1.8 Houdang HashMap The linked list at a certain position of exceeds 8 Time , Will be converted from a linked list to a red black tree , Speed up query .