R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
注意：
特性3中的叶子节点，是只为空(NIL或null)的节点。特性5，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。红黑树示意图如下：
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
AVL树是一棵严格的平衡树，它所有的子树都满足二叉平衡树的定义。因此AVL树高被严格控制在XXX，因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。
红黑树用非严格的平衡来降低插入删除时旋转的次数。
因此，如果你的业务中查找远远多于插入、删除，那选AVL树； 如果查找、插入、删除频率差不多，那么选择红黑树。
红黑树本质上还是一颗二叉查找树，所以，对红黑树的插入删除操作都可以分为两阶段来完成，首先，将红黑树看成一颗普通的二叉查找树完成插入删除操作，然后，通过旋转以及颜色调整来使得操作后的树满足红黑树的所有特性即可。
红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。旋转包括两种：左旋 和 右旋。
对x点进行右旋：
对y点进行左旋：
区分 左旋 和 右旋
它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。
左旋示例图(以x为节点进行左旋)：
z x / / \ --(左旋)--> x y z / y对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。 因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
右旋示例图(以x为节点进行右旋)：
y x \ / \ --(右旋)--> x y z \ z对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
默认插入的结点为红色。为何？
因为红黑树中黑节点至少是红节点的两倍，因此插入节点的父节点为黑色的概率较大，而此时并不需要作任何调整，因此效率较高。
1. 父为黑
插入后无需任何操作。由于黑节点个数至少为红节点的两倍，因此父为黑的情况较多，而这种情况在插入后无需任何调整，这就是红黑树比AVL树插入效率高的原因！
2. 父为红
父为红的情况破坏了红黑树的性质，此时需要根据叔叔的颜色来做不同的处理。
1.红叔（叔叔为红）
红叔的情况，其实相对来说比较简单的，如下图所示，只需要通过修改父、叔的颜色为黑色，祖的颜色为红色，而且回去递归的检查祖节点即可。（此时若爷爷节点和太爷爷节点颜色相同，再以爷爷节点为起始节点，进行刚才相同的操作，即：根据爷爷的兄弟颜色做相应的操作。）
2.黑叔
黑叔的情况有如下4种，这几种情况下是不能够通过修改颜色达到平衡的效果，因此会通过旋转的操作，红黑树种有两种旋转操作，左旋和右旋(现在存在的疑问，什么时候使用到左旋，什么时候使用到右旋)
Case 1:爸爸在左、叔叔在右、我在左
[先右旋，再改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)]。
Case 2:爸爸在左、叔叔在右、我在右
[先左旋变成Case1中的情况，再右旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)]。
Case 3:叔叔在左、爸爸在右、我在右
[先左旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)]。
Case 4:叔叔在左、爸爸在右、我在左
[先右旋变成Case 3的情况，再左旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)]。
删除操作相比于插入操作情况更加复杂，删除一个节点可以大致分为三种情况：
1.删除的节点没有孩子节点，即当前节点为叶子节点，这种可以直接删除
2.删除的节点有一个孩子节点，这种需要删除当前节点，并使用其孩子节点顶替上来
3.删除的节点有两个孩子节点，这种需要先找到其后继节点(树中大于节点的最小的元素);然后将其后继节点的内容复制到该节点上，其后继节点就相当于该节点的替身， 需要注意的是其后继节点一定不会有两个孩子节点(这点应该很好理解，如果后继节点有左孩子节点，那么当前的后继节点肯定不是最小的，说明后继节点只能存在没有孩子节点或者只有一个右孩子节点)，即这样就将问题转换成为1,2中的方式。
在讲述修复操作之前，首先需要明白几点，
1.对于红黑树而言，单支节点的情况只有如下图所示的一种情况，即为当前节点为黑色，其孩子节点为红色,(1.假设当前节点为红色，其两个孩子节点必须为黑色，2.若有孙子节点，则必为黑色，导致黑子数量不等，而红黑树不平衡)
2.由于红黑树是特殊的二叉查找树，它的删除和二叉查找树类型，真正的删除点即为删除点A的中序遍历的后继(前继也可以)，通过红黑树的特性可知这个后继必然最多只能有一个孩子，其这个孩子节点必然是右孩子节点，从而为单支情况(即这个后继节点只能有一个红色孩子或没有孩子)
下面将详细介绍，在执行删除节点操作之后，将通过修复操作使得红黑树达到平衡的情况。
Case 1:被删除的节点为红色，则这节点必定为叶子节点(首先这里的被删除的节点指的是真正删除的节点，通过上文得知的真正删除的节点要么是节点本身，要么是其后继节点，若是节点本身则必须为叶子节点，不为叶子节点的话其会有左右孩子，则真正删除的是其右孩子树上的最小值，若是后继节点，也必须为叶子节点，若不是则其也会有左右孩子，从而和2中相违背)，这种情况下删除红色叶节点就可以了，不用进行其他的操作了。 Case 2:被删除的节点是黑色，其子节点是红色，将其子节点顶替上来并改变其颜色为黑色，如下图所示。 Case 3:被删除的节点是黑色，其子节点也是黑色，将其子节点顶替上来，变成了双黑的问题，此时有以下情况。 Case 3.1:新节点的兄弟节点为红色，此时若新节点在左边则做左旋操作，否则做右旋操作，之后再将其父节点颜色改变为红色，兄弟节点从图中可以看出，操作之后红黑树并未达到平衡状态，而是变成的黑兄的情况
Case 3.2:新节点的兄弟节点为黑色,此时可能有如下情况。 红父二黑侄：将父节点变成黑色，兄弟节点变成红色，新节点变成黑色即可,如下图所示 黑父二黑侄：将父节点变成新节点的颜色，新节点变成黑色，兄弟节点染成红色，还需要继续以父节点为判定点继续判断,如下图所示。 红侄情况一:新节点在右子树，红侄在兄弟节点左子树，此时的操作为右旋，并将兄弟节点变为父亲的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示。
情况二:新节点在右子树，红侄在兄弟节点右子树，此时的操作为先左旋，后右旋并将侄节点变为父亲的颜色，父节点变为黑色，如下图所示。
情况三：新节点在左子树，红侄在兄弟节点左子树,此时的操作为先右旋在左旋并将侄节点变为父亲的颜色，父亲节点变为黑色，如下图所示。
情况四：新节点在右子树，红侄在兄弟节点右子树,此时的操作为左旋，并将兄弟节点变为父节点的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示
如下是使用JAVA代码实现红黑树的过程，主要包括了插入、删除、左旋、右旋、遍历等操作。
1.插入节点
/* 插入一个节点 * @param node */ private void insert(RBTreeNode<T> node){ int cmp; RBTreeNode<T> root = this.rootNode; RBTreeNode<T> parent = null; //定位节点添加到哪个父节点下 while(null != root){ parent = root; cmp = node.key.compareTo(root.key); if (cmp < 0){ root = root.left; } else { root = root.right; } } node.parent = parent; //表示当前没一个节点，那么就当新增的节点为根节点 if (null == parent){ this.rootNode = node; } else { //找出在当前父节点下新增节点的位置 cmp = node.key.compareTo(parent.key); if (cmp < 0){ parent.left = node; } else { parent.right = node; } } //设置插入节点的颜色为红色 node.color = COLOR_RED; //修正为红黑树 insertFixUp(node); } /** * 红黑树插入修正 * @param node */ private void insertFixUp(RBTreeNode<T> node){ RBTreeNode<T> parent,gparent; //节点的父节点存在并且为红色 while( ((parent = getParent(node)) != null) && isRed(parent)){ gparent = getParent(parent); //如果其祖父节点是空怎么处理 // 若父节点是祖父节点的左孩子 if(parent == gparent.left){ RBTreeNode<T> uncle = gparent.right; if ((null != uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node = gparent; continue; } if (parent.right == node){ RBTreeNode<T> tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } setColorBlack(parent); setColorRed(gparent); rightRotate(gparent); } else { RBTreeNode<T> uncle = gparent.left; if ((null != uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node = gparent; continue; } if (parent.left == node){ RBTreeNode<T> tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } setColorBlack(parent); setColorRed(gparent); leftRotate(gparent); } } setColorBlack(this.rootNode); }插入节点的操作主要分为以下几步：
1.定位：即遍历整理红黑树，确定添加的位置，如上代码中insert方法中就是在找到添加的位置
2.修复：这也就是前面介绍的，添加元素后可能会使得红黑树不在满足其特性，这时候需要通过变色、旋转来调整红黑树，也就是如上代码中insertFixUp方法
2.删除节点
private void remove(RBTreeNode<T> node){ RBTreeNode<T> child,parent; boolean color; //被删除节点左右孩子都不为空的情况 if ((null != node.left) && (null != node.right)){ //获取到被删除节点的后继节点 RBTreeNode<T> replace = node; replace = replace.right; while(null != replace.left){ replace = replace.left; } //node节点不是根节点 if (null != getParent(node)){ //node是左节点 if (getParent(node).left == node){ getParent(node).left = replace; } else { getParent(node).right = replace; } } else { this.rootNode = replace; } child = replace.right; parent = getParent(replace); color = getColor(replace); if (parent == node){ parent = replace; } else { if (null != child){ setParent(child,parent); } parent.left = child; replace.right = node.right; setParent(node.right, replace); } replace.parent = node.parent; replace.color = node.color; replace.left = node.left; node.left.parent = replace; if (color == COLOR_BLACK){ removeFixUp(child,parent); } node = null; return; } if (null != node.left){ child = node.left; } else { child = node.right; } parent = node.parent; color = node.color; if (null != child){ child.parent = parent; } if (null != parent){ if (parent.left == node){ parent.left = child; } else { parent.right = child; } } else { this.rootNode = child; } if (color == COLOR_BLACK){ removeFixUp(child, parent); } node = null; } /** * 删除修复 * @param node * @param parent */ private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){ RBTreeNode<T> other; //node不为空且为黑色，并且不为根节点 while ((null == node || isBlack(node)) && (node != this.rootNode) ){ //node是父节点的左孩子 if (node == parent.left){ //获取到其右孩子 other = parent.right; //node节点的兄弟节点是红色 if (isRed(other)){ setColorBlack(other); setColorRed(parent); leftRotate(parent); other = parent.right; } //node节点的兄弟节点是黑色，且兄弟节点的两个孩子节点也是黑色 if ((other.left == null || isBlack(other.left)) && (other.right == null || isBlack(other.right))){ setColorRed(other); node = parent; parent = getParent(node); } else { //node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色 if (null == other.right || isBlack(other.right)){ setColorBlack(other.left); setColorRed(other); rightRotate(other); other = parent.right; } //node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色，左孩子是任意颜色 setColor(other, getColor(parent)); setColorBlack(parent); setColorBlack(other.right); leftRotate(parent); node = this.rootNode; break; } } else { other = parent.left; if (isRed(other)){ setColorBlack(other); setColorRed(parent); rightRotate(parent); other = parent.left; } if ((null == other.left || isBlack(other.left)) && (null == other.right || isBlack(other.right))){ setColorRed(other); node = parent; parent = getParent(node); } else { if (null == other.left || isBlack(other.left)){ setColorBlack(other.right); setColorRed(other); leftRotate(other); other = parent.left; } setColor(other,getColor(parent)); setColorBlack(parent); setColorBlack(other.left); rightRotate(parent); node = this.rootNode; break; } } } if (node!=null) setColorBlack(node); }删除节点主要分为几种情况去做对应的处理：
1.删除节点,按照如下三种情况去删除节点 1.真正删除的节点没有子节点2.真正删除的节点有一个子节点3.正在删除的节点有两个子节点2.修复红黑树的特性，如代码中调用removeFixUp方法修复红黑树的特性。