Red black tree definition

  • The root node is black

  • Nodes are either red or black

  • The path from any node to its descendants contains the same number of black nodes

  • Red nodes, whose children cannot be red

  • All leaf nodes are black. This leaf node refers to a leaf node that is NIL (or NULL) and is usually omitted.

Red black tree coloring, rotation rules

All newly inserted nodes are red except for the first node, which is the initial root, which is black.

  • 1 If the parent node is black, insert the node directly

  • 2 If the parent node of the new node is red

    • 2.1 ifInsert the nodetheUncle nodeIf it is red, proceeddyeing, the parent node and tertiary node becomeblack, the grandfather node becomesredContradictions shift upward.

    • 2.2 ifInsert the nodetheUncle nodeFor the black

      • 2.2.1 If the bias of the inserted node and its parent node is the same as that of the parent node and its grandfather node. In other words, if the inserted node is the right (left) subtree of its parent node, and the parent node is the right (left) subtree of its inserted node’s grandfather, then the bias is consistent. At this point, the first step is to turn the parent node to black and the grandfather node to red. In the second step, the grandfather node is used as the benchmark to turn left.

      • 2.2.2 If the bias of the inserted node and its parent node is inconsistent with that of the parent node and its grandfather node. At this point, the first step is node rotation, with the parent node as the benchmark for dextral rotation, so that the three nodes are biased to the same, and then the last biased to the same operation.

  • Supplement:

    1. The essence of rotation, in fact, is to align the nodes, all you have to do is think about when is it left, when is it right
    2. The rules for coloring and rotation serve the definition
    3. One problem is that staining can cause conflict to move up. What happens when you move up to the root node

Examples of red-black tree insertion

For example, insert int[] a = {10, 18, 16, 12, 13, 17, 15, 14, 9, 8,7}.

  1. Insert node 10,The initial node, set as the root node, the color ofblackColor.

  1. Insert node 18 in colorredColor, because the parent node isblackColor, directly inserted.

  1. Insert node 16 in colorredColor, because the parent node isredColor, and uncle node isblackColor (by definitionAll leaf nodes are black), so it is true2.2.2Conditions,First rotate, then dye, then rotate.

  1. Insert node 12 in colorredColor, because the parent node isredColor, and uncle node is alsoredColor, in line with the2.1Condition, parent node and tertiary node changeblackColor, grandfather node changesredColor, because the grandfather node is the root node, so again becomesblackColor (definition: the root node is black).

  1. Insert node 13 in colorredColor, because the parent node isredColor, and uncle node isblackWith thatInserting a Node 16The difference is that its bias is consistent with2.2.1Conditions described are the same, so dye directly in rotation.

  1. Insert node 17 in colorredColor, because the parent node isblackColor, directly inserted.

  1. Insert node 15 in colorredColor, because the parent node isredColor, and uncle node is alsoredColor, in line with the2.1Condition, parent node and tertiary node changeblackColor, grandfather node changesredColor, at this point, the red-black tree equilibrium condition is satisfied, no rotation is required.

  1. Insert node 14 in colorredColor, because the parent node isredColor, and uncle node isblackColor, and the parent node is biasedDon't agree. Conform to the2.2.2Conditions, first rotate, before dyeing, before rotating.

  1. Insert node 9 in colorredColor, because the parent node isblackColor, directly inserted.

  1. Insert node 8 in colorredColor, because the parent node isredColor, and uncle node isblackColor, and the parent node is biasedconsistent. Conform to the2.2.1Condition, first dye, in rotation

  1. Insert node 7 in colorredColor, because the parent node isredColor, and uncle node is alsoredColor, in line with the2.1Condition, parent node and tertiary node changeblackColor, grandfather node changesredColor. Because node 9 and node 12 are in a continuous state, they do not meet the definition2.2.1Conditions,12 nodeschangeblack.Node 16changeredBy definitionThe path from any node to its descendants contains the same number of black nodes, so the root node is turned black to not meet the definition, so according to2.2.1, perform rotation.

supplement

  • Red-black tree inserts sample site