The Java Collection Detailed Series is a new series that I am going to start after I have completed a series of blogs that consolidate the Java Foundation Chapter.
These articles will be sorted out into my Java Interview Guide warehouse on GitHub, and more exciting content can be found in my warehouse.
https://github.com/h2pl/Java-...
If you like, please click Star, fork Ha
The article was first published on my personal blog:
www.how2playlife.com
What is a red-black tree?
First of all, what is a red-black tree? Red-black tree is a kind of "balanced" binary search tree. It is a classical and efficient algorithm, which can ensure that the operation time of dynamic set is O (lgn) in the worst case. Each node of the red-black tree contains five domains: color,key,left,right and p. Color is a storage bit added to each node to represent the color of the node, which can be RED or BLACK. Key is the value value of the node, left,right is the left and right child pointer of the node, if not NIL, p is a pointer, referring to the parent node of the section. The following image (from Wikipedia) shows a red-black tree with NIL as a pointer to an external node. (External nodes are treated as nodes without keys)
What is the nature of red-black trees? Generally known as the red black property, it has the following five points:
1) Each node is either red or black;
2) The root node is black;
3) Each leaf node (NIL) is black;
4) If a node is red, both of its children are black;
5) For each node, all paths from that node to other descendant nodes contain the same number of black nodes.
For further analysis, we have the following knowledge points.
(1) Black height: The number of black nodes on any path from a node x (excluding the node) to a leaf node is called the black height of the node X.
(2) The height of a red-black tree with n inner nodes is at most 2lg(n+1). (The inner node is regarded as the node with keywords in the red-black tree)
(3) The height of the red-black tree with n internal nodes is O (log (n).
Definition
Red-black tree is a special binary search tree, also known as R-B tree (RED-BLACK-TREE). Because red-black tree is a special binary search tree, that is, red-black tree has the characteristics of binary search tree, and red-black tree also has the following characteristics:
- 1. Each node is either black or red
- 2. The root node is black
- 3. Each leaf node is black and empty (another way of saying is that each leaf node has two empty black nodes (called black sentries). If there is only one left child in a node n, then the right child of n is a black sentry; if there is only one right child in a node n, then the left child of n is a black sentry. )
- 4. If a node is red, its children must be black.
- 5. All paths from a node to its descendants contain the same number of black nodes.
Several points need to be noted:
1. Feature 3 specifies that every leaf node of the red-black tree is empty, but in Java implementation, the red-black tree will use null to represent the empty node, so when traversing the red-black tree, the black leaf node can not be seen, but the leaf node is red.
2. Feature 4 guarantees that the longest path from the root node to the leaf node will not exceed twice the length of any other path, such as the red-black tree with a black height of 3, the shortest path (path refers to root node to leaf node) is 2 (black node-black node-black node), and the longest path is 4 (black node-red node-black node-red node-black node).
practice
Mangrove operation
Insert operation
Firstly, when inserting red-black trees into nodes, we set the color of inserting nodes to red. If inserting black nodes, it will violate characteristic 5. That is to say, the black height of red-black trees is changed. There are several situations when inserting red nodes as follows:
1. black father
As shown in the figure, this situation does not destroy the characteristics of the red-black tree, that is, it does not require any processing.
2. red father
When his father is red, there are the following situations
- Uncle red
In fact, the case of Uncle Hong is relatively simple. As shown in the figure below, you only need to change the color of father and uncle to black, the color of ancestor to red, and go back to check the ancestor node recursively.
- Uncle black
There are several cases of Uncle Hei, which can not achieve balance by modifying the color. Therefore, there are two kinds of rotation operations in the red-black tree species, left-handed and right-handed (there are questions now, when to use left-handed and when to use right-handed).
- Case 1: [First right-handed, changing the color (root node must be black, its two sub-nodes must be red, uncle node need not be changed)], as shown in the following figure, notice to omit the black sentry node
- Case 2: [First turn left to Case1, then right, and finally change the color (the root node must be black, its two sub-nodes must be red, the uncle node need not change)], as shown in the following figure, notice to omit the black sentry node
- Case 3: [First left-handed, last changed color (root node must be black, its two sub-nodes must be red, uncle node need not change)], as shown in the following figure, notice to omit the black sentry node
- Case 4: [First turn right into Case 3, then turn left, and finally change the color (the root node must be black, its two child nodes must be red, the uncle node need not change)], as shown in the following figure, notice to omit the black sentry node
These are all possible operations for adding new nodes to the red-black tree. The deletion operations in the red-black tree are described below.
Delete operation
The deletion operation is more complicated than the insertion operation. There are three kinds of deletion cases for a node:
- 1. The deleted node has no child node, that is, the current node is a leaf node, which can be deleted directly.
- 2. The deleted node has a child node, which needs to delete the current node and replace it with its child node.
- 3. The deleted node has two child nodes, which need to find its successor node (the smallest element larger than the node in the tree); then copy the content of the successor node to the node, and the successor node is equivalent to the substitute of the node. It should be noted that the successor node will not have two child nodes (which should be well understood, if the successor node has a left child node). Point, then the current successor node is certainly not the smallest, indicating that the successor node can only exist without child nodes or only one right child node, that is to say, the problem will be converted into 1,2 mode.
Before we talk about repair operations, we need to understand a few points.
1. For a red-black tree, the situation of a single node is only as follows: the current node is black and its child node is red. (1) Assuming the current node is red, its two child nodes must be black. 2. If there are grandchildren nodes, they must be black, resulting in different number of sunspots, while the red-black tree is not balanced.)
2. Because the red-black tree is a special binary search tree, its deletion and binary search tree type, the real deletion point is the successor of the ordinal traversal of deletion point A (successor can also be). Through the characteristics of the red-black tree, we can see that this successor must have at most one child, whose child node must be the right child node, so that in a single case (that is, this successor node can only have one child). Red children or no children)
Following is a detailed description of how to balance the red and black trees through repair operations after the deletion of nodes.
- Case 1: if the node to be deleted is red, it must be a leaf node (first, the node to be deleted here refers to the node to be deleted. The node to be deleted is either the node itself or its successor. If it is a leaf node, it must be a leaf node. If it is not a leaf node, it will have left and right children. Then it is the node to be deleted. The minimum value of the right child tree, if the successor node, must also be the leaf node, if not, it will also have left and right children, which is contrary to 2. In this case, delete the red leaf node can be done without other operations.
- Case 2: The deleted node is black and its child node is red. Replace its child node and change its color to black, as shown in the figure below.
-
Case 3: The deleted node is black, and its child nodes are black. Replacement of its child nodes becomes a Double-black problem. Here are the following situations
- Case 1: The sibling node of the new node is red. If the new node is left-handed, it will do left-handed operation. Otherwise, it will do right-handed operation. Then it will change the color of its parent node to red, sibling node.
As can be seen from the figure, after the operation, the red and black trees did not reach equilibrium, but became black brothers.
-
Case 2: The sibling node of the new node is black. This may be the case
- Red Father and Black Nephew: Turn the parent node into black, the brother node into red, and the new node into black, as shown in the figure below.
- Black Father and Black Nephew: Change the parent node into the color of the new node, the new node into black, and the brother node into red. We need to continue to judge the parent node as the decision point, as shown in the figure below.
- Red nephew:
Scenario 1: The new node is in the right subtree, and the red nephew is in the left subtree of the brother node. At this time, the operation is right-handed, and the brother node becomes the father's color, the father node becomes black, and the nephew node becomes black, as shown in the following figure.
Scenario 2: The new node is in the right subtree, and the red nephew is in the right subtree of the brother node. At this time, the operation is left-handed first, then right-handed and the nephew node becomes the father's color, and the parent node becomes black, as shown in the following figure.
Case 3: The new node is in the left subtree, and the red nephew is in the left subtree of the brother node. At this time, the operation is right-handed first, left-handed and the nephew node becomes the father's color. The father node becomes black, as shown in the following figure.
Case 4: The new node is in the right subtree, and the red nephew is in the right subtree of the brother node. At this time, the operation is left-handed, and the brother node becomes the color of the parent node. The father node becomes black, and the nephew node becomes black, as shown in the figure below.
Red-Black Tree Realization
The following is the process of using JAVA code to implement the red-black tree, including insertion, deletion, left-handed, right-handed, traversal and other operations.
insert
/* Insert a node * @param node */ private void insert(RBTreeNode<T> node){ int cmp; RBTreeNode<T> root = this.rootNode; RBTreeNode<T> parent = null; //Which parent node is the location node added to while(null != root){ parent = root; cmp = node.key.compareTo(root.key); if (cmp < 0){ root = root.left; } else { root = root.right; } } node.parent = parent; //Represents that there is currently no node, then the new node is the root node. if (null == parent){ this.rootNode = node; } else { //Find out the location of the new node under the current parent node cmp = node.key.compareTo(parent.key); if (cmp < 0){ parent.left = node; } else { parent.right = node; } } //Set the color of the insertion node to red node.color = COLOR_RED; //Modified to Red-Black Tree insertFixUp(node); } /** * Red-Black Tree Insertion Correction * @param node */ private void insertFixUp(RBTreeNode<T> node){ RBTreeNode<T> parent,gparent; //The parent node of the node exists and is red while( ((parent = getParent(node)) != null) && isRed(parent)){ gparent = getParent(parent); //What if its grandfather node is empty? // If the parent node is the left child of the grandfather node if(parent == gparent.left){ RBTreeNode<T> uncle = gparent.right; if ((null != uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node = gparent; continue; } if (parent.right == node){ RBTreeNode<T> tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } setColorBlack(parent); setColorRed(gparent); rightRotate(gparent); } else { RBTreeNode<T> uncle = gparent.left; if ((null != uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node = gparent; continue; } if (parent.left == node){ RBTreeNode<T> tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } setColorBlack(parent); setColorRed(gparent); leftRotate(gparent); } } setColorBlack(this.rootNode); }
The operation of inserting nodes is divided into the following steps:
- 1. Location: That is, traversing the red-black tree to determine the location of the addition, such as insert method in the code above is to find the location of the addition.
- 2. Repair: This is also the previous introduction, adding elements may make the red-black tree do not meet its characteristics, at this time need to change color, rotation to adjust the red-black tree, that is, insertFixUp method in the above code.
Delete node
Here is the code to delete the node
private void remove(RBTreeNode<T> node){ RBTreeNode<T> child,parent; boolean color; //Neither left nor right child is empty when the deleted node is deleted if ((null != node.left) && (null != node.right)){ //Gets the successor node of the deleted node RBTreeNode<T> replace = node; replace = replace.right; while(null != replace.left){ replace = replace.left; } //Node node is not root node if (null != getParent(node)){ //Node is the left node if (getParent(node).left == node){ getParent(node).left = replace; } else { getParent(node).right = replace; } } else { this.rootNode = replace; } child = replace.right; parent = getParent(replace); color = getColor(replace); if (parent == node){ parent = replace; } else { if (null != child){ setParent(child,parent); } parent.left = child; replace.right = node.right; setParent(node.right, replace); } replace.parent = node.parent; replace.color = node.color; replace.left = node.left; node.left.parent = replace; if (color == COLOR_BLACK){ removeFixUp(child,parent); } node = null; return; } if (null != node.left){ child = node.left; } else { child = node.right; } parent = node.parent; color = node.color; if (null != child){ child.parent = parent; } if (null != parent){ if (parent.left == node){ parent.left = child; } else { parent.right = child; } } else { this.rootNode = child; } if (color == COLOR_BLACK){ removeFixUp(child, parent); } node = null; }
/** * Delete repair * @param node * @param parent */ private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){ RBTreeNode<T> other; //Node is not empty and black, and is not the root node while ((null == node || isBlack(node)) && (node != this.rootNode) ){ //Node is the left child of the parent node if (node == parent.left){ //Get his right child other = parent.right; //The sibling node of the node is red if (isRed(other)){ setColorBlack(other); setColorRed(parent); leftRotate(parent); other = parent.right; } //The sibling node of the node is black, and the two child nodes of the sibling node are also black. if ((other.left == null || isBlack(other.left)) && (other.right == null || isBlack(other.right))){ setColorRed(other); node = parent; parent = getParent(node); } else { //The sibling node of the node is black, and the right child of the sibling node is red. if (null == other.right || isBlack(other.right)){ setColorBlack(other.left); setColorRed(other); rightRotate(other); other = parent.right; } //The sibling node of the node is black, and the right child of the sibling node is red, and the left child is arbitrary color. setColor(other, getColor(parent)); setColorBlack(parent); setColorBlack(other.right); leftRotate(parent); node = this.rootNode; break; } } else { other = parent.left; if (isRed(other)){ setColorBlack(other); setColorRed(parent); rightRotate(parent); other = parent.left; } if ((null == other.left || isBlack(other.left)) && (null == other.right || isBlack(other.right))){ setColorRed(other); node = parent; parent = getParent(node); } else { if (null == other.left || isBlack(other.left)){ setColorBlack(other.right); setColorRed(other); leftRotate(other); other = parent.left; } setColor(other,getColor(parent)); setColorBlack(parent); setColorBlack(other.left); rightRotate(parent); node = this.rootNode; break; } } } if (node!=null) setColorBlack(node); }
Deleting nodes can be divided into several cases to do the corresponding processing:
-
1. Delete nodes, according to the following three cases to delete nodes
- 1. Truly deleted nodes have no child nodes
- 2. Truly deleted nodes have a child node
- 3. The node being deleted has two sub-nodes
- 2. repair the characteristics of red and black trees, such as calling the removeFixUp method in code to restore the characteristics of red black trees.
3. summary
The above mainly introduces some characteristics of red and black trees, including some operations to analyze the process in detail, writing time is relatively long, the feeling is really more difficult to understand. Later will continue to understand more in-depth, if there are problems, please correct.
Reference articles
Implementation of Red and Black Tree (V) Java
Research on TreeMap Red-Black Tree Algorithms by Analyzing JDK Source Code
Insertion and deletion of red and black trees
In-depth analysis of red-black tree and its Java implementation
Wechat Public Number
Java Technology
If you want to pay real-time attention to my updated articles and shared dried goods, you can pay attention to my public number (Java Technology Jianghu), a technology station of an Ali Java engineer, by Huang Xiaoxiao, focusing on Java related technologies: SSM, Spring Boot, MySQL, distributed, middleware, cluster, Linux, network, multi-threading, occasionally talking about Docker, ELK, and sharing at the same time. Technical dry goods and learning experience, dedicated to Java stack development!
Java Engineers Necessary Learning Resources: Some Java Engineers commonly use learning resources. After paying attention to the public number, the keyword "Java" can be answered in the background for free without routine access.
Personal Public No. Huang Xiaoxiao
Huang Xiaoxiao is a 985 master of cross-examination software engineering. He has taught himself Java for two years. He has been offer ed by nearly ten big factories, such as BAT, and has grown from a technical Xiaobai to an Ali engineer.
The author focuses on the JAVA back-end technology stack, and is keen to share the programmer's dry goods, learning experience, job-hunting experience and program life. At present, Huang Xiaoxie's CSDN blog has a million + visits, and knows that fans are 2W +, and the whole network has 10W + readers.
Huang Xiaoxiao is a slash youth, who insists on learning and writing. He believes in the power of lifelong learning. He hopes to make friends with more programmers and make progress and grow together. Pay attention to the public number [Huang Xiaoxiao], and then reply [original e-book]. You can get my original e-book `The Training Manual for Rookie Programmers: From Technical Xiaobai to Alibaba Java Engineer'.
Programmer 3T technology learning resources: Some programmers learn technology resources package, after paying attention to the public number, the background reply keyword "information" can be free of charge without routine access.
This article by the blog article multiple platform OpenWrite Release!