红黑树
节点不是红色就是黑色 。
根节点是黑色的 。
每一个叶子节点(最后的空节点)是黑色的 。
如果一个节点是红色的，那么他的孩子节点都是黑色的 。
从任意一个节点到叶子节点，经过的黑色节点是一样多的 。
这里叶子节点的定义跟之前不一样，这里的叶子节点指的是空节点，不是左右孩子节点都为空的节点。
2-3 树
满足二分搜索树的基本性质
节点可以存放一个元素或者两个元素，是一棵绝对平衡的树，任意节点的左右子树的高度差一样，比 AVL 树的平衡定义更加严格。
2-3 树添加节点时，永远不会添加到空节点中。
红黑树和2-3树的等价性
2-3 树的2节点对应红黑树的黑色节点，红色的节点代表与父节点是连在一起的，跟父节点一起组成 2-3 树中的3节点。
我们把节点横着放，对比下面这棵 2-3 树和红黑树：
按照这个等价性的定义，红黑树所有的红色节点都是左倾斜的。
详细分析红黑树的定义
每个节点不是红色就是黑色 。
答：这是一个定义，2-3 树的2节点对应红黑树的黑色节点，红色的节点代表与父节点是连在一起的，跟父节点一起组成 2-3 树中的3节点。
根节点是黑色的 。
答：根节点如果是2节点，那肯定是黑色的，如果是3节点，因为红色节点左倾斜了，父节点还是黑色的，所以根节点是黑色的。
每一个叶子节点(最后的空节点)是黑色的 。
答：这是一个定义，当整棵树为空时，那么根节点也为空，也是黑色，跟第2条属性对应上了。
如果一个节点是红色的，那么他的孩子节点都是黑色的 。
答：红节点如果连接2节点，那肯定是黑色的，如果连的是3节点，也是由于红节点左倾斜，先连接的节点肯定是左倾斜的红节点的父节点，是黑色的。
从任意一个节点到叶子节点，经过的黑色节点是一样多的 。
答：因为 2-3 树是绝对平衡的树，从任意节点到叶子节点经过的节点数量是一样的。那么在红黑树中，就等于经过的黑色节点数是一样多的。
总结：红黑树是一种黑平衡的二叉树(不是平衡二叉树，高度差可以大于1)，最大高度为 2logn，常数忽略，时间复杂度为 O(logn)。因为高度比 AVL 树要高，所以查找速度可能略差于 AVL 树，但是添加和删除等操作比较高效，整体性能更优。
红黑树添加元素
如上图所示，共有3种处理情况 ：
情况一：右节点为红色，左节点黑色，需要左旋转
左旋转代码如下：
// 左旋转，返回旋转后的根节点
private Node leftRotate(Node node) {
Node retNode = node.right;
node.right = retNode.left;
retNode.left = node;
// 新的根节点应该保持原来根节点的颜色值
retNode.color = node.color;
// 设为红色，表示加进来的节点跟之前的节点融合
node.color = RED;
return retNode;
}
情况二：左节点为红色，左节点的左节点还是红色，需要右旋转
右旋转代码如下：
// 右旋转，返回旋转后的根节点
private Node rightRotate(Node node) {
Node retNode = node.left;
node.left = retNode.right;
retNode.right = node;
// 新的根节点应该保持原来根节点的颜色值
retNode.color = node.color;
// 设为红色，表示加进来的节点跟之前的节点融合
node.color = RED;
return retNode;
}
情况三：左右节点均为红色，需要颜色翻转
颜色翻转代码如下：
private void flipColors(Node node) {
// 将左右孩子变成黑色
node.left.color =BLACK ;
node.right.color = BLACK;
// 根节点因为要向上融合，要设为红色
node.color = RED;
}
红黑树代码实现
public class RBTree<K extends Comparable<K>, V> {
// true 定义为 红色
private static final boolean RED = true;
// false 定义为 黑色
private static final boolean BLACK = false;
private Node root;
private int size;
/**
* 右旋转，返回旋转后的根节点
*/
private Node rightRotate(Node node) {
Node retNode = node.left;
node.left = retNode.right;
retNode.right = node;
// 新的根节点应该保持原来根节点的颜色值
retNode.color = node.color;
// 设为红色，表示加进来的节点跟之前的节点融合
node.color = RED;
return retNode;
}
/**
* 左旋转，返回旋转后的根节点
*/
private Node leftRotate(Node node) {
Node retNode = node.right;
node.right = retNode.left;
retNode.left = node;
// 新的根节点应该保持原来根节点的颜色值
retNode.color = node.color;
// 设为红色，表示加进来的节点跟之前的节点融合
node.color = RED;
return retNode;
}
/**
* 颜色翻转
*/
private void flipColors(Node node) {
// 将左右孩子变成黑色
node.left.color =BLACK ;
node.right.color = BLACK;
// 根节点因为要向上融合，要设为红色
node.color = RED;
}
/**
* 判断节点的颜色
*/
private boolean isRed(Node node) {
// 空节点默认为黑色节点
if (node == null) {
return false;
}
return node.color;
}
/**
* 向红黑树中添加新的元素(key, value)
*/
public void add(K key, V value) {
root = add(root, key, value);
// 最终根节点为黑色节点
root.color = BLACK;
}
/**
* 向以node为根的红黑树中插入元素(key, value)，递归算法
* 返回插入新节点后红黑树的根
*/
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (node.key.compareTo(key) < 0) {
node.right = add(node.right, key, value);
} else if (node.key.compareTo(key) > 0) {
node.left = add(node.left, key, value);
} else {
node.value = value;
}
// 右节点为红色，左节点黑色，需要 左旋转
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
// 左节点为红色，左节点的左节点还是红色，需要 右旋转
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
// 左右节点均为红色，需要颜色翻转
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
/**
* 向以 node 为根的树中查询key,递归算法
*/
private boolean contains(Node node, K key) {
if (node == null) {
return false;
}
if (key.compareTo(node.key) < 0) {
return contains(node.left, key);
} else if (key.compareTo(node.key) > 0) {
return contains(node.right, key);
} else {
return true;
}
}
public boolean contains(K key) {
if (key == null) {
return false;
} else {
return contains(root, key);
}
}
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
/**
* 向以 node 为根的树中查询key对应的结点,递归算法
*/
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else if (key.compareTo(node.key) > 0) {
return getNode(node.right, key);
} else {
return node;
}
}
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " does not exist!");
} else {
node.value = newValue;
}
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private class Node {
public K key;
public V value;
public Node left, right;
// 定义节点的颜色
public boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
// 默认新节点为红色，因为新节点肯定要和之前的节点做融合
this.color = RED;
}
}
}
RBTree 和 AVLTree 的性能比较
BST在元素按排序的方式插入时，会退化成链表，因为 BST 没有自平衡机制。所以这里只比较红黑树和 AVL 树的性能。
整体性能测试：
public static void main(String[] args) {
System.out.println("Pride and Prejudice");
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("F:\\java_projects\\data_structure\\DataStructures\\src\\pride-and-prejudice.txt", words)) {
System.out.println("Total words: " + words.size());
// Collections.sort(words);
// Test BST
long startTime = System.nanoTime();
BSTMap<String, Integer> bst = new BSTMap<>();
for (String word : words) {
if (bst.contains(word))
bst.set(word, bst.get(word) + 1);
else
bst.add(word, 1);
}
for(String word: words)
bst.contains(word);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
System.out.println("BST: " + time + " s");
// Test AVL
startTime = System.nanoTime();
AVLTree<String, Integer> avl = new AVLTree<>();
for (String word : words) {
if (avl.contains(word))
avl.set(word, avl.get(word) + 1);
else
avl.add(word, 1);
}
for(String word: words)
avl.contains(word);
endTime = System.nanoTime();
time = (endTime - startTime) / 1000000000.0;
System.out.println("AVL: " + time + " s");
// Test RBTree
startTime = System.nanoTime();
RBTree<String, Integer> rbt = new RBTree<>();
for (String word : words) {
if (rbt.contains(word))
rbt.set(word, rbt.get(word) + 1);
else
rbt.add(word, 1);
}
for(String word: words)
rbt.contains(word);
endTime = System.nanoTime();
time = (endTime - startTime) / 1000000000.0;
System.out.println("RBTree: " + time + " s");
}
}
运行结果如下：
BST: 0.578413541 s
AVL: 0.493906978 s
RBTree: 0.41666528 s
只测试添加操作的性能
public static void main(String[] args) {
int n = 20000000;
Random random = new Random(n);
ArrayList<Integer> testData = new ArrayList<>(n);
for(int i = 0 ; i < n ; i ++)
testData.add(random.nextInt(Integer.MAX_VALUE));
Collections.sort(testData);
// Test RBTree
long startTime = System.nanoTime();
RBTree<Integer, Integer> rbt = new RBTree<>();
for (Integer x: testData)
rbt.add(x, null);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
System.out.println("RBTree: " + time + " s");
// Test AVL
startTime = System.nanoTime();
AVLTree<Integer, Integer> avl = new AVLTree<>();
for (Integer x: testData)
avl.add(x, null);
endTime = System.nanoTime();
time = (endTime - startTime) / 1000000000.0;
System.out.println("AVL: " + time + " s");
}
运行结果如下：
RBTree: 17.118380952 s
AVL: 14.228043812 s
总结： 两者性能相差不大，因为都是 O(logn) 级别的。
二分搜索树、AVL、红黑树性能总结
对于完全随机的数据，普通的二分搜索树很好用，缺点是在极端情况下会退化成链表(或者高度不平衡)。
对于查询较多的使用情况，AVL树很好用。
红黑树牺牲了平衡性(2logn的高度)，统计性能更优(综合增删改查所有的操作)。系统标准库类的底层用到的树基本都是红黑树。
最后说明
这里的红黑树的实现不是最优实现，还有更优的实现方式，这里只为学习红黑树的内部原理。