Characteristics of red-black trees:
(1) Each node is either black or red. (2) The root node must be black. (3) Each leaf node (NIL) is black. [Note: leaf nodes are NIL or NULL leaf nodes!] (4) If a node is red, its children must be black. (5) A simple path from any node to each of its leaves contains the same number of black nodes.
Application of red black tree
Red black tree is widely used, mainly to store ordered data, its time complexity is O(LGN), very high efficiency.
For example, TreeSet and TreeMap in Java collections, set and map in C++ STL, and Linux virtual memory management are all implemented through red-black trees.
Red-black trees are relatively balanced
Properties 4 and 5 together determine that the total number of nodes in the longest path cannot exceed twice that of the shortest path. Because the number of black nodes has to be the same, the red nodes can’t be connected, so the shortest path is all black, and the longest path is alternating red and black. For example, four black nodes, the shortest: black-black-black-black (4), the longest: black-red-black-red-black-black (7). Because the path length/height difference is limited, it is called a red-black tree with certain balance and will not appear extreme tilt.
Red-black tree add operation
We first set the original color of the added nodes to red, so as not to break the property that each node has the same number of black nodes to all its leaf nodes
If the parent node of the added node is black, the task is done smoothly
If you add it as the root node, just black it out
However, if the parent node of the added node is red, it violates the fact that the children of the red node must be black
Insert summary and example
According to the method of adding nodes to binary tree, insert nodes first.
After the insertion, the newly inserted node is used as the current balancing node N to perform balancing operations. Now, looking back at these cases of equilibrium insertion, it’s not really that complicated:
N is the root: black finish;
Father black: what matter need not tube;
Father red uncle red: father/uncle painted black, grandfather painted red, and then grandfather as a new balance node recursive processing (we balance below, let him communicate with the old man);
Parent red and tertiary black: if the parent node and the newly inserted node are on the same side, twist it (with left and right rotation, with right and left rotation, incidentally coloring); If not on the same side, move to the same side first.
Example: insert 10,20,15,30,5,8; For simplicity, no null black nodes are drawn.
