写这篇文章之前，本来是打算写HashMap的源码分析，但是jdk1.8之后的HashMap对位桶+链表的结构进行了优化，即链表长度大于8之后链表就会转成红黑树，所以这里先把红黑树的原理分析下。
链表的增删改查的平均时间复杂度是O(n)，红黑树的增删改查的平均时间复杂度是O(log2n)，n > log2n，所以红黑树的效率更高。
大学里的《数据结构》介绍了各种树的结构，这里总结下。介绍的东西比较多，如果只关心红黑树的话，可以选择性阅读。
自由树：一个连通的，无回路的无向图；
令G=(V，E)为一个无向图。下面的表述是等价的。
- G是自由树。
- G中任意两个顶点由唯一一条简单路径得到。
- G是连通的，但从E中去掉任何边后得到的图都是非连通的。
- G是无回路的，且|E|=|V|-1。
- G是连通的，且|E|=|V|-1。
- G是无回路的，但添加任何边到E中得到的图包含回路。
二叉树：每个结点最多有两个子树的树结构；
- 二叉树的第i层至多有
个结点；
- 深度为n的二叉树至多有
个结点；（等比数列
）。
- 对任何一棵二叉树T，如果其终端结点数(又称叶子节点)为n0，度为2的结点数为n2，则n0 = n2 + 1。
这条性质怎么证明呢？可以直观地这样解释：构造二叉树的过程就是从原始结点开始“生长”结点的过程,初始状态下,原始结点就是终端结点,n0=1,n1=0,n2=0,每当一个原来的终端结点变成“1度结点”的时候只是把终端的位置向下移动了一点,n1++,不影响n0和n2,而每当一个原来的终端结点变成“2度结点”的时候,原来的终端消失,增加两个终端,总效果就是n0++,n2++,所以二叉树当中的n0和n2总是同步增加,即总是满足n0 = n2 + 1。
严格的数学证明也是有的：假设二叉树有N 个节点，那么它会有多少条边呢？答案是N - 1，这是因为除了根节点，其余的每个节点都有且只有一个父节点，那么这N 个节点恰好为树贡献了N - 1 条边。这是从下往上的思考，而从上往下(从树根到叶节点)的思考，容易得到每个节点的度数和 0 * n0 + 1 * n1 + 2 * n2 即为边的个数。因此，我们有等式 N - 1 = n1 + 2 * n2，把N 用n0 + n1 + n2 替换，得到n0 + n1 + n2 - 1 = n1 + 2 * n2，于是有 n0 = n2 + 1。命题得证
满二叉树：一棵深度为n，且有2n-1个节点的树是满二叉树，或者说除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。比如下图是满二叉树的标准图形：
满二叉树
满二叉树满足二叉树的所有性质，还有自己独特的性质，比图树高h和节点数N的关系：，这条公式可以从二叉树的第二条性质推倒出来(深度为h的二叉树至多有
个结点即
)。
完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为h的，有N个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树中编号从1至N的结点一一对应时称之为完全二叉树。换一种说法：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。
- 深度为h的完全二叉树的节点数N满足，2h-1<=N<=2h-1
- 树高h=log2N + 1。
完全二叉树
二叉排序树(二叉搜索树)：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树
堆(大顶堆、小顶堆)：堆和二叉排序树是有区别的，堆首先是一种完全二叉树，其次满足下面的性质：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，即：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ；
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆，即：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 。
关于堆，具体内容可以看下堆排序。
平衡二叉搜索树(AVL)：平衡二叉树或为空树,或为如下性质的二叉排序树:
- 左右子树深度之差的绝对值不超过1;
- 左右子树仍然为平衡二叉树.
哈弗曼树：它是最优二叉树，定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。以{5,6,7,8,15}为例，来构造一棵哈夫曼树。参考文献。
构造哈弗曼树
红黑树：红黑树是基于二叉搜索树实现的(只是比二叉搜索树多了修正操作)。AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树引用。
红黑树上每个结点内含五个域，color(颜色)，key(值)，left(左孩子)，right(右孩子)，p(父节点)。如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
- 每个结点要么是红的，要么是黑的。
- 根结点是黑的。
- 每个叶结点，即空结点（NIL）是黑的[注意：这里叶子节点，是指为空(NIL)的叶子节点！]。
- 如果一个结点是红的，那么它的俩个儿子都是黑的。
- 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
红黑树
还有各种B+、B-、B*树，就不分析了。
2 红黑树平衡性的修正
在红黑树中插入的节点都是红色的，因为插入一个红色节点比插入一个黑色节点破坏红黑特性的可能性更小。原因是：插入黑色节点总会改变黑色高度（违背规则5），但是插入红色节点只有一半的机会会违背规则4。另外违背规则4比违背规则5要更容易修正。
在对红黑树进行插入、删除的操作的时候会破坏红黑树结构，为了保持红黑树的特质，需要对红黑树进行修正，怎么修正呢？红黑树提供了三种修正的方法：变色、左旋、右旋。
2.1变色
变色
如上图所示，图a中只有一个根节点20，根据性质2，它的颜色是黑色的；图b插入节点11,节点11是红色的，作为20的左子节点，依然没有破坏红黑树的性质；图c插入节点22，新插入的节点仍然是红色的，图c依然是红黑树；图d中插入新的红节点10，如果不变色，那么不满足性质4，所以把红节点11变色为黑色，同时需要把红节点22变色为黑色，因为要满足性质5。下面章节3.1中会给出需要修正红黑树的三种情况，这个变色属于第一种情况，稍等再讨论。
2.2右旋
右旋
在图d中继续插入节点5变成图e，11节点导致树不平衡，需要对11节点进行旋转操作，因为左子树高，那么就右旋，变成图f，f还要进行变色变成图g，这个操作是后面内容讨论3.1章节中的修正的三种情况的第2种情况，稍等会讨论到。右旋有一个动图很形象：
右旋
动图对S节点进行右旋，S变成了原来左孩子的右孩子
2.3左旋
左旋和右旋是相对的概念，原理类似。理解了右旋也就理解了左旋。
左旋
上面动图对E节点进行左旋，E变成了原来右孩子的左孩子。
2.4左旋和右旋区分
上面的动态图出自这个文章。
右旋和左旋
仔细观察上面"左旋"和"右旋"的示意图。我们能发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，旋转之后仍然是二叉查找树，这也是我们进行左右旋操作的原因。
可以总结一句话：如果一个节点的左右子树导致不平衡，需要对它进行左旋或者右旋(左子树高就右旋，右子树高就左旋)，左旋使它变成左孩子，右旋使它变成右孩子。但是具体什么时候左旋什么时候右旋，对哪个节点进行旋转，后面章节的3.1插入和3.2删除会具体分析。
3 红黑树的操作
红黑树的操作包括查找、插入和删除，插入和删除可能会破坏红黑树的性质，那么就需要用变色、左旋、右旋进行修正。下面的内容参考自【数据结构和算法05】 红-黑树（看完包懂~），作者写的非常好，我对部分内容进行了修改，原文的删除红黑树节点的代码（方法remove(RBNode<T> node)）有bug，我已经修复。先来定义节点类RBNode：
public class RBNode<T extends Comparable<T>> {
public int color; //颜色 0-red 1=black
public T key; //关键字(键值)
public RBNode<T> left; //左子节点
public RBNode<T> right; //右子节点
public RBNode<T> parent; //父节点
public RBNode(T key, int color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString() {
return key + " " + (this.color == RED ? "RED" : "BLACK");
}
}
左旋的实现：
/*
* 左旋示意图：对节点x进行左旋
* p p
* / /
* x y
* / \ / \
* lx y -----> x ry
* / \ / \
* ly ry lx ly
* 左旋做了三件事：
* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
* 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
* 3. 将y的左子节点设为x，将x的父节点设为y
*/
private void leftRotate(RBNode<T> x) {
//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode<T> y = x.right;
x.right = y.left;
if (y.left != null)
y.left.parent = x;
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
y.parent = x.parent;
if (x.parent == null) {
this.root = y; //如果x的父节点为空，则将y设为父节点
} else {
if (x == x.parent.left) //如果x是左子节点
x.parent.left = y; //则也将y设为左子节点
else
x.parent.right = y;//否则将y设为右子节点
}
//3. 将y的左子节点设为x，将x的父节点设为y
y.left = x;
x.parent = y;
}
右旋的实现：
/*
* 左旋示意图：对节点y进行右旋
* p p
* / /
* y x
* / \ / \
* x ry -----> lx y
* / \ / \
* lx rx rx ry
* 右旋做了三件事：
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y，将y的父节点设为x
*/
private void rightRotate(RBNode<T> y) {
//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode<T> x = y.left;
y.left = x.right;
if (x.right != null)
x.right.parent = y;
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
x.parent = y.parent;
if (y.parent == null) {
this.root = x; //如果x的父节点为空，则将y设为父节点
} else {
if (y == y.parent.right) //如果x是左子节点
y.parent.right = x; //则也将y设为左子节点
else
y.parent.left = x;//否则将y设为右子节点
}
//3. 将y的左子节点设为x，将x的父节点设为y
x.right = y;
y.parent = x;
}
3.1插入操作
由于红黑树是基于二叉排序树的，所以插入也是基于二叉排序树的，即：从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到末端，就是插入点。
/*********************** 向红黑树中插入节点 **********************/
public void insert(T key) {
RBNode<T> node = new RBNode<T>(key, RED, null, null, null);
insert(node);
}
//将节点插入到红黑树中，这个过程与二叉搜索树是一样的
private void insert(RBNode<T> node) {
RBNode<T> current = null; //表示最后node的父节点
RBNode<T> x = this.root; //用来向下搜索用的
//1. 找到插入的位置
while (x != null) {
current = x;
int cmp = node.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = current; //找到了位置，将当前current作为node的父节点
//2. 接下来判断node是插在左子节点还是右子节点
if (current != null) {
int cmp = node.key.compareTo(current.key);
if (cmp < 0)
current.left = node;
else
current.right = node;
} else {
this.root = node;
}
//3. 将它重新修整为一颗红黑树
insertFixUp(node);
}
红黑树的插入比二叉排序树的插入多一个步骤是insertFixUp，这个函数是进行树的修正操作。
如果是第一次插入，原树为空，只会违反红黑树的规则2，所以只要把插入的根节点改成黑色即可；如果插入节点的父节点是黑色的，那不会违背红黑树的规则，什么也不需要做；但是下面三种情况，需要进行变色和旋转(和普通树不一样，红黑树存在nil节点且都是黑色)：
- 插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的；
- 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点；
- 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点。
上面这三种情况中，如果叔叔节点是nil，那么是黑色，这是红黑树的性质3决定的。
上面这三种情况中假设父节点是左孩子，如果父节点是右孩子，那么情况1的操作是一样的，情况2和情况3反一下就行了，我们只讨论父节点是左孩子的情况。
上面三种情况处理问题的核心思路都是：将红色的节点移到根节点，然后，将根节点设为黑色。下面进行详细分析。
对于情况1，这个情况比较简单，只需要变色就行了，上面2.1章节的图c到图d的过程就是情况1，当然图c到图d的过程比较简单因为就树的高度比较低，如果树的高度很高的话，需要循环操作了：将当前节点的父节点和叔叔节点涂黑，将祖父节点涂红，再将当前节点指向其祖父节点，再次从新的当前节点开始算法。
对于情况2，上面2.2章节的图e到图g的修正情况就是情况2，有2.2章节我们很清晰地知道，具体操作是把父节点变黑，祖父节点变红，再对祖父节点右旋，共这三步。
对于情况3，这个情况比较复杂点，首先需要把这种情况改造成情况2的结构，然后根据情况2的算法进行操作就行了，怎么转换成情况2的结构呢？其实把当前节点的父节点进行一次左旋操作就好了。如下图：
图i就是情况2了，那么就根据情况2的算法进行操作。
插入红黑树的情况讨论完了，下面贴出修正的算法insertFixUp的代码：
private void insertFixUp(RBNode<T> node) {
RBNode<T> parent, gparent; //定义父节点和祖父节点
//需要修整的条件：父节点存在，且父节点的颜色是红色
while (((parent = parentOf(node)) != null) && isRed(parent)) {
gparent = parentOf(parent);//获得祖父节点
//若父节点是祖父节点的左子节点，下面else与其相反
if (parent == gparent.left) {
RBNode<T> uncle = gparent.right; //获得叔叔节点
//case1: 叔叔节点也是红色
if (uncle != null && isRed(uncle)) {
setBlack(parent); //把父节点和叔叔节点涂黑
setBlack(uncle);
setRed(gparent); //把祖父节点涂红
node = gparent; //将位置放到祖父节点处
continue; //继续while，重新判断
}
//case3: 叔叔节点是黑色，且当前节点是右子节点，if操作转换成情况2
if (node == parent.right) {
leftRotate(parent); //从父节点处左旋
RBNode<T> tmp = parent; //然后将父节点和自己调换一下，为下面右旋做准备
parent = node;
node = tmp;
}
//case2: 叔叔节点是黑色，且当前节点是左子节点
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若父节点是祖父节点的右子节点,与上面的完全相反，本质一样的
RBNode<T> uncle = gparent.left;
//case1: 叔叔节点也是红色
if (uncle != null & isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(gparent);
node = gparent;
continue;
}
//case2: 叔叔节点是黑色的，且当前节点是左子节点，if操作转换成情况3mk
if (node == parent.left) {
rightRotate(parent);
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
//case3: 叔叔节点是黑色的，且当前节点是右子节点
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
//将根节点设置为黑色
setBlack(this.root);
}
3.2删除操作
删除某一个节点需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和变色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：
第一步：将红黑树当作一颗二叉查找树，将节点删除。
这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
① 被删除节点没有儿子，即为叶节点。这种情况有点复杂，如果被删除节点的颜色是红色的话，那么，直接将该节点删除就OK了，如果是黑色的要分情况讨论。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置，这种情况很简单。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子而且存在的唯一的儿子一定是右子树。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。
第一步逻辑很清晰，代码如下：
/*********************** 删除红黑树中的节点 **********************/
public void remove(T key) {
RBNode<T> node;
if ((node = search(root, key)) != null) {
System.out.println("要删除的节点找到了：" + node.toString());
remove(node);
}
}
private void remove(RBNode<T> node) {
RBNode<T> child, parent;
int color;
//1. 被删除的节点“左右子节点都不为空”的情况
if ((node.left != null) && (node.right != null)) {
//先找到被删除节点的后继节点，用它来取代被删除节点的位置
RBNode<T> replace = node;
// 1). 获取后继节点
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// 2). 处理“后继节点”和“被删除节点的父节点”之间的关系
if (parentOf(node) != null) { //要删除的节点不是根节点
if (node == parentOf(node).left)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else { //否则
this.root = replace;
}
// 3). 处理“后继节点的子节点”和“被删除节点的子节点”之间的关系
child = replace.right; //后继节点肯定不存在左子节点！
parent = parentOf(replace);
color = colorOf(replace);//保存后继节点的颜色
if (parent == node) { //后继节点是被删除节点的子节点
parent = replace;
} else { //否则
if (child != null)
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 == BLACK) { //4. 如果移走的后继节点颜色是黑色，重新修整红黑树
removeFixUp(child, parent);//将后继节点的child和parent传进去
}
node = null;
} else {//这种情况是最对一个子节点不为null，前两种情况
child = node.left == null ? node.right : node.left;
if (child != null) {
child.parent = node.parent;
}
if (node.parent != null) {
boolean isLeft = node.key.compareTo(node.parent.key) < 0;
if (isLeft) {
node.parent.left = child;
} else {
node.parent.right = child;
}
}
if (node.parent == null) {
this.root = child;
}
node = null;
}
}
第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。要删除节点y，先找到y的后继节点x，x与y互调，再把x的颜色变成y的颜色(可能是红色也可能是黑色)，删除y节点。然后只有一种情况会破坏红黑性质，那就是x原来的颜色是黑色，因为少了一个黑色，这样这会破坏性质5，这一种情况下需要调用方法removeFixUp进行修正。
由于少了一个黑色，我们可以假设x包含一个额外的黑色，现在，x不仅包含它替换后的颜色属性，x还包含一个额外的黑色。即x的颜色属性是"红+黑"或"黑+黑"，它违反了"特性(1)"。引文
由于x原来的位置被删除，其实我们需要的修正只是针对x原来的右子树node(原来的x肯定没有左子树)和x原来的父节点parent。直接贴代码吧，比较难解释：
private void removeFixUp(RBNode<T> node, RBNode<T> parent) {
RBNode<T> other;
while ((node == null || isBlack(node)) && (node != this.root)) {
if (parent.left == node) { //node是左子节点，下面else与这里的刚好相反
other = parent.right; //node的兄弟节点
if (isRed(other)) { //case1: node的兄弟节点other是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
//case2: node的兄弟节点other是黑色的，且other的两个子节点也都是黑色的
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
setRed(other);
node = parent;
parent = parentOf(node);
} else {
//case3: node的兄弟节点other是黑色的，且other的左子节点是红色，右子节点是黑色
if (other.right == null || isBlack(other.right)) {
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
//case4: node的兄弟节点other是黑色的，且other的右子节点是红色，左子节点任意颜色
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.root;
break;
}
} else { //与上面的对称
other = parent.left;
if (isRed(other)) {
// Case 1: node的兄弟other是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
// Case 2: node的兄弟other是黑色，且other的俩个子节点都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left == null || isBlack(other.left)) {
// Case 3: node的兄弟other是黑色的，并且other的左子节点是红色，右子节点为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: node的兄弟other是黑色的；并且other的左子节点是红色的，右子节点任意颜色
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.root;
break;
}
}
}
if (node != null)
setBlack(node);
}
下面分析下，分析参考文章。
情况②比较简单，先把这个软柿子干掉。
根据性质5，可以推断出的是，待删除结点必定是黑色（红色结点不可能只有一个孩子），且唯一的子树一定是一个红色孩子。所以这种情况可以在删除时就处理掉，用红色孩子顶替待删除结点，再将其涂成黑色。
情况①，分两种情况：
同样先捏软柿子：
删除deleted结点之后，经过一系列变换：
，那么可以先转换成黑兄的情况。
parent左旋一下，然后parent和brother交换颜色，之后brother指向最下面那个结点。这样一来，就变成了上面的黑兄情况。
3.3 完整代码和测试代码
插入和删除分析完了，那么给出完成的全部代码：
class RBTree<T extends Comparable<T>> {
private RBNode<T> root; //根节点
private static final int RED = 0;
private static final int BLACK = 1;
public RBNode<T> parentOf(RBNode<T> node) { //获得父节点
return node != null ? node.parent : null;
}
public void setParent(RBNode<T> node, RBNode<T> parent) { //设置父节点
if (node != null)
node.parent = parent;
}
public boolean isRed(RBNode<T> node) { //判断节点的颜色
return (node != null) && (node.color == RED) ? true : false;
}
public boolean isBlack(RBNode<T> node) {
return !isRed(node);
}
public void setRed(RBNode<T> node) { //设置节点的颜色
if (node != null)
node.color = RED;
}
public void setBlack(RBNode<T> node) {
if (node != null)
node.color = BLACK;
}
public int colorOf(RBNode<T> node) { //获得节点的颜色
return node != null ? node.color : BLACK;
}
public void setColor(RBNode<T> node, int color) {
if (node != null)
node.color = color;
}
/***************** 前序遍历红黑树 *********************/
public void preOrder() {
preOrder(root);
}
private void preOrder(RBNode<T> tree) {
if (tree != null) {
System.out.print(tree.key + " ");
preOrder(tree.left);
preOrder(tree.right);
}
}
/***************** 中序遍历红黑树 *********************/
public void inOrder() {
inOrder(root);
}
private void inOrder(RBNode<T> tree) {
if (tree != null) {
preOrder(tree.left);
System.out.print(tree.key + " ");
preOrder(tree.right);
}
}
/***************** 后序遍历红黑树 *********************/
public void postOrder() {
postOrder(root);
}
private void postOrder(RBNode<T> tree) {
if (tree != null) {
preOrder(tree.left);
preOrder(tree.right);
System.out.print(tree.key + " ");
}
}
/**************** 查找红黑树中键值为key的节点 ***************/
public RBNode<T> search(T key) {
return search(root, key);
// return search2(root, key); //使用递归的方法，本质一样的
}
private RBNode<T> search(RBNode<T> x, T key) {
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
//使用递归
private RBNode<T> search2(RBNode<T> x, T key) {
if (x == null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search2(x.left, key);
else if (cmp > 0)
return search2(x.right, key);
else
return x;
}
/**************** 查找最小节点的值 **********************/
public T minValue() {
RBNode<T> node = minNode(root);
if (node != null)
return node.key;
return null;
}
private RBNode<T> minNode(RBNode<T> tree) {
if (tree == null)
return null;
while (tree.left != null) {
tree = tree.left;
}
return tree;
}
/******************** 查找最大节点的值 *******************/
public T maxValue() {
RBNode<T> node = maxNode(root);
if (node != null)
return node.key;
return null;
}
private RBNode<T> maxNode(RBNode<T> tree) {
if (tree == null)
return null;
while (tree.right != null)
tree = tree.right;
return tree;
}
/********* 查找节点x的后继节点,即大于节点x的最小节点 ***********/
public RBNode<T> successor(RBNode<T> x) {
//如果x有右子节点，那么后继节点为“以右子节点为根的子树的最小节点”
if (x.right != null)
return minNode(x.right);
//如果x没有右子节点，会出现以下两种情况：
//1. x是其父节点的左子节点，则x的后继节点为它的父节点
//2. x是其父节点的右子节点，则先查找x的父节点p，然后对p再次进行这两个条件的判断
RBNode<T> p = x.parent;
while ((p != null) && (x == p.right)) { //对应情况2
x = p;
p = x.parent;
}
return p; //对应情况1
}
/********* 查找节点x的前驱节点，即小于节点x的最大节点 ************/
public RBNode<T> predecessor(RBNode<T> x) {
//如果x有左子节点，那么前驱结点为“左子节点为根的子树的最大节点”
if (x.left != null)
return maxNode(x.left);
//如果x没有左子节点，会出现以下两种情况：
//1. x是其父节点的右子节点，则x的前驱节点是它的父节点
//2. x是其父节点的左子节点，则先查找x的父节点p，然后对p再次进行这两个条件的判断
RBNode<T> p = x.parent;
while ((p != null) && (x == p.left)) { //对应情况2
x = p;
p = x.parent;
}
return p; //对应情况1
}
/*************对红黑树节点x进行左旋操作 ******************/
/*
* 左旋示意图：对节点x进行左旋
* p p
* / /
* x y
* / \ / \
* lx y -----> x ry
* / \ / \
* ly ry lx ly
* 左旋做了三件事：
* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
* 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
* 3. 将y的左子节点设为x，将x的父节点设为y
*/
private void leftRotate(RBNode<T> x) {
//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode<T> y = x.right;
x.right = y.left;
if (y.left != null)
y.left.parent = x;
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
y.parent = x.parent;
if (x.parent == null) {
this.root = y; //如果x的父节点为空，则将y设为父节点
} else {
if (x == x.parent.left) //如果x是左子节点
x.parent.left = y; //则也将y设为左子节点
else
x.parent.right = y;//否则将y设为右子节点
}
//3. 将y的左子节点设为x，将x的父节点设为y
y.left = x;
x.parent = y;
}
/*************对红黑树节点y进行右旋操作 ******************/
/*
* 左旋示意图：对节点y进行右旋
* p p
* / /
* y x
* / \ / \
* x ry -----> lx y
* / \ / \
* lx rx rx ry
* 右旋做了三件事：
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y，将y的父节点设为x
*/
private void rightRotate(RBNode<T> y) {
//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode<T> x = y.left;
y.left = x.right;
if (x.right != null)
x.right.parent = y;
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
x.parent = y.parent;
if (y.parent == null) {
this.root = x; //如果x的父节点为空，则将y设为父节点
} else {
if (y == y.parent.right) //如果x是左子节点
y.parent.right = x; //则也将y设为左子节点
else
y.parent.left = x;//否则将y设为右子节点
}
//3. 将y的左子节点设为x，将x的父节点设为y
x.right = y;
y.parent = x;
}
/*********************** 向红黑树中插入节点 **********************/
public void insert(T key) {
RBNode<T> node = new RBNode<T>(key, RED, null, null, null);
insert(node);
}
//将节点插入到红黑树中，这个过程与二叉搜索树是一样的
private void insert(RBNode<T> node) {
RBNode<T> current = null; //表示最后node的父节点
RBNode<T> x = this.root; //用来向下搜索用的
//1. 找到插入的位置
while (x != null) {
current = x;
int cmp = node.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = current; //找到了位置，将当前current作为node的父节点
//2. 接下来判断node是插在左子节点还是右子节点
if (current != null) {
int cmp = node.key.compareTo(current.key);
if (cmp < 0)
current.left = node;
else
current.right = node;
} else {
this.root = node;
}
//3. 将它重新修整为一颗红黑树
insertFixUp(node);
}
private void insertFixUp(RBNode<T> node) {
RBNode<T> parent, gparent; //定义父节点和祖父节点
//需要修整的条件：父节点存在，且父节点的颜色是红色
while (((parent = parentOf(node)) != null) && isRed(parent)) {
gparent = parentOf(parent);//获得祖父节点
//若父节点是祖父节点的左子节点，下面else与其相反
if (parent == gparent.left) {
RBNode<T> uncle = gparent.right; //获得叔叔节点
//case1: 叔叔节点也是红色
if (uncle != null && isRed(uncle)) {
setBlack(parent); //把父节点和叔叔节点涂黑
setBlack(uncle);
setRed(gparent); //把祖父节点涂红
node = gparent; //将位置放到祖父节点处
continue; //继续while，重新判断
}
//case3: 叔叔节点是黑色，且当前节点是右子节点，if操作转换成情况2
if (node == parent.right) {
leftRotate(parent); //从父节点处左旋
RBNode<T> tmp = parent; //然后将父节点和自己调换一下，为下面右旋做准备
parent = node;
node = tmp;
}
//case2: 叔叔节点是黑色，且当前节点是左子节点
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若父节点是祖父节点的右子节点,与上面的完全相反，本质一样的
RBNode<T> uncle = gparent.left;
//case1: 叔叔节点也是红色
if (uncle != null & isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(gparent);
node = gparent;
continue;
}
//case2: 叔叔节点是黑色的，且当前节点是左子节点，if操作转换成情况3mk
if (node == parent.left) {
rightRotate(parent);
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
//case3: 叔叔节点是黑色的，且当前节点是右子节点
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
//将根节点设置为黑色
setBlack(this.root);
}
/*********************** 删除红黑树中的节点 **********************/
public void remove(T key) {
RBNode<T> node;
if ((node = search(root, key)) != null) {
System.out.println("要删除的节点找到了：" + node.toString());
remove(node);
}
}
private void remove(RBNode<T> node) {
RBNode<T> child, parent;
int color;
//1. 被删除的节点“左右子节点都不为空”的情况
if ((node.left != null) && (node.right != null)) {
//先找到被删除节点的后继节点，用它来取代被删除节点的位置
RBNode<T> replace = node;
// 1). 获取后继节点
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// 2). 处理“后继节点”和“被删除节点的父节点”之间的关系
if (parentOf(node) != null) { //要删除的节点不是根节点
if (node == parentOf(node).left)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else { //否则
this.root = replace;
}
// 3). 处理“后继节点的子节点”和“被删除节点的子节点”之间的关系
child = replace.right; //后继节点肯定不存在左子节点！
parent = parentOf(replace);
color = colorOf(replace);//保存后继节点的颜色
if (parent == node) { //后继节点是被删除节点的子节点
parent = replace;
} else { //否则
if (child != null)
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 == BLACK) { //4. 如果移走的后继节点颜色是黑色，重新修整红黑树
removeFixUp(child, parent);//将后继节点的child和parent传进去
}
node = null;
} else {//这种情况是最对一个子节点不为null，前两种情况
child = node.left == null ? node.right : node.left;
if (child != null) {
child.parent = node.parent;
}
if (node.parent != null) {
boolean isLeft = node.key.compareTo(node.parent.key) < 0;
if (isLeft) {
node.parent.left = child;
} else {
node.parent.right = child;
}
}
if (node.parent == null) {
this.root = child;
}
node = null;
}
}
private void removeFixUp(RBNode<T> node, RBNode<T> parent) {
RBNode<T> other;
while ((node == null || isBlack(node)) && (node != this.root)) {
if (parent.left == node) { //node是左子节点，下面else与这里的刚好相反
other = parent.right; //node的兄弟节点
if (isRed(other)) { //case1: node的兄弟节点other是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
//case2: node的兄弟节点other是黑色的，且other的两个子节点也都是黑色的
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
setRed(other);
node = parent;
parent = parentOf(node);
} else {
//case3: node的兄弟节点other是黑色的，且other的左子节点是红色，右子节点是黑色
if (other.right == null || isBlack(other.right)) {
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
//case4: node的兄弟节点other是黑色的，且other的右子节点是红色，左子节点任意颜色
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.root;
break;
}
} else { //与上面的对称
other = parent.left;
if (isRed(other)) {
// Case 1: node的兄弟other是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
// Case 2: node的兄弟other是黑色，且other的俩个子节点都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left == null || isBlack(other.left)) {
// Case 3: node的兄弟other是黑色的，并且other的左子节点是红色，右子节点为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: node的兄弟other是黑色的；并且other的左子节点是红色的，右子节点任意颜色
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.root;
break;
}
}
}
if (node != null)
setBlack(node);
}
/****************** 销毁红黑树 *********************/
public void clear() {
destroy(root);
root = null;
}
private void destroy(RBNode<T> tree) {
if (tree == null)
return;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree = null;
}
/******************* 打印红黑树 *********************/
public void print() {
if (root != null) {
print(root, root.key, 0);
}
}
/*
* key---节点的键值
* direction--- 0:表示该节点是根节点
* -1:表示该节点是它的父节点的左子节点
* 1:表示该节点是它的父节点的右子节点
*/
private void print(RBNode<T> tree, T key, int direction) {
if (tree != null) {
if (0 == direction)
System.out.printf("%2d(B) is root\n", tree.key);
else
System.out.printf("%2d(%s) is %2d's %6s child\n",
tree.key, isRed(tree) ? "R" : "B", key, direction == 1 ? "right" : "left");
print(tree.left, tree.key, -1);
print(tree.right, tree.key, 1);
}
}
class RBNode<T extends Comparable<T>> {
public int color; //颜色 0-red 1=black
public T key; //关键字(键值)
public RBNode<T> left; //左子节点
public RBNode<T> right; //右子节点
public RBNode<T> parent; //父节点
public RBNode(T key, int color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString() {
return key + " " + (this.color == RED ? "RED" : "BLACK");
}
}
}
测试代码：
public class Test {
private static final int a[] = {20, 11, 22, 10, 5, 21, 30, 24};//{10, 40, 30, 60, 90, 70, 20, 50, 80};
private static final boolean mDebugInsert = true; // "插入"动作的检测开关(false，关闭；true，打开)
private static final boolean mDebugDelete = true; // "删除"动作的检测开关(false，关闭；true，打开)
public static void main(String args[]) {
int i, ilen = a.length;
RBTree<Integer> tree = new RBTree<Integer>();
System.out.printf("== 原始数据: ");
for (i = 0; i < ilen; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
for (i = 0; i < ilen; i++) {
tree.insert(a[i]);
// 设置mDebugInsert=true,测试"添加函数"
if (mDebugInsert) {
System.out.printf("== 添加节点: %d\n", a[i]);
System.out.printf("== 树的详细信息: \n");
tree.print();
System.out.printf("\n");
}
}
System.out.printf("== 前序遍历: ");
tree.preOrder();
System.out.printf("\n== 中序遍历: ");
tree.inOrder();
System.out.printf("\n== 后序遍历: ");
tree.postOrder();
System.out.printf("\n");
System.out.printf("== 最小值: %s\n", tree.minValue());
System.out.printf("== 最大值: %s\n", tree.maxValue());
System.out.printf("== 树的详细信息: \n");
tree.print();
System.out.printf("\n");
// 设置mDebugDelete=true,测试"删除函数"
if (mDebugDelete) {
for (i = 0; i < ilen; i++) {
tree.remove(a[i]);
System.out.printf("== 树的详细信息: \n");
tree.print();
System.out.printf("\n");
}
}
}
}
3.4 遇到的小问题
我的windows系统，源码中有中文注释，javac编译源码的时候出现了错误: 编码gbk的不可映射字符
Windows下为GBK编码，javac编译utf-8编码的java文件时，容易出现“错误: 编码GBK的不可映射字符”
解决方法是添加encoding 参数：javac -encoding utf-8 Test.java
Linux下为UTF-8编码，javac编译gbk编码的java文件时，容易出现“错误: 编码UTF8的不可映射字符”
解决方法是添加encoding 参数：javac -encoding gbk Test.java
如果还不能解决，将其保存成ANSI编码
首先记事本打开java源文件。然后另存为，选择ANSI编码。
参考文献
