红黑树的所有搜索操作，包括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 positionint 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 colorif (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;}}// constructorpublic 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 positionint 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 colorif (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 keypublic 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 keyreturn null;}if (x.key.compareTo(key) > 0) {// smaller, move to the leftreturn get(key, x.left);} else if (x.key.compareTo(key) < 0) {// larger, move to the rightreturn get(key, x.right);} else {return x;// find it}}// find the smallest keypublic 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 keypublic 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 kpublic 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 itreturn x;} else if (cmp < 0) {return floor(x.left, k);// smaller, move to the left} else {// larger, attempt to move to the rightNode t = floor(x.right, k);if (t != null) {return t;} else {return x;}}}// find the smallest key larger or equals kpublic 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 valuereturn x;} else if (cmp > 0) {return ceiling(x.right, k);// larger, move to the left} else {// smaller, attempt to move to the rightNode t = ceiling(x.left, k);if (t != null) {return t;} else {return x;}}}// return the kth smallest keypublic 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 indexreturn x;} else if (rank > k) { // move to the leftreturn select(k, x.left);} else {// move to the rightreturn select(k - rank - 1, x.right);}}// find the rank of a given keypublic 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 keyreturn size(x.left);} else if (cmp > 0) {// smaller, move to the rightreturn size(x.left) + 1 + rank(key, x.right);} else {// larger, move to the leftreturn rank(key, x.left);}}