The underlying data structure of red-black tree:
Binary search tree (special binary tree) Binary search tree (perfect equilibrium, ideal state)
Linked list -> binary tree -> binary lookup tree -> special binary lookup tree (self-balanced binary lookup tree)
The time complexity is the depth of our red-black tree
Binary search method:
Logn => 2^x =n (height of tree) =>x=log2^n =>logn(min+ Max) /2:56 (1+100) /2 =50 and so on
1. Every node is red or black
2. There can be no red nodes connected
3. The root node is black root
4. The two children of each red node are all black, and the leaf nodes are all black. If the output degree is 0, it can be approximately balanced
Rotation:
First find the point we need to rotate, rotate 90 degrees counterclockwise, and then attach the right subtree of the rotated child node to the rotated left subtree
Color-changing rules:
Rules for rotation and color transformation: All insertion points default to red
Discoloration: Discoloration occurs when the red-black tree rule is broken, i.e., the parent of the current node is red, and another child of the parent node is red (uncle node).
1. Change the parent node to black
2. The uncle node becomes black
3. The grandfather node becomes red
4. Set pointer to grandfather node to current operation. Analysis of point transformation rules
Left-handed: the current parent node is red, the uncle node is black, and the current node is a right subtree. Left-handed: the parent node is left-handed
Right-handed: the current parent node is red, the uncle node is black, and the current node is a left subtree, and the right-handed grandfather node. Make the parent node black and the grandfather node red
The parent of the current node is red, and the other child of the parent node is also red (uncle node).
