# Red and black tree

A red-black Tree “RBT” is a self-balancing (not absolutely balanced) binary search Tree (BST) with each node following the following rules:

1. Each node is either black or red.
2. The root node is black.
3. Each leaf node (NIL) is black.
4. Every red node has two children that must be black.
5. The path from any node to each leaf node contains the same number of black nodes.

What does a red-black tree do to balance itself? Three operations: left, right and color change

## 1 Rotation operation

### 1.1 Concept Explanation

Left-spin: 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``

Left-handed code implementation

``/ around a left-handed p * * * * p (r) * / | pr / \ * pl pr (r) = > p rr * / \ \ * rl rr pl rl left-handed 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 pr-rl to p-rl // 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``

Right-handed 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``

Adding nodes in a two-three-four tree must comply with the following rules:

• Insertions are always inserted into the bottom layer
• Ascending element: upgrade the insertion node from 2-node to 3-node, or from 3-node to 4-node;
• After inserting elements into 4-node, we need to raise the middle element to the ascending element of the parent node, the original node becomes two 2-nodes, and then insert the element into 2-node. If the parent node is also a 4-node, 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 red-black tree would be:

• The newly inserted node is red in color, so that it may not affect the height of the red-black tree.
• The 2-node corresponds to a single black node in the red-black tree, and the insertion succeeds directly (corresponding to the 2-node ascending element).
• The 3-node corresponds to the black + red subtree in the red-black tree. After insertion, it is restored to the red + black + red subtree (corresponding to the 3-node ascending element).
• The 4-node corresponds to the red + black + red subtree in the red-black 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: Red-black tree + New node (red) **=** Peer two-three-four tree + new node

### 2.1 Example of Adding a Node

We map the node additions to the corresponding red-black tree by adding a two-three-four tree

Two-three-four 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 red-black 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 red-black tree is

### 2.2 New code implementation

Now that the new rules for red-black 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 red-black 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 2-3-4 tree 2 node to add a new element element, will merge into 3 nodes directly, node * there are two elements in the red-black 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.two-three-four 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 * Red-black 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.two-three-four 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 two-three-four tree, see if you understand

Inserted scene

Insert scene 1: the red-black 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 red-black 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 red-black tree will not be affected. The inserted node can be directly inserted without self-balancing. Processing: Direct insertion.

Insert scenario 3: The parent of the insert node is red again recall the properties of red-black 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 red-black 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 bottom-up 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 red-black 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