正文
在实现红黑树之前我们先来定义一棵红黑树：
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设置为黑色。
红黑树的几种基本操作
红黑树相比普通的二叉查找树的一个重要优势就是插入的高效性，但是正因为如此红黑树的插入操作的算法实现相比普通的二叉树要复杂一些。在正式实现插入算法之前，我们有必要先了解一下对于红黑树的几种基本操作。
左旋转
