1. The definition of red-black tree
A red-black tree is a binary lookup tree that contains red-black links and satisfies the following conditions:
Red links are all left links. 2. No node is connected to two red links at the same time. The tree is perfectly black balanced, with the same number of black links on any empty link path to the root nodeCopy the code2-3 trees and red – black trees
2. Red-black tree API
2.1 node class
Since each Node has a link to itself (from its parent), we can add a Boolean variable color to the previous Node Node to indicate the color of the link. This variable is true if the link to it is red, and false if the link to it is black
private class Node<Key.Value> {
/ / store the key
private Key key;
/ / store the value
private Value value;
// Left child node
private Node left;
// Right child node
private Node right;
// The color of the link pointing to it from its parent
private boolean color;
public Node(Key key, Value value, Node left, Node right, boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color; }}Copy the code2.2 equilibration
L:
When the left child of a node is black and the right child is red, left-handed rotation is required.
* Sinistral is the rotation of a node to the left child of its right child *
** Premise: the current node of ** is h, and its right child is X
The process of left-handed rotation:
1. Change the left child of x to the right child of H: h.light =x.left;
2. Make h the left child of x: x.left=h;
X.color =h.color; x = x.color;
4. Set h color to RED: h.color=true;
Right:
When the left child of a node is red, and the left child of a node is red, you have to rotate it right
** Dextral is the rotation of a node to the right child of its left child **
** premise: the current node of ** is h, its left child is X;
Dextral process:
-
Let the right child of X be the left child of H: H.left = X.right;
-
Let h be the right child of x: x. Light =h;
-
Change x’s color to h’s color: x.color = h.color;
-
Let h be RED;
After right rotation, the left and right links are red, requiring color inversion
2.3 code
/ * * *@Author blackcat
* @create2021/6/24 men *@version: 1.0
* @description: * /
public class RedBlackTree<Key extends Comparable<Key>, Value> {
/ / the root node
private Node root;
// Record the number of elements in the tree
private int N;
// Red link
private static final boolean RED = true;
// Black links
private static final boolean BLACK = false;
class Node {
/ / store the key
private Key key;
/ / store the value
private Value value;
// Left child node
private Node left;
// Right child node
private Node right;
// The color of the link pointing to it from its parent
private boolean color;
public Node(Key key, Value value, Node left, Node right, boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color; }}// Check whether the parent link of the current node is red
private boolean isRed(Node x) {
if (x == null) {
return false;
}
return x.color == RED;
}
// Left-turn adjustment
private Node rotateLeft(Node h) {
// Find the right child of the current node h
Node x = h.right;
// change the left child of x to the right child of h
h.right = x.left;
// make h the left child of x
x.left = h;
// change h's color to x's color
x.color = h.color;
// change the color of current node H to RED
h.color = RED;
return x;
}
// Right-handed adjustment
private Node rotateRight(Node h) {
// Get the left child node
Node x = h.left;
// make the right child of x the left child of h
h.left = x.right;
// make h the right child of x
x.right = h;
// change x's color to h's color
x.color = h.color;
// set h's color to RED
h.color = RED;
return x;
}
// Color inversion, equivalent to complete split 4-node
private void flipColors(Node h) {
// The color property of the current node changes to RED;
h.color = RED;
// The color attribute values of the left and right children of the current node are black
h.left.color = BLACK;
h.right.color = BLACK;
}
// Insert the entire tree
public void put(Key key, Value val) {
put(root, key, val);
// Change the root color to BLACK
root.color = BLACK;
}
// In the specified tree, the insert operation is completed and the new tree is returned after the element is added
private Node put(Node h, Key key, Value val) {
// If h is null, return a red node
if (h == null) {
/ / the number of + 1
N++;
return new Node(key, val, null.null, RED);
}
// Compare the size of the key and key on node H
int cmp = key.compareTo(h.key);
if (cmp < 0) {
// Continue to the left
h.left = put(h.left, key, val);
} else if (cmp > 0) {
// Continue to the right
h.right = put(h.right, key, val);
} else {
// A value substitution occurs
h.value = val;
}
// Left-turn: when the left child of h is black and the right child is red, left-turn is required
if(isRed(h.right) && ! isRed(h.left)) { h = rotateLeft(h); }// Turn right: when the left child of the current node h and the left child of the current node h are both red, you need to turn right
if (isRed(h.left) && isRed(h.left.left)) {
rotateRight(h);
}
// Color inversion: color inversion is required when both the left and right children of the current node are red
if (isRed(h.left) && isRed(h.right)) {
flipColors(h);
}
return h;
}
// Find the corresponding value from the tree according to the key
public Value get(Key key) {
return get(root, key);
}
// Select key from the specified tree x
private Value get(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp > 0) {
// If the key of the new node is greater than the key of the current node, continue to find the right child of the current node
return get(x.right, key);
} else if (cmp < 0) {
// If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node
return get(x.left, key);
} else {
// If the key of the new node is equal to the key of the current node, it is returned directly
returnx.value; }}// Get the number of elements in the tree
public int size(a) {
returnN; }}Copy the code