Location>code7788 >text

red and black trees

Popularity：115 ℃/2024-09-08 17:01:55

summarize

Red-Black Tree (R-BTree) is a self-balancing binary lookup tree, where each node in a red-black tree has an extra storage bit indicating the color of the node, and the color can only be red (Red) or black (Black).

The characteristics of red and black trees are as follows:

  • Each node is either black, or red
  • The root node is black
  • Each leaf node is black, where the leaf node refers to the bottom null node, i.e., the node with value null in the graph, which is generally omitted from the discussion, and the root node with value null is not regarded as a leaf node in the red-black tree
  • If a node is red, its children must be black
  • All paths from any node to a leaf node contain the same number of black nodes under them

With the above properties as restrictions, the degeneration of a binary search tree into a single linked table can be avoided. With properties 4 and 5, it is guaranteed that the longest path from any node to each of its leaf nodes will not be more than twice the shortest path, because when a path is the shortest, it must be composed of black nodes. When a path is the longest, it must consist of both red and black nodes (Property 4). Property 5, in turn, restricts all paths from any node to each of its leaf nodes to contain the same number of black nodes. Therefore, the length of the longest path is equal to 2 times the length of the shortest path.


Spinning of the Red and Black Tree

Red-black tree left rotation: a node as the pivot point of the left rotation, means that the right child node (b) of a node is set as the parent node of a node, then a node becomes the left node of b node, and b node's original left child node d is redistributed according to the rules of the balanced binary tree.

The same is true for the right-handedness of the red-black tree


Addition of red and black trees

The addition of red and black trees is divided into three steps:

  1. Consider a red-black tree as a binary lookup tree and insert a new node with the rules of a binary lookup tree, at which point the new node must be at the end of the tree, i.e., it is a leaf node (disregarding black nodes with the value null)
  2. Color the inserted node red (if it is painted black, then the path where this node is located has one more black node than the other paths, which is more troublesome to adjust; if it is painted red, the number of black nodes on all the paths will remain unchanged at this time, and only two consecutive red nodes may appear, which can be adjusted by color change and rotation)
  3. By left-rotating, right-rotating, or coloring operations to make it a red-black tree again

Depending on the parent of the node being inserted, the specific insertion can be handled in three cases

The first one: if the inserted node is the root node, paint this node black directly

The second one: if the parent node of the inserted node is black, it does not destroy the nature of the binary tree and does not need to be adjusted

The third one: if the parent node of the inserted node is red, there must exist a non-empty grandfather node (black) of the inserted node, i.e., there must also exist an uncle node of the inserted node, and even if the uncle node (another child node of the grandfather node of the current node) is null, we regard it as existent, and the null node itself is a black node. Then according to the color of the uncle node, it is further divided into three cases to deal with:

  • If the uncle node is red, set the parent and uncle nodes to black and the grandfather node to red. Note that after the grandfather node is set to red, it may form consecutive red nodes with its parent node, in which case you need to set the current node as the grandfather node and recursively adjust upwards
  • If the uncle node is black and the current node is the right child of the parent node, set the parent node as the current node, use the current node as the pivot point for left-hand rotation, and then adjust it according to the other circumstances
  • If the uncle node is black and the current node is the left child of the parent node, set the parent node to black, set the grandfather node to red, and use the grandfather node as the pivot point for right rotation

Red-black tree removal

Red-black tree deletion is a two-step process:

  1. Consider a red-black tree as a binary lookup tree and delete nodes according to the deletion rules of a binary lookup tree
    1. If the deleted node has no children, then the node is deleted directly
    2. If the deleted node has only one child, then the node is deleted directly and replaced with the unique child of that node
    3. If the deleted node has two children, then first find out the replacement node of that node, then overwrite the data of that node with the data of the replacement node, and after that delete the replacement node
  2. Because a red-black tree may violate the properties of a red-black tree after deleting nodes, it needs to be corrected by rotating and recoloring it to become a red-black tree again
    1. If the children of the current node are "red+black" nodes, then set the current node to black.
    2. If the children of the current node are "black+black" nodes and the current node is the root node, then do nothing
    3. If the children of the current node are "black+black" nodes, and the current node is not the root node, then it can be handled as follows
      • If the current node's sibling node is red, set the current node's sibling node to black, set the parent node to red, perform a left rotation on the parent node, and reset the current node's sibling node
      • If the child of the current node is a "black+black" node, and the sibling node of the current node is black, and both children of the sibling node are black, then set the sibling node of the current node to red, and set the parent node of the current node to be the new node.
      • If the children of the current node are "black+black" nodes, and the brother node of the current node is black, and the left child of the brother node is red and the right child of the brother node is black, then set the left child of the current node to black, set the brother node to red, right-rotate the brother node, and reset the brother node of the current node.
      • If the child of the current node is a "black+black" node, and the sibling node of the current node is black, and the right child of the sibling node is red and the left child of the sibling node is any color, assign the color of the parent of the current node to the sibling node, set the parent node to black, set the right child of the sibling node to black, and perform a left-rotation of the parent node, setting the current node as the root node. node is left-rotated, setting the current node as the root node
<Previous Next>