First, “Algorithm – Simple” N fork tree introduction

Two, “Algorithm – simple” red black tree rotation

Three, “Algorithm – Simple” red black tree insertion

4. Delete the red black tree of algorithm – Simple and Simple

One, foreword

As mentioned in rotation of red-black Trees, RBT deletion is slightly more complicated than insertion, so how complicated? And how to delete and adjust? This will be the unveiling!

In order to describe the whole process more clearly and simply, this paper will be divided into:

  1. Find the node to delete;
  2. Find a node that can replace the deleted node;
  3. After deletion does not meet the red-black tree condition adjustment;

Find the node to delete

Given a node key or value, according to the characteristics of red-black trees:

  • The value of all left subtrees must be less than the value of the root node;
  • All nodes in the right subtree must be greater than the root node;

So, we can quickly find the key or value of the node we want to delete by using dichotomy.

public class RBTree { / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Delete a specified node * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / public void remove(int value) { if (root == null) { return; } / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * dichotomy, To find the first need to delete the node * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / p = root TreeNode; while (p ! = null) { if (p.value == value) { break; } else if (p.value > value) { p = p.left; } else { p = p.right; If (p == null) {return; } // Find nodes that can be replaced...... // Adjust the red black tree...... }}Copy the code

Search for nodes that can be replaced

As shown below, we want to delete the node with value 5:

If we directly delete node 5, then select node 2 8 for the new root node or node (instead of the root node 5, not the root of the RBT), no matter choose which node as the new root node, can not satisfy the red-black tree 5 points, from the roots of RBT to any leaf node, its path at the same number of black nodes. So, we don’t have a good solution? There must be a way, and there are two ways, of course, but it’s really just one way, just a different strategy! First, we find that the number less than 5 is the right node of node 2, and the number greater than 5 is the left node of node 8. Therefore, we can elect node 3 or node 6 to be the new node. Let’s see what happens to the red-black tree when we select each new node.

We find that whether the new root node elected by the “precursor election law” or the “successor election law” is used to replace the old node, all the five requirements of the red-black tree are met, and no adjustment is required (the following article will explain which cases need not be adjusted and which cases need to be adjusted).

So how is the precursor and successor realized, and what are the requirements?

  1. The node to be deleted only has a child node:

A. If the left child exists, locate the left child node first, and then locate the right child node continuously until the next right child node is NULL. A. Similarly, if the right son exists, locate the right son node first and then locate the left son node continuously until the next left son node is NULL. C. For a or B, only assign the value of the rightmost or leftmost node to the deleted node, and then point the deleted node to the rightmost or leftmost child node; D. For the rightmost or leftmost nodes, there may also be sons, so continue with the first point and eventually execute to e, the node with no sons \color{red}{finally execute to e, the node with no sons} finally execute to e, the node with no sons}. E. If there is no son on the far right or left, point 2 is implemented; 2. If neither son exists, go to the next section.

  • Recursively find the replacement node (successor) :

Find a precursor or successor node, and replace the value of the deleted node (if you have two sons, either the precursor or the sequential successor can be used)

Public class RBTree {public void remove(int value) {// Binary search for the node to be deleted...... P = findPreOrNextNode(p); // Adjust the red black tree...... } / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Find a successor or precursor node, Finally converted to delete (contains one or zero) child nodes * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / private TreeNode findPreOrNextNode(TreeNode p) { if (p.left ! = null || p.right ! TreeNode g = p; TreeNode g = p; / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1. Successor: node * or * that is only the second largest than the node to be deleted. Only times smaller than to delete node * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / if (p.r d.light! = null) {// find the successor node p = p.light; while (p.left ! = null) { p = p.left; }} else {// find the precursor node p = p.lift; while (p.right ! = null) { p = p.right; }} / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * exchange [node is to be deleted] and the value of the subsequent/precursor 】 【 To delete the node subsequent/precursor 】 【 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / g.v alue = p.v alue. p = findPreOrNextNode(p); } else {/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * to remove nodes without son left, right, Remove yourself is * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /} return p; }}Copy the code

4. Adjust the red black tree

If both sons do not exist, consider the color of the node to be deleted. Consider the following: The node to be deleted is the left node. \color{red}{Consider the following: The node to be deleted is the left node; } Consider the following conditions: The node to be deleted is the left node. The same is true for the right node, but the condition is different) :

  1. If the color is red, delete it directly without subsequent adjustment.
  2. If it is black, we need to consider the color of the sibling node and the child of the sibling node:

A. color{red}{a.}a. If the sibling node is red, then the fifth point of the red-black tree should be met, and the sibling node must have two black sons, then change the left son of the sibling node to red, the sibling node to black, and the parent node to left, the adjustment is complete; B. color{red}{b.}b. if the sibling node is black (if there is a son, it must be red, black does not satisfy the red black tree point 5) : i. color{red}{I.} I. The sibling node has a right son: change the color of the parent node to the sibling node, change the color of the parent node and the sibling’s right son node to red, and rotate the parent node to the left. Ii. Color {red}{ii.}ii. The sibling node has a left child, and the sibling node is right-rotated, as in 2.b.i. Ii. Color {red}{ii.}ii. The sibling node has two sons, and ignores the sibling’s left son node, the situation is the same as 2.b.i. Iv. \color{red}{iv.}iv. the sibling node has no son, because the deleted node is black. For dynamic balance, directly change the color of the sibling node to red, but it may not satisfy the fourth point of the red-black tree (the parent node may be red), therefore, change the node to be the parent node and continue to perform the second point.

Assume the name of each node:

  • X is the node to be deleted.
  • P is the parent node;
  • B is the sibling node;
  • BL is the left node of sibling node.
  • BR is the right node of the sibling node.

The following is an intuitive analysis of the five situations mentioned in point 2:

  • 2. A: X = black, B = red, BL = black, BR = black

  • B.i: X = black, B = black, BR = red
  • B. II: X = black, B = black, BL = red
  • B. II: X = black, B = black, BL = red, BR = red

  • B. IV: X = black, B = black

  • Check or adjust after deleting node:
Public class RBTree {public void remove(int value) {// Binary search for the node to be deleted...... // Find nodes that can be replaced...... // Adjust the red black tree and remove the X node fixedRemove(p); if (p == p.parent.left) { p.parent.left = null; } else { p.parent.right = null; }} / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1, cur has no son: * 1.1, cur is a red node, it is directly deleted; * 1.2. Cur is a black node, and its sibling node needs to be considered; * 2, cur has a son: * 2.1, exchange the value of cur and its son node, change to delete the son node; * 2.2 repeat Step 1; 3, A cur is impossible to have two sons: * 3.1, according to remove, a cur is either a successor, a progenitor or no son; * 3.2, so only 1 and 2 above exist; * 3.3, and step 2 eventually translates to case 1.1 or 1.2 that need to be considered in Step 1; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / private void fixedRemove(TreeNode cur) { while (cur ! = root && cur.color == TreeNode.BLACK) { /*********************************************************************************************************** * cur Is the node to be deleted * B is the sibling node * P is the parent node * * [The following analysis is based on the fact that cur is the left node; if it is the right node, the condition is opposite] * Because cur exists and is black, its sibling node must exist: * * 1. If b node is red, then under the red-black tree condition, b's son node must exist, and there are two black sons: * Let b's left son be red, B is black, and rotate to the left of P; * * 2, if b is black: * 2.1, B has a right son (must be red), give the color of P to B, set the right son of P and B to black, and rotate left for P; * 2.2, b has a left son (must be red), set the son to black, b to red, b is the right node, rotate b to the right; * 2.3. B has two sons (it must be red). In this case, the treatment is the same as 2.1; * * 2.4. If B has no son, b is set as red, cur points to P, and continue to recursively up to the root node, or until the red node is encountered; * The reason for the upward recursion is that P can be red or black, and B changes from black to red, so a black node is missing. Condition 5 May not be met, so * needs to check the color of p node and its siblings. ***********************************************************************************************************/ TreeNode p = cur.parent; TreeNode b; If (cur = = p.l eft) {/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * to delete the node to the left *********************************************************************************/ b = p.right; // 1 if (b.color == TreeNode.RED) { b.left.color = TreeNode.RED; b.color = TreeNode.BLACK; rotateLeft(p); break; } // 2.4 if (b.left == null && b.right == null) {b.collor = treenode.red; cur = p; continue; } // if (b.left! = null && b.right == null) { b.left.color = TreeNode.BLACK; b.color = TreeNode.RED; rotateRight(b); } // 2.1, 2.3, and 2.2 -> 2.1 b.color = p.color; p.color = b.right.color = TreeNode.BLACK; rotateLeft(p); break; } else {/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * for the right to delete node ******************************************************************************/ b = p.left; // 1 if (b.color == TreeNode.RED) { b.right.color = TreeNode.RED; b.color = TreeNode.BLACK; rotateLeft(p); break; } // 2.4 if (b.left == null && b.right == null) {b.collor = treenode.red; cur = p; continue; } // if (b.ight! = null && b.left == null) { b.right.color = TreeNode.BLACK; b.color = TreeNode.RED; rotateLeft(b); } // 2.1, 2.3, and 2.2 -> 2.1 b.color = p.color; p.color = b.left.color = TreeNode.BLACK; rotateRight(p); break; } // May be 2.4 exit, force p node BLACK, to achieve dynamic balance cur.color = treenode.black; }}Copy the code

V. Test and results

public class Main { public static void main(String[] args) { rbTree(); } private static void rbTree() { int[] values = new int[]{ 12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17}; RBTree tree = new RBTree(null); / / keep consistent with [https://www.cs.usfca.edu/~galles/visualization/RedBlack.html] the effect of the output tree. / / priority precursor setLeftFirst (true); for (int value : values) { tree.insert(value); } tree.doPreTravel(); tree.remove(14); tree.doPreTravel(); }}Copy the code
  • Fully inserted RBT

  • Delete the RBT of node 14

Github red black tree complete source code