红黑树的所有搜索操作，包括get() min() max() ceiling() floor() rank() select() 等（参数未列出），均和普通二叉树一样，搜索时无视节点颜色即可。
红黑树主要在于其插入操作，上一篇我们讲了对双节点插入的几种情况（文章链接）我们会发现即使最复杂的情况，插入值在两值中间，也可以转化为基础操作。
下图展示了红黑树插入所有可能的情况：插入值小于左端值，插入值在两值中间，插入值大于右端值。我们可以发现其实所有情况都可以以下列规律化解：
1 如红键在右节点，左旋
2 如红键在左节点，且左节点左子节点也为红键，右旋
3 如左节点和右节点均为红键，变色
插入操作代码如下：
public void put(Key key, Value value) {
root = put(root, key, value);
}
private Node put(Node x, Key key, Value value) {
if (x == null) {
return new Node(key, value, 1, RED);
}
// find the correct position
int cmp = key.compareTo(x.key);
if (cmp > 0) {
x.right = put(x.right, key, value);
} else if (cmp < 0) {
x.left = put(x.left, key, value);
} else {
x.value = value;
}
// rotation and flip color
if (isRed(x.left)) {
x = rotateLeft(x);
}
if (isRed(x.left) && isRed(x.left.left)) {
x = rotateRight(x);
}
if (isRed(x.left) && isRed(x.right)) {
flipColor(x);
}
x.count = size(x.left) + size(x.right) + 1;
return x;
}
前一部分程序和二叉树一样，目的是找到正确插入位置。然后插入后对键进行变换以保证红键永远在左边
红黑树性能分析：
由于不可能连续出现两个红键，且根节点到树底各个路径黑键数相等，红黑树最糟情况高度（所有红键和黑键交替出现），不可能大于最优情况高度（所有键为黑键）的两倍。
因此，红黑树查找及插入操作最糟情况时间复杂度为2logN
对于平均情况，时间复杂度约为logN
最后，给出红黑树目前完整程序（暂时还没有删除操作）
public class RedBlackBSTSymbolTable{ public static final boolean RED = true; public static final boolean BLACK = false; private class Node { private Key key; private Value value; private Node left; private Node right; private int count; private boolean color; private Node(Key key, Value value, int count, boolean color) { this.key = key; this.value = value; this.count = count; this.color = color; } } public Node root; public int size() { return size(root); } private int size(Node x) { if (x == null) { return 0; } else { return x.count; } } // constructor public RedBlackBSTSymbolTable () { root = null; } private boolean isRed(Node x) { return x.color; } private Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.count = h.count; h.count = size(h.left) + size(h.right) + 1; return x; } private Node rotateRight(Node h) { Node x = h.left; x.right = h.left; x.right = h; x.color = h.color; h.color = RED; x.count = h.count; h.count = size(h.left) + size(h.right) + 1; return x; } private void flipColor(Node h) { h.left.color = BLACK; h.right.color = BLACK; h.color = RED; } public void put(Key key, Value value) { root = put(root, key, value); } private Node put(Node x, Key key, Value value) { if (x == null) { return new Node(key, value, 1, RED); } // find the correct position int cmp = key.compareTo(x.key); if (cmp > 0) { x.right = put(x.right, key, value); } else if (cmp < 0) { x.left = put(x.left, key, value); } else { x.value = value; } // rotation and flip color if (isRed(x.left)) { x = rotateLeft(x); } if (isRed(x.left) && isRed(x.left.left)) { x = rotateRight(x); } if (isRed(x.left) && isRed(x.right)) { flipColor(x); } x.count = size(x.left) + size(x.right) + 1; return x; } // The methods below are the same as those in a regular BST // since the searching operations are the same // find a certain value according to its key public Value get(Key key) { Node result = get(key, root); if (result == null) { return null; } return result.value; } private Node get(Key key, Node x) { if (x == null) { // no this key return null; } if (x.key.compareTo(key) > 0) { // smaller, move to the left return get(key, x.left); } else if (x.key.compareTo(key) < 0) { // larger, move to the right return get(key, x.right); } else { return x; // find it } } // find the smallest key public Key min() { return min(root).key; } private Node min(Node x) { if (x.left == null) { return x; } else { return min(x.left); } } // find the largest key public Key max() { return max(root).key; } private Node max(Node x) { if (x.right == null) { return x; } else { return max(x.right); } } // find the largest key less or equals k public Key floor (Key k) { Node x = floor(root, k); if (x == null) { return null; } else { return x.key; } } private Node floor(Node x, Key k) { if (x == null) { return null; } int cmp = k.compareTo(x.key); if (cmp == 0) { // the same key, return it return x; } else if (cmp < 0) { return floor(x.left, k); // smaller, move to the left } else { // larger, attempt to move to the right Node t = floor(x.right, k); if (t != null) { return t; } else { return x; } } } // find the smallest key larger or equals k public Key ceiling (Key k) { Node x = ceiling(root, k); if (x == null ) { return null; } return x.key; } private Node ceiling(Node x, Key k) { if (x == null) { return null; } int cmp = k.compareTo(x.key); if (cmp == 0) { // the exact value return x; } else if (cmp > 0) { return ceiling(x.right, k); // larger, move to the left } else { // smaller, attempt to move to the right Node t = ceiling(x.left, k); if (t != null) { return t; } else { return x; } } } // return the kth smallest key public Key select(int k) { Node x = select(k, root); if (x == null) { return null; } return x.key; } private Node select(int k, Node x) { if (x == null) { return null; } int rank = size(x.left); if (rank == k) { // find the correct index return x; } else if (rank > k) { // move to the left return select(k, x.left); } else { // move to the right return select(k - rank - 1, x.right); } } // find the rank of a given key public int rank(Key key) { return rank(key, root); } private int rank(Key key, Node x) { if (x == null) { return 0; } int cmp = key.compareTo(x.key); if (cmp == 0) { // find the key return size(x.left); } else if (cmp > 0) { // smaller, move to the right return size(x.left) + 1 + rank(key, x.right); } else { // larger, move to the left return rank(key, x.left); } }
