红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它具有以下特性： 1. 每个节点要么是红色，要么是黑色。 2. 根节点是黑色的。 3. 每个叶子节点（NIL节点）是黑色的。 4. 如果一个节点是红色的，则它的子节点必须是黑色的（反之不一定成立）。 5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。 

        红黑树简单实现;

java">public class RedBlackTree {private static final boolean RED = true;private static final boolean BLACK = false;private Node root;private class Node {int key;String value;Node left, right;boolean color;public Node(int key, String value, boolean color) {this.key = key;this.value = value;this.color = color;}}private boolean isRed(Node node) {if (node == null) {return false;}return node.color == RED;}// 左旋抓private Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;return x;}// 右旋转private Node rotateRight(Node h) {Node x = h.left;h.left = x.right;x.right = h;x.color = h.color;h.color = RED;return x;}// 转换颜色private void flipColors(Node h) {h.color = RED;h.left.color = BLACK;h.right.color = BLACK;}// 插入操作public void put(int key, String value) {root = put(root, key, value);root.color = BLACK;}private Node put(Node h, int key, String value) {if (h == null) {return new Node(key, value, RED);}if (key < h.key) {h.left = put(h.left, key, value);} else if (key > h.key) {h.right = put(h.right, key, value);} else {h.value = value;}// 红黑树平衡操作if (isRed(h.right) && !isRed(h.left)) {h = rotateLeft(h);}if (isRed(h.left) && isRed(h.left.left)) {h = rotateRight(h);}if (isRed(h.left) && isRed(h.right)) {flipColors(h);}return h;}// 对外暴露的查询方法public String get(int key) {return get(root, key);}// 递归查询操作private String get(Node x, int key) {if (x == null) {return null;}if (key < x.key) {return get(x.left, key);} else if (key > x.key) {return get(x.right, key);} else {return x.value;}}// 删除操作public void delete(int key) {if (root == null) {return;}if (!isRed(root.left) && !isRed(root.right)){root.color = RED;}root = delete(root, key);if (root != null) {root.color = BLACK;}}private Node delete(Node h, int key) {if (h == null) {return null;}if (key < h.key) {if (!isRed(h.left) && !isRed(h.left.left)) {h = moveRedLeft(h);}h.left = delete(h.left, key);} else {if (isRed(h.left)) {h = rotateRight(h);}if (key == h.key && (h.right == null)) {return h.left; // Corrected to delete the node directly}if (!isRed(h.right) && !isRed(h.right.left)) {h = moveRedRight(h);}if (key == h.key) {Node x = min(h.right);h.key = x.key;h.value = x.value;h.right = deleteMin(h.right);} else {h.right = delete(h.right, key);}}return balance(h);}private Node moveRedLeft(Node h) {flipColors(h);if (isRed(h.right.left)) {h.right = rotateRight(h.right);h = rotateLeft(h);flipColors(h);}return h;}private Node moveRedRight(Node h) {flipColors(h);if (isRed(h.left.left)) {h = rotateRight(h);flipColors(h);}return h;}private Node deleteMin(Node h) {if (h.left == null) {return null;}if (!isRed(h.left) && !isRed(h.left.left)) {h = moveRedLeft(h);}h.left = deleteMin(h.left);return balance(h);}private Node min(Node x) {while (x.left != null) {x = x.left;}return x;}private Node balance(Node h) {if (isRed(h.right)) {h = rotateLeft(h);}if (isRed(h.left) && isRed(h.left.left)) {h = rotateRight(h);}if (isRed(h.left) && isRed(h.right)) {flipColors(h);}return h;}
}

         红黑树实战实现：

java">public class RBTreeNode<T extends Comparable<T>> {private T value;//node valueprivate RBTreeNode<T> left;//left child pointerprivate RBTreeNode<T> right;//right child pointerprivate RBTreeNode<T> parent;//parent pointerprivate boolean red;//color is red or not redpublic RBTreeNode(){}public RBTreeNode(T value){this.value=value;}public RBTreeNode(T value,boolean isRed){this.value=value;this.red = isRed;}public T getValue() {return value;}void setValue(T value) {this.value = value;}RBTreeNode<T> getLeft() {return left;}void setLeft(RBTreeNode<T> left) {this.left = left;}RBTreeNode<T> getRight() {return right;}void setRight(RBTreeNode<T> right) {this.right = right;}RBTreeNode<T> getParent() {return parent;}void setParent(RBTreeNode<T> parent) {this.parent = parent;}boolean isRed() {return red;}boolean isBlack(){return !red;}/*** is leaf node**/boolean isLeaf(){return left==null && right==null;}void setRed(boolean red) {this.red = red;}void makeRed(){red=true;}void makeBlack(){red=false;}@Overridepublic String toString(){return value.toString();}
}public class RBTree<T extends Comparable<T>> {private final RBTreeNode<T> root;//node numberprivate java.util.concurrent.atomic.AtomicLong size = new java.util.concurrent.atomic.AtomicLong(0);//in overwrite mode,all node's value can not  has same	value//in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode.private volatile boolean overrideMode=true;public RBTree(){this.root = new RBTreeNode<T>();}public RBTree(boolean overrideMode){this();this.overrideMode=overrideMode;}public boolean isOverrideMode() {return overrideMode;}public void setOverrideMode(boolean overrideMode) {this.overrideMode = overrideMode;}/*** number of tree number* @return*/public long getSize() {return size.get();}/*** get the root node* @return*/private RBTreeNode<T> getRoot(){return root.getLeft();}/*** add value to a new node,if this value exist in this tree,* if value exist,it will return the exist value.otherwise return null* if override mode is true,if value exist in the tree,* it will override the old value in the tree* * @param value* @return*/public T addNode(T value){RBTreeNode<T> t = new RBTreeNode<T>(value);return addNode(t);}/*** find the value by give value(include key,key used for search,* other field is not used,@see compare method).if this value not exist return null* @param value* @return*/public T find(T value){RBTreeNode<T> dataRoot = getRoot();while(dataRoot!=null){int cmp = dataRoot.getValue().compareTo(value);if(cmp<0){dataRoot = dataRoot.getRight();}else if(cmp>0){dataRoot = dataRoot.getLeft();}else{return dataRoot.getValue();}}return null;}/*** remove the node by give value,if this value not exists in tree return null* @param value include search key* @return the value contain in the removed node*/public T remove(T value){RBTreeNode<T> dataRoot = getRoot();RBTreeNode<T> parent = root;while(dataRoot!=null){int cmp = dataRoot.getValue().compareTo(value);if(cmp<0){parent = dataRoot;dataRoot = dataRoot.getRight();}else if(cmp>0){parent = dataRoot;dataRoot = dataRoot.getLeft();}else{if(dataRoot.getRight()!=null){RBTreeNode<T> min = removeMin(dataRoot.getRight());//x used for fix color balanceRBTreeNode<T> x = min.getRight()==null ? min.getParent() : min.getRight();boolean isParent = min.getRight()==null;min.setLeft(dataRoot.getLeft());setParent(dataRoot.getLeft(),min);if(parent.getLeft()==dataRoot){parent.setLeft(min);}else{parent.setRight(min);}setParent(min,parent);boolean curMinIsBlack = min.isBlack();//inherit dataRoot's colormin.setRed(dataRoot.isRed());if(min!=dataRoot.getRight()){min.setRight(dataRoot.getRight());setParent(dataRoot.getRight(),min);}//remove a black node,need fix colorif(curMinIsBlack){if(min!=dataRoot.getRight()){fixRemove(x,isParent);}else if(min.getRight()!=null){fixRemove(min.getRight(),false);}else{fixRemove(min,true);}}}else{setParent(dataRoot.getLeft(),parent);if(parent.getLeft()==dataRoot){parent.setLeft(dataRoot.getLeft());}else{parent.setRight(dataRoot.getLeft());}//current node is black and tree is not emptyif(dataRoot.isBlack() && !(root.getLeft()==null)){RBTreeNode<T> x = dataRoot.getLeft()==null ? parent :dataRoot.getLeft();boolean isParent = dataRoot.getLeft()==null;fixRemove(x,isParent);}}setParent(dataRoot,null);dataRoot.setLeft(null);dataRoot.setRight(null);if(getRoot()!=null){getRoot().setRed(false);getRoot().setParent(null);}size.decrementAndGet();return dataRoot.getValue();}}return null;}/*** fix remove action* @param node* @param isParent*/private void fixRemove(RBTreeNode<T> node,boolean isParent){RBTreeNode<T> cur = isParent ? null : node;boolean isRed = isParent ? false : node.isRed();RBTreeNode<T> parent = isParent ? node : node.getParent();while(!isRed && !isRoot(cur)){RBTreeNode<T> sibling = getSibling(cur,parent);//sibling is not null,due to before remove tree color is balance//if cur is a left nodeboolean isLeft = parent.getRight()==sibling;if(sibling.isRed() && !isLeft){//case 1//cur in rightparent.makeRed();sibling.makeBlack();rotateRight(parent);}else if(sibling.isRed() && isLeft){//cur in leftparent.makeRed();sibling.makeBlack();rotateLeft(parent);}else if(isBlack(sibling.getLeft()) && isBlack(sibling.getRight())){//case 2sibling.makeRed();cur = parent;isRed = cur.isRed();parent=parent.getParent();}else if(isLeft && !isBlack(sibling.getLeft()) && isBlack(sibling.getRight())){//case 3sibling.makeRed();sibling.getLeft().makeBlack();rotateRight(sibling);}else if(!isLeft && !isBlack(sibling.getRight()) && isBlack(sibling.getLeft()) ){sibling.makeRed();sibling.getRight().makeBlack();rotateLeft(sibling);}else if(isLeft && !isBlack(sibling.getRight())){//case 4sibling.setRed(parent.isRed());parent.makeBlack();sibling.getRight().makeBlack();rotateLeft(parent);cur=getRoot();}else if(!isLeft && !isBlack(sibling.getLeft())){sibling.setRed(parent.isRed());parent.makeBlack();sibling.getLeft().makeBlack();rotateRight(parent);cur=getRoot();}}if(isRed){cur.makeBlack();}if(getRoot()!=null){getRoot().setRed(false);getRoot().setParent(null);}}//get sibling nodeprivate RBTreeNode<T> getSibling(RBTreeNode<T> node,RBTreeNode<T> parent){parent = node==null ? parent : node.getParent();if(node==null){return parent.getLeft()==null ? parent.getRight() : parent.getLeft();}if(node==parent.getLeft()){return parent.getRight();}else{return parent.getLeft();}}private boolean isBlack(RBTreeNode<T> node){return node==null || node.isBlack();}private boolean isRoot(RBTreeNode<T> node){return root.getLeft() == node && node.getParent()==null;}/*** find the successor node* @param node current node's right node* @return*/private RBTreeNode<T> removeMin(RBTreeNode<T> node){//find the min nodeRBTreeNode<T> parent = node;while(node!=null && node.getLeft()!=null){parent = node;node = node.getLeft();}//remove min nodeif(parent==node){return node;}parent.setLeft(node.getRight());setParent(node.getRight(),parent);//don't remove right pointer,it is used for fixed color balance//node.setRight(null);return node;}private T addNode(RBTreeNode<T> node){node.setLeft(null);node.setRight(null);node.setRed(true);setParent(node,null);if(root.getLeft()==null){root.setLeft(node);//root node is blacknode.setRed(false);size.incrementAndGet();}else{RBTreeNode<T> x = findParentNode(node);int cmp = x.getValue().compareTo(node.getValue());if(this.overrideMode && cmp==0){T v = x.getValue();x.setValue(node.getValue());return v;}else if(cmp==0){//value exists,ignore this nodereturn x.getValue();}setParent(node,x);if(cmp>0){x.setLeft(node);}else{x.setRight(node);}fixInsert(node);size.incrementAndGet();}return null;}/*** find the parent node to hold node x,if parent value equals x.value return parent.* @param x* @return*/private RBTreeNode<T> findParentNode(RBTreeNode<T> x){RBTreeNode<T> dataRoot = getRoot();RBTreeNode<T> child = dataRoot;while(child!=null){int cmp = child.getValue().compareTo(x.getValue());if(cmp==0){return child;}if(cmp>0){dataRoot = child;child = child.getLeft();}else if(cmp<0){dataRoot = child;child = child.getRight();}}return dataRoot;}/*** red black tree insert fix.* @param x*/private void fixInsert(RBTreeNode<T> x){RBTreeNode<T> parent = x.getParent();while(parent!=null && parent.isRed()){RBTreeNode<T> uncle = getUncle(x);if(uncle==null){//need to rotateRBTreeNode<T> ancestor = parent.getParent();//ancestor is not null due to before before add,tree color is balanceif(parent == ancestor.getLeft()){boolean isRight = x == parent.getRight();if(isRight){rotateLeft(parent);}rotateRight(ancestor);if(isRight){x.setRed(false);parent=null;//end loop}else{parent.setRed(false);}ancestor.setRed(true);}else{boolean isLeft = x == parent.getLeft();if(isLeft){rotateRight(parent);}rotateLeft(ancestor);if(isLeft){x.setRed(false);parent=null;//end loop}else{parent.setRed(false);}ancestor.setRed(true);}}else{//uncle is redparent.setRed(false);uncle.setRed(false);parent.getParent().setRed(true);x=parent.getParent();parent = x.getParent();}}getRoot().makeBlack();getRoot().setParent(null);}/*** get uncle node* @param node* @return*/private RBTreeNode<T> getUncle(RBTreeNode<T> node){RBTreeNode<T> parent = node.getParent();RBTreeNode<T> ancestor = parent.getParent();if(ancestor==null){return null;}if(parent == ancestor.getLeft()){return ancestor.getRight();}else{return ancestor.getLeft();}}private void rotateLeft(RBTreeNode<T> node){RBTreeNode<T> right = node.getRight();if(right==null){throw new java.lang.IllegalStateException("right node is null");}RBTreeNode<T> parent = node.getParent();node.setRight(right.getLeft());setParent(right.getLeft(),node);right.setLeft(node);setParent(node,right);if(parent==null){//node pointer to root//right  raise to root noderoot.setLeft(right);setParent(right,null);}else{if(parent.getLeft()==node){parent.setLeft(right);}else{parent.setRight(right);}//right.setParent(parent);setParent(right,parent);}}private void rotateRight(RBTreeNode<T> node){RBTreeNode<T> left = node.getLeft();if(left==null){throw new java.lang.IllegalStateException("left node is null");}RBTreeNode<T> parent = node.getParent();node.setLeft(left.getRight());setParent(left.getRight(),node);left.setRight(node);setParent(node,left);if(parent==null){root.setLeft(left);setParent(left,null);}else{if(parent.getLeft()==node){parent.setLeft(left);}else{parent.setRight(left);}setParent(left,parent);}}private void setParent(RBTreeNode<T> node,RBTreeNode<T> parent){if(node!=null){node.setParent(parent);if(parent==root){node.setParent(null);}}}/*** debug method,it used print the given node and its children nodes,* every layer output in one line* @param root*/public void printTree(RBTreeNode<T> root){java.util.LinkedList<RBTreeNode<T>> queue =new java.util.LinkedList<RBTreeNode<T>>();java.util.LinkedList<RBTreeNode<T>> queue2 =new java.util.LinkedList<RBTreeNode<T>>();if(root==null){return ;}queue.add(root);boolean firstQueue = true;while(!queue.isEmpty() || !queue2.isEmpty()){java.util.LinkedList<RBTreeNode<T>> q = firstQueue ? queue : queue2;RBTreeNode<T> n = q.poll();if(n!=null){String pos = n.getParent()==null ? "" : ( n == n.getParent().getLeft() ? " LE" : " RI");String pstr = n.getParent()==null ? "" : n.getParent().toString();String cstr = n.isRed()?"R":"B";cstr = n.getParent()==null ? cstr : cstr+" ";System.out.print(n+"("+(cstr)+pstr+(pos)+")"+"\t");if(n.getLeft()!=null){(firstQueue ? queue2 : queue).add(n.getLeft());}if(n.getRight()!=null){(firstQueue ? queue2 : queue).add(n.getRight());}}else{System.out.println();firstQueue = !firstQueue;}}}public static void main(String[] args) {RBTree<String> bst = new RBTree<String>();bst.addNode("d");bst.addNode("d");bst.addNode("c");bst.addNode("c");bst.addNode("b");bst.addNode("f");bst.addNode("a");bst.addNode("e");bst.addNode("g");bst.addNode("h");bst.remove("c");bst.printTree(bst.getRoot());}
}