Binary search tree

Since a red-black tree is essentially a binary search tree, let’s look at binary search trees before we look at red-black trees.

A sorted Binary Tree is an empty Tree or a sorted Binary Tree with the following properties:

  • If the left subtree of any node is not empty, the value of all nodes in the left subtree is less than the value of its root node.
  • If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than the value of its root node.
  • The left and right subtrees of any node are binary search trees respectively.
  • No duplicate nodes have the same key value.
Since the height of a randomly constructed binary search tree with n nodes is LGN, it follows that the execution time of a general operation is O (LGN). (For proof of the height of a binary search tree with n nodes, see section 12.4 of binary search tree, Chapter 12, Introduction to Algorithms).

However, if the binary tree degenerates into a linear chain with N nodes, the worst case running time of these operations is O (n). We will see a binary search tree-red black tree, which has some properties that make the tree relatively balanced, such that the time complexity of the final search, insert, and delete is O (LGN) in the worst case.

Red and black tree

We’ve already said that a red-black tree is essentially a binary search tree, but it adds coloring and correlation properties to the binary search tree to make the red-black tree relatively balanced, thus ensuring that the search, insert, delete time of a red-black tree is order log n at worst.

But how does it guarantee that the height of a red-black tree with n nodes is always h = logn? This leads to five properties of red-black trees:

1) Every node is either red or black.


2) The root is black.


3) Every leaf (leaf refers to NIL pointer or NULL at the end of the tree) is black.


4) If a node is red, both of its sons are black.


5) For any node, each path to the NIL pointer to the end of the leaf node tree 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 conclusion that “the time complexity of search, insert and delete of red-black tree is O(log n) at worst”.

As shown below, it is a red-black tree:



These “leaves” or “NULL “nodes, which contain no data and serve only as an indication of where the tree ends, and their parents are often omitted from drawings.

Tree rotation knowledge

When we modify a red-black tree during insertion or deletion, we may violate the properties of a red-black tree.

In order to keep the property of red-black tree, we can recolor the nodes and rotate the tree, that is, modify the color and pointer structure of some nodes in the tree, so as to maintain the property or balance of red-black tree after inserting or deleting nodes.

Tree rotation is divided into left rotation and right rotation. The following is a graphic explanation and introduction:

1. Left-handed



As shown above:

So when we do left-turn on some pivot, we assume that its right child y is not NIL[T], and pivot can be any left child that is not NIL[T].

Left-turn takes place on the “pivot” of the chain from pivot to Y, making Y the new root of the child’s tree, and B, the left child of Y, the right child of pivot.

The reference code for left-spin is as follows (with x in place of pivot above) : 

Left-rotate (T, x) 1 y ← right[x] ▹ Set y. 2 Right [x] ← LEFT [y] ▹ Turn y's left subtree into x'S Right subtree. 3 p[left[y]] ← x 4 p[y] ← p[x] ▹ Link xParent to y. 5 if p[x] = nil[T] 6 then root[T] ← y 7 else if x = left[p[x]] 8 then left[p[x]] 9 else right[p[x]] ← Y 10 left[y] ← x ▹ Put x on y'P [x] ← yCopy the code

2. Right

Dextral rotation is similar to left-handed rotation, but I won’t go into details here.



For tree rotation, only the search property of the original tree can remain unchanged, but the red-black property of the original tree cannot be maintained. After data insertion and deletion of the red-black tree, rotation and color repainting can be used to restore the red-black property of the tree.

Red-black tree insertion

To really understand the insert and delete of red-black trees, you need to understand the insert and delete of binary lookup trees. We will understand the insertion and deletion of the binary search tree.

Insertion of binary lookup tree

If you want to insert a node into the binary search tree, you should first find the position where the node is inserted and then insert it. Assuming that the inserted node is Z, the pseudo-code of the insert is as follows: 

Tree-insert (T, z) 1 Y ← NIL 2 X ← root[T] 3while4 x indicates a NILdoY please x 5if key[z] < key[x]
 6            then7 x please left [x]elseX ← right[x] 8 P [z] ← y 9if y = NIL
10     thenRoot [T] ← z ⊹ Tree T was empty 11else if key[z] < key[y]
12             thenLeft [y] please zelseRight [y] please zCopy the code
As you can see, the above 3-7 lines of code is to look for in the bintree z to be inserted into the position, if the nodes of z is less than the current traversal to insert, and then to the current node in the left subtree continue to find, if z is greater than the current node, then to the current node in the right subtree of continue to search, 9-13 lines of code to insert place, If z is still smaller than the new current node traversed at the moment, z is the left child of the current node, otherwise it is the right child of the current node.

Red-black tree insertion and insertion repair

Now that we know about binary search tree inserts, let’s look specifically at red-black tree inserts. The insertion of red-black tree is equivalent to an insertion repair operation in order to restore balance on the basis of binary search tree insertion.

Assuming that the node to be inserted is Z, the insertion pseudocode of red-black tree is as follows: 

RB-INSERT(T, z)  
 1  y ← nil[T]  
 2  x ← root[T]  
 3  while4 x indicates a nil [T]doY please x 5if key[z] < key[x]  
 6            then7 x please left [x]elseX ← right[x] 8 P [z] ← y 9if y = nil[T]  
10     thenRoot [T] please zelse if key[z] < key[y]  
12             thenLeft [y] please zelseRight [y] ← Z 14 left[z] ← nil[T] 15 Right [z] ← nil[T] 16 color[z] ← RED 17 RB- insert-fixup (T, z)Copy the code
INSERT(T, z); INSERT(T, z); INSERT(T, z); INSERT(T, z); INSERT(T, z); Finally, to ensure that the red and black properties remain after the insertion operation, an auxiliary program rb-insert-fixup is called to recolor the node and rotate it.

In other words

  • If I’m inserting the root, because the tree is empty, I’m just going to violate property 2, so I’m just going to color it black.
  • If I insert a node whose parent is black, and since that doesn’t violate properties 2 and 4, the red-black tree is not broken, I don’t do anything.
However, when encountering the following three situations:

  • Insert fix case 1: If the parent of the current node is red and the other child of the grandfather node is red
  • Insert repair case 2: the parent of the current node is red, the uncle node is black, and the current node is the right child of its parent
  • Insert repair case 3: The parent of the current node is red, the uncle node is black, and the current node is the left child of its parent
How to adjust? The answer is to follow the rb-insert-fixup (T, z) call on the last line of the red-black tree insertion code, as shown below: 

RB- insert-fixup (T,z) 1while color[p[z]] = RED  
 2     do if p[z] = left[p[p[z]]]  
 3           thenY please right [p [p] [z]] 4if color[y] = RED  
 5                   thenColor [P [z]] ← BLACK ▹ Case 1 6 color[Y] ← BLACK ▹ Case 1 7 color[P [P [z]]] ← RED ▹ Case 1 8 Z ← P [P [z]] ▹ Case 1 9else if z = right[p[z]]  
10                           thenZ ← p[z] ▹ Case 2 11 left-rotate (T, Z) ▹ Case 2 12 color[P [z]] ← BLACK ▹ Case 3 13 color[P [p[z]]] ← RED ▹ Case 3 14 right-rotate (T, P [p[z]]) ▹ Case 3 15else (same as then clause  
                         with "right" and "left"Only very thrifty) 16 color[root[T]] ← BLACKCopy the code
Now, let’s deal with the above three insertion and repair cases respectively.

Insert repair condition 1:

The parent of the current node is red and the other child of the grandparent is red.

As shown in the following code: 

 1 while color[p[z]] = RED  
 2     do if p[z] = left[p[p[z]]]  
 3           thenY please right [p [p] [z]] 4if color[y] = RED  Copy the code
The parent must have a parent, otherwise it’s not a red-black tree before insertion.

At the same time, it’s divided into whether the parent is the left child or the right child of the grandfather, and for symmetry, we only have to solve for one direction.

Here, we only consider the case where the parent is the left child of the grandfather.

You can also say whether the current node is the left child or the right child of its parent, but it’s the same thing. We put this in the same category.

Countermeasure: Black the parent node and uncle node of the current node, red the grandfather node, point the current node to the grandfather node, and start the algorithm from the new current node. As shown in the following code: 

 5                   thenColor [P [z]] ← BLACK ▹ Case 1 6 color[Y] ← BLACK ▹ Case 1 7 color[P [P [z]]] ← RED ▹ Case 1 8 Z ← P [P [z]] ▹ Case 1Copy the code

For case 1, before the change [the current node is 4 nodes] :



After the change:



Insert repair condition 2:

The parent of the current node is red, the uncle is black, and the current node is the right child of its parent

Countermeasures: The parent of the current node as the new current node, with the new current node as the fulcrum left rotation. As shown in the following code: 

 9                   else if z = right[p[z]]
10                           thenZ ← p[z] ▹ Case 2 11 Left-rotate (T, z) ▹ Case 2Copy the code
As shown in the picture below,
Before the change[Current node is 7] :



After the change:



Insert repair condition 3:

The parent of the current node is red, the uncle is black, and the current node is the left child of its parent

Solution:The parent becomes black, the grandparent becomes red, and the grandparent is right-handed. The operation code is: 

12 color[P [z]] ← BLACK ▹ Case 3 13 color[P [P [z]]] ← RED ▹ Case 3 14 right-rotate (T, P [p[z]]) ▹ Case 3Copy the code
Finally, by painting the root black, the whole red-black tree is restored to balance.

As shown below [the current node is 2 nodes]



After the change:



Delete red black tree

Ok, so let’s finally look at deleting red black trees.

“We delete node method and conventional method of deleting nodes in the binary search tree is the same, if not deleted nodes have double non-empty children, directly delete this node, the only child nodes with it for its position, if its nodes are empty son, then replace it with an empty nodes position, if it’s a Gemini full is not empty, We copy the contents of its immediate successor to its location, and then delete its successor in the same way. Its successor cannot be binary and non-null, so this is passed only once at most.”

Deletion of binary lookup tree

Before continuing, I would like to add several cases of binary tree node deletion. The nodes to be deleted can be divided into three types according to the number of sons:

  1. No sons, leaves. Set the parent’s child pointer to NULL and delete the child.
  2. Only one son. If the parent pointer points to the only child of the child, delete the child.
  3. He has two sons. This is the most troublesome case, because after you delete the nodes, you have to make sure that the structure of the search binary tree is satisfied. And it’s actually pretty easy, because we can pick the largest element in the left child or the smallest element in the right child and put it where we want to delete the node, and we can keep the structure unchanged. Of course, you have to remember to adjust the subtree, because there is deletion again. It’s customary to pick the largest of the left sons, and it’s the same thing to pick the smallest of the right sons, it doesn’t make any difference, it just goes from left to right. Here we also select the largest element of the left son and place it at the node to be deleted. The largest element of the left son is actually easy to find, as long as the left son continues to search the right subtree, until it finds a node that does not have a right subtree. That’s the biggest.
The binary search tree deletion code is as follows: 

TREE-DELETE(T, z)
 1  if left[z] = NIL or right[z] = NIL
 2      thenY please z 3elseY please TREE - SUCCESSOR (z) 4ifLeft [y] indicates a NIL 5thenX please left [y] 6else[y] 7 x please rightifX indicates a NIL 8thenPlease p p [x] [y] 9if p[y] = NIL
10      thenRoot [T] please x 11else if y = left[p[y]]
12              thenPlease left [p [y]] 13 xelseRight [p] [y] please 14 xifY indicates z 15thenKey [Z] ← Key [y] 16 Copy y's satellite data into z 17 return yCopy the code

Red black tree deletion and deletion repair

OK, back to the red-black tree, the red-black tree node deletion algorithm implementation is:

Rb-delete (T, z) The total operation of simply deleting a node 

 1 if left[z] = nil[T] or right[z] = nil[T]  
 2    thenY please z 3elseY please TREE - SUCCESSOR (z) 4ifLeft [y] indicates a nil [T] 5thenX please left [y] 6elseX ← right[y] 7 P [x] ← P [y] 8if p[y] = nil[T]  
 9    thenRoot [T] please 10 xelse if y = left[p[y]]  
11            thenLeft [p] [y] please x 12elseRight [p] [y] please 13 xifY indicates z 14thenKey [Z] ← Key [y] 15 Copy y's satellite data into z 16 if color[y] = BLACK 17 then RB-DELETE-FIXUP(T, x) 18 return yCopy the code
“After deleting the nodes, the properties of the original red-black tree may be changed. If the nodes are red, the properties of the original red-black tree will remain. There is no need to modify the nodes. If the deleted node is not the unique node of the tree, the number of black nodes from the branch of the deleted node to each leaf node will change, and property 5 will be destroyed. Property 4 is broken if the only non-null child of the deleted node is red, and the parent of the deleted node is also red. If the deleted node is the root node and its only non-null child is red, the new root node will become red after deletion, violating property 2.

Rb-delete-fixup (T, x) restores work with red-black properties 

 1 whileX ≠ root[T] and color[x] = BLACK 2do if x = left[p[x]]  
 3           thenW please right [p] [x] 4if color[w] = RED  
 5                   thenColor [W] ← BLACK ▹ Case 1 6 color[P [x]] ← RED ▹ Case 1 7 left-rotate (T, P [x]) ▹ Case 1 8 W ← right[P [x]] ▹ Case 1 9if color[left[w]] = BLACK and color[right[w]] = BLACK  
10                   thenColor [W] RED ▹ Case 2 11 x ← p[x] ▹ Case 2 12else if color[right[w]] = BLACK  
13                           thenColor [left[w]] ← BLACK ▹ Case 3 14 color[W] ← RED ▹ Case 3 15 right-rotate (T, W) ▹ Case 3 16 W ← right[P [x]] ▹ Case 3 17 color[W] ← color[P [x]] ▹ Case 4 18 color[P [x]] ← BLACK ▹ Case 4 19 Color [right[w]] ← BLACK ▹ Case 4 20 left-rotate (T, P [x]) ▹ Case 4 21 x ← root[T] ▹ Case 4 22else (same as then clause with "right" and "left"[X] ← BLACK (for a money rattle)Copy the code
“The above fix looks a bit complicated, so let’s use an analysis trick: We start with the node that replaced it and think it has an extra layer of black. Here an extra heavy black is what meaning, we are not the red and black tree node plus another except the red color, there is only a hypothesis, we think our current pointing to it, with an additional black so empty, can think its black inherited from its parent node to be deleted after it, it can accommodate two colors now, if it is red, So it’s now red plus black, and if it was black, it’s now black plus black. With this extra black, the original red-black tree property 5 remains the same. Now it’s just a matter of restoring the other properties, moving as close to the root as possible and exhausting the possibilities.” – saturnman.

Recovery is easier if:

  • A) The current node is red + black
Solution, directly dye the current node to black, at the end of the red-black tree properties are restored.

  • B) The current node is black + black and the root node, solution: do nothing, end
But what about the following? :

  • 1: The current node is black + black and the sibling node is red (the children of the parent node and sibling node are black)
  • Case 2: The current node is black plus black and the sibling is black and the two children of the sibling are all black
  • 3: The current node is black + black, the sibling node is black, the sibling child is red, the right child is black
  • 4: The current node is black-black, its sibling is black, but the right child of the sibling is red, and the left child of the sibling is any color
At this point, we need to call rb-delete-fixup (T, x) to restore and preserve the red-black nature of the work.

Below, let’s deal with these four deletion and repair cases respectively.

Delete Fix case 1:

The current node is black + black and the sibling is red (the children of the parent and sibling are black).

Solution:Dye the parent node red, the sibling node black, and then re-enter the algorithm (we only discuss the case when the current node is the left child of its parent). After this transformation, the original red-black tree property 5 remains unchanged, but the problem is transformed into a situation where the sibling is black. That is, the following code operation: 

// Call line 1-8 of rb-delete-fixup (T, x)whileX ≠ root[T] and color[x] = BLACK 2do if x = left[p[x]]
 3           thenW please right [p] [x] 4if color[w] = RED
 5                   thenColor [W] ← BLACK ▹ Case 1 6 color[P [x]] ← RED ▹ Case 1 7 left-rotate (T, P [x]) ▹ Case 1 8 W ← right[P [x]] ▹ Case 1Copy the code
Before the change:



After the change:



Delete Fix case 2:

The current node is black plus black and the sibling is black and the two children of the sibling are all black.

Solution:Add a heavy black from the current node and its siblings to the parent node, treat the parent node as the new current node, and re-enter the algorithm. Call line 9-10 of rb-insert-fixup (T, z) as follows: 

// Call rb-delete-fixup (T, x) on line 9-11if color[left[w]] = BLACK and color[right[w]] = BLACK
10                   thenColor [W] ← RED ▹ Case 2 11 x p[x] ▹ Case 2Copy the code
Before the change:



After the change:



Deleted Fix Case 3:

The current node is black + black, the sibling is black, the left sibling is red, the right sibling is black.

Solution:Dye the sibling node red and the left sibling node black, and then solve dextral rotation at the sibling node as the fulcrum, and then re-enter the algorithm. This converts the current case to case 4, while property 5 remains, which calls lines 12-16 of rb-insert-fixup (T, z) as follows: 

// Call line 12-16 of rb-delete-fixup (T, x)else if color[right[w]] = BLACK
13                           thenColor [left[W]] ← BLACK ▹ Case 3 14 color[W] ← RED ▹ Case 3 15 right-rotate (T, W) ▹ Case 3 16 W ← RIGHT [P [x]] ▹ Case 3Copy the code
Before the change:



After the change:



Deleted Fix Case 4:

The current node is black-black, its sibling is black, but the sibling’s right child is red, and the sibling’s left child is any color.

Solution:Dye the sibling node to the color of the parent node of the current node, dye the parent node of the current node to black, dye the right child of the sibling node to black, and then rotate left with the parent node of the current node as the fulcrum. At this point, the algorithm ends and all properties of the red-black tree are adjusted correctly, that is, call line 17-21 of rb-insert-fixup (T, z), as shown below: 

/ / call the RB - DELETE - FIXUP (T, X) Line 17-21 code 17 color[W] ← color[P [x]] ▹ Case 4 18 color[P [x]] ← BLACK ▹ Case 4 19 color[right[W]] ← BLACK ▹ Case 4 20 Left-rotate (T, P [x]) ▹ Case 4 21 x ← root[T] ▹ Case 4Copy the code
Before the change:



After the change:



In this paper, the reference

This paper refers to the introduction to algorithms, STL source code analysis, computer programming art and other information.

The last

Welcome everyone to pay attention to my public kind hao [Programmer Tracking wind], sorted out 2019 many companies Java interview questions more than 100 pages of PDF documents, articles will be updated in it, sorted materials will also be placed in it.