Red and black tree
A redblack Tree “RBT” is a selfbalancing (not absolutely balanced) binary search Tree (BST) with each node following the following rules:
 Each node is either black or red.
 The root node is black.
 Each leaf node (NIL) is black.
 Every red node has two children that must be black.
 The path from any node to each leaf node contains the same number of black nodes.
What does a redblack tree do to balance itself? Three operations: left, right and color change
1 Rotation operation
1.1 Concept Explanation
Leftspin: take a node as the rotation point, its right child node becomes the parent node of the rotation node, the left child node of the right child node becomes the right child node of the rotation node, and the left child node remains unchanged.
Dextral: to some! The left child node of the left child node becomes the parent node of the rotation node, and the right child node of the left child node becomes the left child node of the rotation node, while the right child node remains unchanged.
1.2 Code implementation
Start by defining the class structure
package com.bobo.util.treemap; public class BRTree { private static final boolean RED = false; private static final boolean BLACK = true; private RBNode root; public RBNode getRoot() { return root; } public void setRoot(RBNode root) { this.root = root; } @param <K> * @param <V> */ static class RBNode<K extends Comparable<K>,V>{// The node is a private RBNode parent; private RBNode left; private RBNode right; private boolean color; private K key; private V value; public RBNode() { } public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) { this.parent = parent; this.left = left; this.right = right; this.color = color; this.key = key; this.value = value; } public RBNode getParent() { return parent; } public void setParent(RBNode parent) { this.parent = parent; } public RBNode getLeft() { return left; } public void setLeft(RBNode left) { this.left = left; } public RBNode getRight() { return right; } public void setRight(RBNode right) { this.right = right; } public boolean isColor() { return color; } public void setColor(boolean color) { this.color = color; } public K getKey() { return key; } public void setKey(K key) { this.key = key; } public V getValue() { return value; } public void setValue(V value) { this.value = value; }}}Copy the code
Lefthanded code implementation
/ around a lefthanded p * * * * p (r) * /  pr / \ * pl pr (r) = > p rr * / \ \ * rl rr pl rl lefthanded when * * * p  connection between the pl and pr  rr * pr  rl will be turned into P rl * that is, rl will become the right child of p * and p will become the parent of rL * and we will determine if p has a parent * if no * r will become the root node * if r.parent = p.parent * and we will set r to P.arent. left == p * p.arent. left = r; * otherwise * p.arent. right = r; * last * parent = r; * r.left = p; * @param p */ private void leftRotate(RBNode p){ if(p ! = null){ RBNode r = p.right; // set prrl to prl // set rl to p right child node p.light = r.tip; if(r.left ! = null){// set the parent of rL to p r.lift. parent = p; } // 2. Determine the parent node of p r.parent = p.parent; If (p parent == null){root = r; }else if(p.arent. left == p){p.arent. left = r; }else{p.arent. right = r;}else{p.arent. right = r;}else{p.arent. right = r; // set r to the right child of r; // set r to the left child of r; p.parent = r; }}Copy the code
Righthanded implementation:
Public void rightRotate(RBNode p){if(RBNode p! = null){ RBNode r = p.left; p.left = r.right; if(r.right ! = null){ r.right.parent = p; } r.parent = p.parent; if(p.parent == null){ root = r; }else if(p.parent.left == p){ p.parent.left = r; }else{ p.parent.right = r; } r.right = p; p.parent = r; }}Copy the code
2 Adding a Node
www.processon.com/view/link/6…
Adding nodes in a twothreefour tree must comply with the following rules:
 Insertions are always inserted into the bottom layer
 Ascending element: upgrade the insertion node from 2node to 3node, or from 3node to 4node;
 After inserting elements into 4node, we need to raise the middle element to the ascending element of the parent node, the original node becomes two 2nodes, and then insert the element into 2node. If the parent node is also a 4node, then recurse to the ascending element of the upper level, and increase the height of the tree by 1 when reaching the root node.
And corresponding those rules to a redblack tree would be:
 The newly inserted node is red in color, so that it may not affect the height of the redblack tree.
 The 2node corresponds to a single black node in the redblack tree, and the insertion succeeds directly (corresponding to the 2node ascending element).
 The 3node corresponds to the black + red subtree in the redblack tree. After insertion, it is restored to the red + black + red subtree (corresponding to the 3node ascending element).
 The 4node corresponds to the red + black + red subtree in the redblack tree. After insertion, it is restored to the red grandparent + black grandparent + red child subtree. Then, the grandparent is treated as the newly inserted red node and recursively repaired to the upper level until the repair is successful or the root node is encountered.
Formula: Redblack tree + New node (red) **=** Peer twothreefour tree + new node
2.1 Example of Adding a Node
We map the node additions to the corresponding redblack tree by adding a twothreefour tree
Twothreefour tree additions (all done in leaves)
1. Add a node and two nodes
2. Add a node and merge it with the two nodes
3. Add a node and merge it with the three nodes
There are three possible positions for the inserted value
The corresponding redblack tree is:
4. Add a node and merge it with the four nodes.
The position of the insert value might be
The structure of the corresponding redblack tree is
2.2 New code implementation
Now that the new rules for redblack trees are clear, you can implement them in Java code.
So let’s do the insert node, which is a normal binary tree insert
/** * new node * @param key * @param value */ public void put(K key, V value){RBNode t = this.root; If (t == null){root = new RBNode<>(key, value == null? key : value,null); return ; } int cmp ; RBNode parent; RBNode parent; if(key == null){ throw new NullPointerException(); } // Do {parent = t; cmp = key.compareTo((K)t.key); If (CMP < 0){if(CMP < 0); }else if(CMP > 0){// t = t.light; }else{// Insert node value == compare node. Replacement value t.s etValue (value = = null? key:value); return; } }while (t ! = null); RBNode<K, Object> e = new RBNode<>(key, value == null? key : value, parent); If (CMP < 0){parent. Left = e; }else{ parent.right = e; } // Adjust the color rotation fixAfterPut(e); }Copy the code
And then adjust it according to the characteristics of the redblack tree (rotation, color change)
private boolean colorOf(RBNode node){ return node == null ? BLACK:node.color; } private RBNode parentOf(RBNode node){ return node ! = null ? node.parent:null; } private RBNode leftOf(RBNode node){ return node ! = null ? node.left:null; } private RBNode rightOf(RBNode node){ return node ! = null ? node.right:null; } private void setColor(RBNode node ,boolean color){ if(node ! = null){ node.setColor(color); }} / * * * insert node after the adjustment of processing * 1. The 234 tree 2 node to add a new element element, will merge into 3 nodes directly, node * there are two elements in the redblack tree: Add a red node, the red node will be added under the black node (2 nodes)  this case does not need to be adjusted * 2.twothreefour tree add 3 nodes add one element to make 4 nodes merge node 3 elements * there are 6 cases, (root left, left, left, left, right, right, right) These four need to be adjusted (left, center, right) none need to be adjusted * Redblack tree: new red nodes are added to the black nodes on top and red nodes on bottom = After sorting, middle nodes are black, and nodes on both sides are red * * 3.twothreefour tree: Add an element that needs to be split: the middle element is upgraded to the parent, and the new element is merged with one of the remaining ones. The new node is red + the grandfather node is black, the father node and the uncle node are red, the grandfather node is red, the father node and the uncle node are black, * @param x */ private void fixAfterPut(RBNode<K, Object> x) {x.color = RED; // If the parent node is black, you don't need to adjust it. If the parent node is black, you don't need to adjust it. = null && x ! = root && x.parent.color == RED){if(parentOf(x) == parentOf(x)).left) RBNode y = rightOf(parentOf(parentOf(x))); SetColor (parentOf(x),BLACK); setColor(parentOf(x),BLACK); setColor(y,BLACK); SetColor (parentOf(parentOf(x)),RED); ParentOf (parentOf(x)); }else{if(x == parentOf(x).right){// if(x == parentOf(x).right){// if(x == parentOf(x).right); leftRotate(x); } // setColor(parentOf(x),BLACK); // setColor(parentOf(x),BLACK); SetColor (parentOf(parentOf(x)),RED); RightRotate (parentOf(parentOf(x))); RBNode y = leftOf(parentOf(parentOf(x))); RBNode y = leftOf(parentOf(x)); Stickline (parentOf(x), parentOf(x), parentOf(x),BLACK), colorred; setColor(y,BLACK); setColor(parentOf(parentOf(x)),RED); x = parentOf(parentOf(x)); }else{// case 2 if(x == parentOf(x).left){x = parentOf(x); rightRotate(x); } setColor(parentOf(x),BLACK); setColor(parentOf(parentOf(x)),RED); leftRotate(parentOf(parentOf(x))); } } } root.color = BLACK; }Copy the code
2.3 Inserting a Node
I’m going to do the analysis of adding nodes without using a twothreefour tree, see if you understand
Inserted scene
Insert scene 1: the redblack tree is empty
In the simplest case, we just use the insertion node as the root, but note that the root node is black according to property 2 of a redblack tree. You also need to set the insert to black. Processing: make the insertion node the root node and set the node to black.
Insert scenario 2: The parent node of the inserted node is black. Since the inserted node is red and the parent node is black, the balance of the redblack tree will not be affected. The inserted node can be directly inserted without selfbalancing. Processing: Direct insertion.
Insert scenario 3: The parent of the insert node is red again recall the properties of redblack trees 2: the root is black. If the parent of the insert is red, then the parent cannot be the root, so there is always a grandparent of the insert. This is important because subsequent rotations definitely require the involvement of the grandparent.
Insert scenario 3.1: the uncle node exists and is a red node from the redblack tree property 4 yes, the grandparent must be a black node, because there cannot be two connected red nodes at the same time. In this case, the number of red and black layers that should be inserted into the subtree is: black red red. Obviously the easiest way to do this is to change it to red black red.
Actual case:
The grandfather node is the root node: red black black
The grandparent is not the root node:
Insert scenario 3.2** : The uncle node does not exist or is black, and the parent of the inserted node is the left child of the grandparent
From the perspective of insertion alone, that is, excluding the case of bottomup processing in scenario 3.1, if the uncle node is not red, it is a leaf node (Nil). Because if the uncle is black and the parent is red, then there are more black nodes in the subtree of the uncle than there are in the subtree of the parent, and that doesn’t satisfy the redblack tree property 5. The same is true of the following scenarios, which will not be explained further.
As I said before, when you need to rotate, you must rent or lend to one side of the subtree if it has too many or too few nodes. Insert is obviously the case of many, so you just rent the nodes that are many to the subtree on the other side.
Insert scenario 3.2.1: The insert node is the left child of its parent
Insert scenario 3.2.2: The uncle node does not exist or is black, and the father node of the insert node is the right child of the grandparent
Ok, red black tree add operation we introduced here, next we will give you a detailed introduction of red black tree delete operation oh
Read three things ❤️
If you found this post helpful, I’d like to invite you to do three small favors for me:

Likes, retweets, and your “likes and comments” are what drive me to create.

Follow the public account “Java rotten pigskin”, irregularly share original knowledge.

【666】 Scan the code to get the learning materials package

At the same time, look forward to the following article ing🚀