This is the 12th day of my participation in the August Text Challenge.More challenges in August

The strict balancing strategy of binary balanced tree achieves stable O(logN) search time complexity at the cost of establishing search structure (insert and delete operation). But is it worth it? Can we find a compromise strategy that does not sacrifice too much of the cost of building a search structure, but still ensure stable and efficient search efficiency? The answer is: red-black trees.

Red-black tree is a binary search tree which contains red and black nodes and can be self-balanced. The height is logN. Its properties are as follows:

  • Each node is either red or black
  • The root node is black
  • Each leaf node (NIL) is black
  • If a node is red, both of its children are black
  • The path from any node to each leaf node contains the same number of black nodes

It is these five properties of red-black tree that make a red-black tree with N nodes always maintain logN height, thus explaining the reason of the conclusion that “the worst time complexity of search, insert and delete of red-black tree is O(logN)”.

The efficiency of summary

  • Search: Time complexity O(logN) at best, but less than AVL at worst, but much better than BST

  • Insert/delete: the probability of changing the balance of the tree is much smaller than AVL (RBT is not highly balanced)

    Therefore, the possibility of rotation operation is small, and once rotation is required, the insertion of a node only needs two rotations at most, and the deletion only needs three rotations at most (less than the number of rotations required by AVL deletion operation). Although the time complexity of the color-changing operation is in order (logN), in practice, this operation requires very little cost due to its simplicity

1 a left-handed

  • Rotate the two nodes counterclockwise so that one node is replaced by its right child, which becomes the left child of the right child
  • Left-handed rotation of x means “turn x into a left node.”
  • Left-handed condition: two consecutive red nodes, and the uncle node is black, and the red node below is in the right subtree

1.1 case 1

If the current node is a right subtree and the parent node is a left subtree. Example :(900 is the newly inserted node)

To left-rotate according to the parent [899] (who becomes the child according to the left-rotate) :

The left subtree of [900] is hung to the right subtree of [899], and [899] becomes the child node. When [900] becomes the parent node, it does not change color.

1.2 case 2

If the current node is a right subtree and the parent node is a right subtree. Look like :([100] is the current node)

According to the grandfather node leftward [56] (according to who leftward, who becomes child node) :

[56] becomes a child node, [89] becomes a parent node, and the left subtree of [89] hangs to the right subtree of [56]. At the same time: the parent node becomes black ([89] becomes black) and the grandfather node becomes red ([56] becomes red).

2 a right-handed

  • Rotate the two nodes clockwise so that one node is replaced by its left child, which becomes the right child of the left child
  • Left-handed rotation of x means “turn x into a left node.”
  • Dextral condition: two consecutive red nodes, and the uncle node is black, and the red node below is in the left subtree

2.1 case 1

If the current node is a left subtree and the parent node is a right subtree. Look like :([8000] is the current node)

According to the parent node dextrorotatory [9000] (according to who dextrorotatory, who becomes child node) :

[9000] becomes a child node, and [8000] becomes a parent node. The right subtree of [8000] hangs to the left subtree of [9000], and it does not change color at this time.

2.2 case 2

If the current node is a left subtree and the parent node is also a left subtree. Example :([899] is the current node)

According to the grandfather node dextral [1000] (according to who dextral, who becomes child node) :

[1000] becomes a child node, [900] becomes a parent node, and the right child tree of [900] hangs to the left child tree of [1000] at the same time: the parent node becomes black ([900] becomes black), and the grandfather node becomes red ([1000] becomes red).

3 color

If the parent and uncle nodes of the current node are both red, perform the following color change operation:

Father –> black uncle –> black ye –> Red

Four scenes that cannot be rotated by changing color

3.1 Scenario 1: Rotation of left and right Nodes

In this case, both the parent node and the inserted node are left nodes, as shown below (rotate the original figure 1). In this case, we insert node 65. The rule is as follows: grandfather node [right rotation], with [color change].

According to the rules, the steps are as follows:

3.2 Scenario 2: Rotating Left and right Nodes

In this case, the parent node is the left node, the inserted node is the right node, and in rotating the original figure 1, we insert node 67. The rules are as follows: the parent node is left-handed, then the grandfather node is right-handed, paired with the color change. According to the rules, the steps are as follows:

3.3 Scenario 3: Rotation of right and left Nodes

In this case, the parent is the right node and the inserted node is the left node, as shown below (rotate the original figure 2) in this case, we want to insert node 68. The rules are as follows: the parent node is right-handed, then the grandfather node is left-handed, paired with the color change.

According to the rules, the steps are as follows:

3.4 Scenario 4: Right and Right Nodes are rotated

In this case, the parent node and the inserted node are both right nodes, and in rotating the original figure 2, we insert node 70. The rule is as follows: grandfather node [left rotation], with [color change]. According to the rules, the steps are as follows: