Welcome to my blog post

The Red Black Tree is a self-balancing Binary Search Tree. Formerly also called a Symmetric Binary B-tree.

Preliminary knowledge

The knowledge framework structure of the tree is shown in the figure below:

Balanced binary search tree

Balanced Binary Search Tree (BBST) The classic and common balanced binary search trees are AVL tree and red black tree.

Binary search tree

Binary Search Tree (BST) is a kind of Binary Tree. Also called binary search tree, binary sort tree.

It is characterized by the fact that the value of any node is greater than the value of all nodes in its left subtree, and the value of any node is less than the value of all nodes in its right subtree.

balance

Balance: when the number of nodes is fixed, the closer the height of the left and right subtrees are, the more balanced (the lower the height is) the binary tree will be. And the ideal balance is a complete/full binary tree, the smallest binary tree.

The average time complexity of a binary search tree can be considered as the height O(h) of the tree. Like the one on the left, the left and right subtrees are close in height, belonging to a balanced binary search tree, O(h) = O(logn); The one on the right, at its maximum height, is reduced to a linked list, O(h)=O(n).

Improved binary search tree

When binary trees degenerate into linked lists, the performance is very low, so we need to find a way to restore the binary search tree balance (reduce the height of the tree) after node insertion and deletion operations. However, if it is not necessary to increase the time complexity in order to achieve the optimal balance, a reasonable solution is to achieve a moderate balance with as few adjustments as possible.

Hence, the concept of AVL tree is derived.

AVL tree

AVL tree is one of the first self-balanced binary search trees. It is named after two inventors: G.M.Adelson-Velsky and E.M.Landis.

Balance factor

Balance Factor: the height difference between the left and right subtrees of a node.

Each leaf node has an equilibrium factor of 0. If you look at this binary search tree, the red numbers indicate the equilibrium factor for each node.

For example:

The height of the left subtree of 8 is 2 and the height of the right subtree is 1, so its balance factor is 1. The height of the left subtree of 5 is 0 and the height of the right subtree is 3, so its balance factor is -3. The height of the left subtree of 4 is 2 and the height of the right subtree is 4, so its equilibrium factor is -2.

Let’s look at the AVL tree and the balance factor corresponding to each of its nodes:

It can be seen that the AVL tree has the following characteristics:

  • The balance factor of each node can only be -1, 0 or 1 (if the absolute value exceeds 1, it is considered unbalanced)
  • The height difference between the left and right subtrees of each node is no more than 1
  • Search, insert, delete time order logn

B tree

Balanced Tree is a Balanced multi-path search Tree, which is mainly used to implement file systems and databases. Here is a simple b-tree of order 3:

The characteristics of

  • A node can store more than two elements and can have more than two children
  • It has some properties of binary search trees
  • Equilibrium, all subtrees of each node are the same height
  • shorter

Properties of M-order B-trees (M ≥ 2)

Order M B tree means that a node has at most m children. Suppose a node stores x, then if the node is:

  • Root node: 1 ≤ x ≤ m – 1
  • Non-root node: chrysene m / 2 erres-1 ≤ x ≤ m-1

If there are children, and the number of children is y = x + 1, then if the node is:

  • Root node: 2 ≤ y ≤ m
  • Non-root node: chrysene m / 2 gp ≤ y ≤ m

To take the whole (Ceiling), refers to the smallest integer larger than oneself, expressed by the mathematical symbol chrysene. ├ ─ lower (Floor) — take the largest integer smaller than yourself, expressed in the math symbol — sigma.

For example, m = 3, the number of children 2 ≤ y ≤ 3, the B tree can be called (2,3) tree, 2-3 tree;

If m = 4, and the number of children is 2 ≤ y ≤ 4, this B-tree could be called a (2,4) tree, or a two-three-four tree;

For example, if m = 5 and the number of children is 3 ≤ y ≤ 4, this B tree can be called (3,5) tree or 3-4-5 tree.

And so on.

B tree VS binary search tree

This is a binary search tree, by merging some parent nodes, that happens to correspond to the B tree above. We can draw the conclusion that:

  • B trees and binary search trees are logically equivalent
  • A supernode can be obtained by merging multiple generations of nodes, and the supernode merged in n generations can have at most (2^n) children (at least (2^n) order B tree).

Red black tree definition and properties

Red-black tree is a binary search tree with self-balancing red-black nodes.

To be balanced, a red-black tree must have the following properties:

  1. Each node is either red or black
  2. The root must be black
  3. Leaf nodes (outer nodes, null nodes) are black
  4. Red nodes are not contiguous (i.e., red nodes have black children and black fathers).
  5. For each node, from that point tonil(At the end of the tree, in JavanullAny path containing the same number ofblacknode

The equivalent transformation of red black tree and B tree

Based on the properties above, we can draw a red-black tree that looks like this. Next, the equivalent transformation of red-black tree is performed, that is, all red nodes are raised one level and placed on the same line as their parent, which is similar to a fourth-order B-tree. The transformation effect is shown in the figure below.

It can be concluded that:

  • Red-black trees are equivalent to fourth-order B trees (2-3-4 trees)
  • Black node and red child node are fused together to form a B-tree node
  • The number of black nodes in a red-black tree is equal to the total number of nodes in a fourth-order B-tree

Basic operation of red black tree

When we insert or delete a balanced binary search tree, it is very likely that the tree will become unbalanced (at worst, all ancestor nodes will be out of balance, but neither parent nor non-ancestor nodes can be out of balance), and the tree needs to be rotated to achieve equilibrium. Red-black trees achieve self-balance by turning left, right and color.

The rotation operation is local. When there are fewer nodes on one side of the subtree, borrow some nodes from the other side; When one side of the subtree has too many nodes, it rents some nodes to the other side.

In order to explain this section more clearly, let’s declare a few concepts:

  • N-node: indicates the current node
  • P-parent: indicates the parent node
  • -Serena: S-sibling
  • U-uncle: uncle (brother of P)
  • G-grand: grandparent (parent of P)

left-handed

Left-handed refers to a node as the fulcrum (rotation node), the right child becomes the parent of the rotation node, the left child of the right child becomes the right child of the rotation node, and the left child remains unchanged.

Regardless of the node color, you can see that left-rotation only affects the structure of the rotation node and its right subtree, moving the node of the right subtree to the left subtree.

Right hand

Dextral means that a node is used as the fulcrum (rotation node), the left child becomes the parent 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.

Regardless of node color, you can see that dextral rotation only affects the structure of the rotation node and its left subtree, moving the nodes of the left subtree to the right.

discoloration

Discoloration means that the color of the node changes from red to black or from black to red.

Transformation rule

Combining left rotation, right rotation and discoloration, a set of transformation rules is obtained:

Color change: If the parent and uncle of the current node are red, then:

  • Change the parent and uncle to black
  • Change the grandparent to red
  • Define a pointer to a grandparent

Left-handed: The current node is a right subtree and the parent is red. The uncle is black and spins left-handed to its parent

Dextral: the current node is the left subtree, and the parent is red, and the uncle is black, then:

  • Change the parent to black
  • Change the grandparent to red
  • Dextral rotation of the grandparent

Red-black tree search

Since the red-black tree is a balanced binary search tree, and the search does not disturb the tree’s balance, the search algorithm is also consistent with the balanced binary search tree:

Specific steps:

  1. Starting from the root, set the root to the current node;
  2. If the current node is empty, return nil.
  3. If the current node is not empty, compare the current node key with the search key.
  4. If the current node key is equal to the search key, then that key is the search target and the current node is returned.
  5. If the key of the current node is greater than the search key, set the left child of the current node as the current node, and repeat Step 2.
  6. If the key of the current node is smaller than the search key, set the right child of the current node as the current node, and repeat Step 2.

Red-black tree insertion

Red-black tree insertion is divided into the following two steps:

Locate the insertion position

Specific steps:

  1. Retrieves from the root;
  2. If the root is empty, then the insertion is set to the root and the end.
  3. If the root is not null, set the root to the current;
  4. If the current node is nil, return the parent of the current node, end.
  5. If the current node key is equal to the search key, then the node where the key is located is the insert node, update the value of the node, and end.
  6. If the key of the current node is greater than the search key, set the left child of the current node as the current node, and repeat Step 4.
  7. If the key of the current node is smaller than the search key, set the right child of the current node as the current node, and repeat Step 4.

Self-balancing after insertion

It is recommended that new nodes be added in red by default, so that red-black tree properties can be satisfied as quickly as possible. But if you’re adding a root node, make it black.

Summarize all the possible scenarios for red-black tree insertion.

Scenario 1: Red-black trees are empty

Property 2 of red-black trees: The root must be black.

Fix: Make the insert node black and use it as the root.

Scenario 2: The key inserted into the node already exists

The same element cannot be inserted into the binary search tree. Since the key of the node already exists and the red-black tree is balanced, there is no need to repeat the insertion.

Processing:

  • Set the insertion node to the color of the node to be replaced
  • Update the value of the current node to the value of the inserted node

Scenario 3: The parent of the inserted node is black

The node inserted is red by default, and its parent is black, which does not disturb the balance.

Handle: Insert directly.

Scenario 4: The parent of the inserted node is red

If the parent of the inserted node is red, then the parent cannot be the root, so the inserted node always has a grandparent. This is important because subsequent rotation operations require grandparent.

Scenario 4.1: An uncle exists and is red

According to red-black tree property 4, red nodes cannot be continuous. In this case, the number of red and black layers should be inserted into the subtree: black-red-red. The easiest way to do this is to change it to red-black-red.

Processing:

  • Change the parent and uncle to black
  • Change the grandparent to red
  • Sets the grandparent to the current insertion node

Scenario 4.2: The uncle does not exist or is black, and the parent inserted into the node is the left child of the grandfather

In this scenario, there are more black nodes in the sub-tree where the uncle node is located than in the sub-tree where the parent node is located, which does not meet the property of red-black tree 5.

Scenario 4.2.1: The insert node is a left subtree

Processing:

  • Change the parent to black
  • Change the grandparent to red
  • Turn the grandparent right

Scenario 4.2.2: The insert node is a left subtree

This scenario can obviously be translated to 4.2.1.

Processing:

  • Rotate the parent left
  • Setting the parent node as the insertion node, scenario 4.2.1 is obtained
  • Perform operations described in scenario 4.2.1

Scenario 4.3: The uncle does not exist or is black, and the parent inserted into the node is the right child of the grandfather

Equivalent to the direction reversal of scenario 4.2, look directly at the diagram.

Scenario 4.3.1: The insert node is a left subtree

Processing:

  • Change the parent to black
  • Change the grandparent to red
  • Rotate the grandparent left

Scenario 4.3.2: The insert node is a right subtree

Processing:

  • Rotate the parent right
  • Setting the parent node as the insertion node, scenario 4.3.1 is obtained
  • Perform operations in scenario 4.3.1

For example, if you insert an element into a red-black tree, the transformation of the whole tree is as follows:

Red black tree deleted

The red-black tree deletion operation is also divided into two steps:

Locate the delete location

Locating the delete location can reuse the operation of red-black tree search.

If no target node exists, ignore this operation. If the target node is found, delete it and perform self-balancing.

Self-balancing is implemented after deletion

There are three possible scenarios for binary search tree deletion:

  • Scenario 1: If the node to be deleted has no children, delete it directly.
  • Scenario 2: If the deleted node has only one child node, replace the deleted node with the child node.
  • Scenario 3: If the deleted node has two children, replace the deleted node with a successor node (the smallest node larger than the deleted node).

Specific applications can be understood with the help of this picture:

We can find that the deletion scenarios of the other two binary trees can be transformed into scenario 1.

In scenario 2, the deleted node is replaced with its unique child node. After the child node is replaced with the deleted node, it can be considered that the deleted node is a child node. If the child node has two children, it is equivalent to the transformation to Scenario 3, which is always transformed from top to bottom and can always be transformed to scenario 1.

In scenario 3, the successor node is used to delete the node. If the successor node has a right child node, it is equivalent to converting to Scenario 2; otherwise, it is converted to Scenario 1.

To sum up, the deleted node can be regarded as the deleted replacement node, and the replacement node always ends at the end of the tree.

Here’s a summary of all the possible scenarios for red-black tree deletion.

In order to understand the aspect, let’s first agree on the name of the node:

  • R – Replace the node
  • P – The parent of the replacement node
  • S – The sibling of the replacement node
  • The left child of the sl-sibling
  • The right child of the sr-sibling
  • Gray – The node color may be red or black

Note: R is the replacement node to be replaced at the location of the deleted node. Before deletion, it still participates in the sub-balance of the tree at its original location. After the balance, it will be replaced at the location of the deleted node, and the deletion is completed.

Scenario 1: The replacement node is red

When we change the replacement node to the deleted node, because the replacement node is red, the deletion will not affect the balance of the red-black tree, as long as the color of the replacement node is changed to the color of the deleted node to rebalance.

Processing: Replace node color to delete node color.

Scenario 2: The replacement node is black

When the replacement is black, we have to do self-balancing, and we can do different rotations to rebalance the tree by distinguishing whether the replacement is the left child or the right child of its parent.

Scenario 2.1: The replacement node is the left subtree

Scenario 2.1.1: The sibling of the replacement node is red

If the sibling node is a red node, then according to the red-black tree property 4, the parent node and child node of the sibling node must be black. The deletion scenario 2.1.2.3 is obtained according to the following processing.

Processing:

  • Turn the sibling into black
  • Change the parent to red
  • Left-spin the parent node to obtain scenario 2.1.2.3
  • Perform operations described in Scenario 2.1.2.3

Scenario 2.1.2: The sibling of the replacement node is black

When the sibling is black, the specific color of the parent and child cannot be determined, and the multi-seed scenario has to be considered.

Scenario 2.1.2.1: The right child of the sibling of the replacement node is red and the left child is any color

The left subtree has one less black node, but the right subtree is red, so we borrow a red node from the right subtree to complement the black node and rotate it. As shown in the figure:

Processing:

  • Change the color of the sibling to that of the parent
  • Change the parent to black
  • Change the right child of the sibling to black
  • I rotate the parent left

Scenario 2.1.2.2: The right child of the sibling of the replacement node is black and the left child is red

The sibling subtree has red nodes, and it can “borrow” a red node from the sibling subtree, which translates back to scenario 2.1.2.1. As shown in the figure:

Processing:

  • Turn the sibling red
  • Change the left child of the sibling to black
  • Right-handed rotation is performed on sibling nodes to obtain scenario 2.1.2.1
  • Perform the operations described in scenario 2.1.2.1

Scenario 2.1.2.3: The children of the siblings of the replacement node are all black

The sibling subtree runs out of red nodes to borrow from, and then borrows from its parent. If the parent is black, make the sibling red and make the parent the new replacement in order to balance the parent in the subtree.

Processing:

  • If the parent is black
    • Turn the sibling red
    • Use the parent as the new replacement node
    • Delete the node again
  • If the parent is red
    • The parent of the replacement node and the sibling of the replacement node swap colors
    • After swapping the values of the delete node and the replacement node, the replacement node is deleted

Scenario 2.2: The replacement node is the right subtree

This is actually a mirror operation for scenario 2.1.

Scenario 2.2.1: The sibling of the replacement node is red

Processing:

  • Turn the sibling into black
  • Change the parent to red
  • Right-handed rotation is performed on the parent node to obtain scene 2.2.2.3
  • Perform operations in scenario 2.2.2.3

Scenario 2.2.2: The sibling of the replacement node is black

Scenario 2.2.2.1: The left child of the sibling of the replacement node is red, and the right child is any color

To deal with

Processing:

  • Change the color of the sibling to that of the parent
  • Change the parent to black
  • Change the left child of the sibling to black
  • We rotate the parent right

Scenario 2.2.2.2: The left child of the sibling of the replacement node is black and the right child is red

Processing:

  • Turn the sibling red
  • Set the right child of the sibling to black
  • Left-rotation is performed on sibling nodes to obtain scenario 2.2.2.1
  • Perform operations in scenario 2.2.2.1

Scenario 2.2.2.3: The children of the siblings of the replacement node are all black

Processing:

  • If the parent is black
    • Turn the sibling red
    • Use the parent as the new replacement node
    • Delete the node again
  • If the parent is red
    • The parent of the replacement node and the sibling of the replacement node swap colors
    • After swapping the values of the delete node and the replacement node, the replacement node is deleted