（点击
上方公众号
，可快速关注）
来源：ziwenxie，
www.ziwenxie.site/2017/03/20/algorithm-red-black-tree/
如有好文章投稿，请点击 → 这里了解详情
引言
红黑树是在实际工程中被广泛应用的一种数据结构，比如Linux中的线程调度就是使用的红黑树来管理进程控制块，而Nginx中也是使用红黑树来管理的timer，Java中的TreeMap和TreeSet也是基于红黑树来实现的。红黑树相比普通二叉查找树的一个优势就是它的树高为~lgN，所以不管是查找/插入/删除操作它均能保证能够在对数时间之内完成。本文我们就先来了解一下红黑树插入算法的实现。
红黑树的定义
红黑树可以定义成含有红黑链接并且满足下列条件的二叉查找树：
比如下图就是一棵典型的红黑树，如果之前了解过2-3树的话(不了解也没有关系，我们下面的内容并不会涉及到2-3树)，可以发现如果将红黑树中的红色结点画平，实际上它就是2-3树的一种变形，不过相比2-3树，红黑树的查找操作要简单的多，但它同时也结合了2-3树中高效的插入操作，所以说红黑树其实是普通的二叉查找树和2-3树两种数据结构优点的结合。
在实现红黑树之前我们先来定义一棵红黑树：
public class RedBlackLiteBST
, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; // root of the BST
private int n; // number of key-value pairs in BST
// BST helper node data type
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // links to left and right subtrees
private boolean color; // color of parent link
public Node(Key key, Value val, boolean color) {
this.key = key;
this.val = val;
this.color = color;
}
}
}
在上面的代码中，我们将链接的颜色保存在表示该结点的Node对象中的color变量中。如果指向它的链接是红色的，那么该变量为true，黑色则为false，我们规定空链接都为黑色。如下图所示，指向结点C的链接是红色，那么我们就将h.left.color设置为红色，指向结点J的链接是黑色的，我们就将h.right.color设置为黑色。
红黑树的几种基本操作
红黑树相比普通的二叉查找树的一个重要优势就是插入的高效性，但是正因为如此红黑树的插入操作的算法实现相比普通的二叉树要复杂一些。在正式实现插入算法之前，我们有必要先了解一下对于红黑树的几种基本操作。
左旋转
如下图所示，现在我们有一条红色的右链接，现在我们想要将这条红色右链接转换为左链接，这个操作过程就叫做左旋转：
我们要做的就是在保持红黑树平衡性的同时，将上图的结构变为下面这样：
仔细观察可以发现，我们要实现的其实就是将红色链接关联的两个节点中由较小的节点E作为根节点转换成由较大的节点S作为根节点。同时在这个过程中为了保持二叉树中左子树都要小于根节点，右子树都要大于根节点，所以如果S节点还存在的话左链接我们还需要将它变成E节点的右链接。具体的实现代码如下：
private Node rotateLeft(Node h) {
assert (h != null) && isRed(h.right);
Node x = h.right;
h.right = x.left;
