This is the 13th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The definition of a red-black tree

A red-black tree is a binary search tree with a storage bit added to each node to represent the color. By managing the colors on each path from root to leaf, approximate equilibrium is achieved (red-black trees ensure that one path is not twice as high as the other), which guarantees that the time complexity of dynamic set operations under the worst conditions is O(lgN)O(lgN)O(lgN).

Binary search tree

A binary search tree can be represented by a linked list, where each node is an object. In addition to some data such as key, it also includes the properties left, right, and p, which refer to the left child, right child and parent respectively. It points to NIL if it doesn’t exist.

The binary search tree satisfies that for any node X, the keyword of the left subtree cannot be greater than x. keyy and the right subtree cannot be less than X. keyy. The worst time of most search tree operations is proportional to the height of the tree.

Properties of red black trees

After introducing binary search trees, let’s introduce some properties that red-black trees satisfy:

  1. Each node is either black or red
  2. The root node must be black
  3. Every leaf node (leaf nodes are NIL nodes) is black. (IF a node has no child or parent, its corresponding pointer points to NIL.)
  4. The two children of every red node are black
  5. All paths from any node to each of its leaves contain the same number of black nodes

So property four tells us that at least half of the nodes on the simple path from the root to the leaf are black.

A red-black tree is not a perfectly balanced binary lookup tree, but the path from any node to each leaf node contains the same number of black nodes. So we call this balance of the red-black tree a perfect balance of black.

The way a red-black tree maintains its balance

A red-black tree has three operations for balance:

Left-handed: with a node as the pivot (rotation node), the right child node becomes the parent node of the rotation node. The left child of the right child becomes the right child of the rotation node, leaving the left child unchanged.

Right-rotation: with a node as the fulcrum (rotation node), the left child node becomes the parent node of the rotation node. The right child of the left child becomes the left child of the rotation node, and the right child remains unchanged.

Color change: node color changes from red to black or from black to red

Red-black trees are self-balanced by rotating and changing colors.

As can be seen from the figure below, if node 11 is taken as the rotation node, its right child 18 becomes the parent, and then the left child 14 of node 18 becomes the right child of node 11.

Search for a red-black tree

A red-black tree is a binary search tree, so it looks for nodes in the same way as a normal binary search tree, but because the red-black tree is better balanced, the worst time complexity is O(2lgN)O(2lgN)O(2lgN).

Insertion of a red-black tree

The insertion time of the red-black tree is O(LGN)O(LGN)O(LGN), and the insertion of the red-black tree is similar to the insertion of the binary search tree, except that the red-black tree determines the corresponding node color and colors it. Here is the pseudocode above:

RB-INSERT(T,z)  T = red-black tree, z = node to be inserted
// Set y to nil
y = T.nil
// Set x as the root node
x = T.root
whilex ! = T.nil// x is not empty
    y = x 
    if z.key< x.key  // Insert a node smaller than the tree
        x = x.left
    else 
        x = x.right
z.p = y  // Set the parent of the insert node to y
if y == T.nil  // The tree is empty
    T.root = z
else if z.key < y.key
    y.left = z
else
    y.right = z
Set the left and right children of the inserted node to nil
z.left = T.nil
z.right = T.nil
z.color = RED
RB-INSERT-FIXUP(T,z)  // Adjust the coloring
Copy the code
while z.p.color == RED
    if z.p == z.p.p.left  // Determine if the parent is left of the grandparent
        y = z.p.p.right  // Set y to the right of the grandparent
        if y.color = RED  // Determine the color of y
            z.p.color = BLACK  // Set the parent of z to black (case 1)
            y.color = BLACK  // Set z's uncle to black (case 1)
            z.p.p.color = RED  // Set the grandparent of z to red (case 1)
            z = z.p.p  // Set node Z to its grandparent (case 1)
        else if z == z.p.right  // If z is the right child of the parent
            z = z.p  // Set z as the parent of z (case 2)
            // Turn the node to the leftLETF - ROTATE (T, z) (2) Z.P.C olor = BLACK// Set z parent to black (case 3)
        z.p.p.color = RED  // Set the grandparent of z to red (case 3)
        // Turn the node rightRIGHT - the ROTATE (T, Z.P.P) (3)else  // Similar to the above
        y = z.p.p.left   
        if y.color = RED
            z.p.color = BLACK
            y.color = BLACK
            z.p.p.color = RED
            z = z.p.p
        else if z == z.p.left
            z = z.p
            // Turn the node to the left
            RIGHT-ROTATE(T,z)
        z.p.color = BLACK
        z.p.p.color = RED
        // Turn the node right
        LEFT-ROTATE(T,z.p.p)
T.root.color = BLACK
Copy the code

I won’t post the details of the left-handed and right-handed code here, but if you want to know yourself, you can go to the Internet to learn about it.

As shown in the figure below: The details can be understood by referring to the code. First, the color of the parent node and uncle node of the node is judged to determine whether the color of the inserted node meets the requirements. If not, the color is adjusted.

Deletion of a red-black tree

Although the deletion of the red-black tree is a bit more complicated than the insertion, I will not post the code to save space. The time required to delete a red-black tree is also O(lgN)O(lgN)O(lgN).

  • If there is no child node, the deleted node may be red or black. 1.1 If the node is red, delete the node without affecting the number of black nodes. 1.2 If the balance is black, delete the balance.
  • If there is only one child node, the deleted node must be black and the child node must be red. Otherwise, the red-black tree nature cannot be satisfied. In this case, the child nodes of the deleted node are connected to the parent node, and the color of the child nodes is black to ensure the number of black nodes.
  • When there are two child nodes, as in the binary search tree, the successor node is used as the replacement deletion node, and the case is changed to 1 or 2.

I won’t go into the details, and I’ll write an article on red-black tree deletion.

conclusion

Data Structure-The heap

This is the second part of the data structure I recorded. Due to my limited technical level, I may not write so accurately. If there is any problem, I hope you can help me to point it out.