红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。
红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。
红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。
红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
下面是一个具体的红黑树的图例： 
这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用”nil叶子”或”空（null）叶子”，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。
红黑树的插入操作
红黑树的插入操作和查询操作有些类似，它按照二分搜索的方式递归寻找插入点。不过这里需要考虑边界条件——当树为空时需要特殊处理。如果插入第一个节点，我们直接用树根记录这个节点，并设置为黑色，否则作递归查找插入。
默认插入的节点颜色都是红色，因为插入黑色节点会破坏根路径上的黑色节点总数，但即使如此，也会出现连续红色节点的情况。因此在一般的插入操作之后，出现红黑树约束条件不满足的情况（称为失去平衡）时，就必须要根据当前的红黑树的情况做相应的调整。和AVL树的平衡调整通过旋转操作的实现类似，红黑树的调整操作一般都是通过旋转结合节点的变色操作来完成的。红黑树插入节点操作产生的不平衡来源于当前插入点和父节点的颜色冲突导致的（都是红色，违反规则2）。 
如图所示，由于节点插入之前红黑树是平衡的，因此可以断定祖父节点g必存在（规则1：根节点必须是黑色），且是黑色（规则2：不会有连续的红色节点），而叔父节点u颜色不确定。
节点之间的对应关系：
当前插入节点 node –n
node的父亲节点 parent -p
node的叔叔节点 uncle -u
node的祖父节点 grandParent -g
node的祖父节点的父节点 grandParent-parent -gp
node的祖父节点的祖父节点 grandParent-grandParent -gg
node的祖父节点的叔叔 grandParent-uncle -gu
可以把问题分为两大类：
1、叔父节点是黑色（若是空节点则默认为黑色）
这种情况下通过旋转和变色操作可以使红黑树恢复平衡。但是考虑当前节点n和父节点p的位置又分为四种情况：
A、n是p左子节点，p是g的左子节点。
B、n是p右子节点，p是g的右子节点。
C、n是p左子节点，p是g的右子节点。
D、n是p右子节点，p是g的左子节点。
情况A，B统一称为外侧插入，C，D统一称为内侧插入。之所以这样分类是因为同类的插入方式的解决方式是对称的，可以通过镜像的方法相似完成。
首先考虑情况A：n是p左子节点，p是g的左子节点。针对该情况可以通过一次右旋转操作，并将p设为黑色，g设为红色完成重新平衡。 
右旋操作的步骤是：将p挂接在g节点原来的位置（如果g原是根节点，需要考虑边界条件），将p的右子树x挂到g的左子节点，再把g挂在p的右子节点上，完成右旋操作。这里将最终旋转结果的子树的根节点作为旋转轴（p节点），也就是说旋转轴在旋转结束后称为新子树的根节点。
情况B则需要使用左单旋操作来解决平衡问题，方法和情况A类似。 
情况C：n是p左子节点，p是g的右子节点。针对该情况通过一次左旋，一次右旋操作（旋转轴都是n，注意不是p），并将n设为黑色，g设为红色完成重新平衡。 
需要注意的是，由于此时新插入的节点是n，它的左右子树x，y都是空节点，但即使如此，旋转操作的结果需要将x，y新的位置设置正确（如果不把p和g的对应分支设置为空节点的话，就会破坏树的结构）。在之后的其他操作中，待旋转的节点n的左右子树可能就不是空节点了。
情况D则需要使用一次右单旋，一次左单旋操作来解决平衡问题，方法和情况C类似。 
2、叔父节点是红色
当叔父节点是红色时，则不能直接通过上述方式处理了（把前边的所有情况的u节点看作红色，会发现节点u和g是红色冲突的）。但是我们可以交换g与p，u节点的颜色完成当前冲突的解决。 
但是仅仅这样做颜色交换是不够的，因为祖父节点g的父节点（记作gp）如果也是红色的话仍然会有冲突（g和gp是连续的红色，违反规则2）。为了解决这样的冲突，我们需要从当前插入点n向根节点root回溯两次。
第一次回溯时处理所有拥有两个红色节点的节点，并按照图中的方式交换父节点g与子节点p，u的颜色，并暂时忽略gp和p的颜色冲突。如果根节点的两个子节点也是这种情况，则在颜色交换完毕后重新将根节点设置为黑色。
第二次回溯专门处理连续的红色节点冲突。由于经过第一遍的处理，在新插入点n的路径上一定不存在同为红色的兄弟节点了。而仍出现gp和p的红色冲突时，gp的兄弟节点（gu）可以断定为黑色，这样就回归前边讨论的叔父节点为黑色时的情况处理。 
由于发生冲突的两个红色节点位置可能是任意的，因此会出现上述的四种旋转情况。不过我们把靠近叶子的红色节点（g）看作新插入的节点，这样面对A，B情况则把p的父节点gp作为旋转轴，旋转后gp会是新子树的根，而面对C，D情况时把p作为旋转轴即可，旋转后p为新子树的根（因此可以把四种旋转方式封装起来）。
在第二次回溯时，虽然每次遇到红色冲突旋转后都会提升g和gp节点的位置（与根节点的距离减少），但是无论g和gp谁是新子树的根都不会影响新插入节点n到根节点root路径的回溯，而且一旦新子树的根到达根节点（parent指针为空）就可以停止回溯了。
通过以上的树重新平衡策略可以完美地解决红黑树插入节点的平衡问题。
红黑树的删除操作
相比于插入操作，红黑树的删除操作显得更加复杂。红黑树使用哨兵节点（NIL节点）表示空节点，而这里使用空指针的方式，因此要杜绝空指针的引用问题）。
由于红黑树就是二叉搜索树，因此节点的删除方式和二叉搜索树相同。不过红黑树删除操作的难点不在于节点的删除，而在于删除节点后的调整操作。因此红黑树的删除操作分为两步，首先确定被删除节点的位置，然后调整红黑树的平衡性。
先考虑删除节点的位置，如果待删除节点拥有唯一子节点或没有子节点，则将该节点删除，并将其子节点（或空节点）代替自身的位置。如果待删除节点有两个子节点，则不能将该节点直接删除。而是从其右子树中选取最小值节点（或左子树的最大值节点）作为删除节点（该节点一定没有两个子节点了，否则还能取更小的值）。当然在删除被选取的节点之前，需要将被选取的节点的数据拷贝到原本需要删除的节点中。选定删除节点位置的情况如图所示，这和二叉搜索树的节点删除完全相同。 
图中用红色标记的节点表示被选定的真正删除的节点（节点y）。其中绿色节点（yold）表示原本需要删除的节点，而由于它有两个子节点，因此删除y代替它，并且删除y之前需要将y的值拷贝到yold，注意这里如果是红黑树也不会改变yold的颜色！通过上述的方式，将所有的节点删除问题简化为独立后继（或者无后继）的节点删除问题。然后再考虑删除y后的红黑树平衡调整问题。由于删除y节点后，y的后继节点n会作为y的父节点p的孩子。因此在进行红黑树平衡调整时，n是p的子节点。
下边考虑平衡性调整问题，首先考虑被删除节点y的颜色。如果y为红色，删除y后不会影响红黑树的平衡性，因此不需要做任何调整。如果y为黑色，则y所在的路径上的黑色节点总数减少1，红黑树失去平衡，需要调整。
y为黑色时，再考虑节点n的颜色。如果n为红色，因为n是y的唯一后继，如果把n的颜色设置为黑色，那么就能恢复y之前所在路径的黑色节点的总数，调整完成。如果n也是黑色，则需要按照以下四个步骤来考虑。
设p是n的父节点，w为n节点的兄弟节点。假定n是p的左子节点，n是p的右子节点情况可以镜像对称考虑。
步骤1：若w为红色，则断定w的子节点（如果存在的话或者为空节点）和节点p必是黑色（规则2）。此时将w与p的颜色交换，并以w为旋转轴进行左旋转操作，最后将w设定为n的新兄弟节点（原来w的左子树x）。
通过这样的转换，将原本红色的w节点情况转换为黑色w节点情况。若w原本就是黑色（或者空节点），则直接进入步骤2。 
步骤2：无论步骤1是否得到处理，步骤2处理的总是黑色的w节点，此时再考虑w的两个子节点x，y的颜色情况。如果x，y都是黑色节点（或者是空节点，如果父节点w为空节点，认为x，y也都是空节点），此时将w的颜色设置为红色，并将n设定为n的父节点p。此时，如果n为红色，则直接设定n为黑色，调整结束。否则再次回到步骤1做相似的处理。注意节点n发生变化后需要重新设定节点w和p。
考虑由于之前黑色节点删除导致n的路径上黑色节点数减1，因此可以把节点n看作拥有双重黑色的节点。通过此步骤将n节点上移，使得n与根节点距离减少，更极端的情况是当n成为根节点时，树就能恢复平衡了（因为根节点不在乎多一重黑色）。另外，在n的上移过程中可能通过后续的转换已经让树恢复平衡了。 
步骤3：如果步骤2中的w的子节点不是全黑色，而是左红（x红）右黑（y黑）的话，将x设置为黑色，w设置为红色，并以节点x为旋转轴右旋转，最后将w设定为n的新兄弟（原来的x节点）。
通过这样的转换，让原本w子节点左红右黑的情况转化为左黑右红的情况。若w的右子节点原本就是红色（左子节点颜色可黑可红），则直接进入步骤4。 
步骤4：该步骤处理w右子节点y为红色的情况，此时w的左子节点x可黑可红。这时将w的右子节点y设置为黑色，并交换w与父节点p的颜色（w原为黑色，p颜色可黑可红），再以w为旋转轴左旋转，红黑树调整算法结束。
通过该步骤的转换，可以彻底解决红黑树的平衡问题！该步骤的实质是利用左旋恢复节点n上的黑色节点总数，虽然p和w虽然交换了颜色，但它们都是n的祖先，因此n路径上的黑色节点数增加1。同时由于左旋，使得y路径上的黑色节点数减1，恰巧的是y的颜色为红，将y设置为黑便能恢复y节点路径上黑色节点的总数。 
通过上述的调整策略，可以完美解决红黑树节点删除时平衡性问题。
package com.gloomy.Tree;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
/**
* 平衡二叉树-红黑树 红黑树性质： 1、根节点是黑色 2、节点颜色只能是红色或黑色的 3、红色节点的两个儿子只能是黑色的 4、NIL节点看作是黑色的
* 5、任意节点到子孙的空节点的路径上的黑色节点数目相同
*
* @author 过路的守望
*
*/
public class RedBlackTree {
/*
* NIL节点(无元素)
*/
private RedBlackNode NIL = new RedBlackNode(Color.Black);
/*
* 红黑树的根
*/
private RedBlackNode root = NIL;
/*
* 红黑树节点数目
*/
private int size = 0;
/**
* 构造方法
*
* @param root
*/
public RedBlackTree(RedBlackNode root) {
this.root = root;
}
public RedBlackTree() {
}
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
RedBlackTree redBlackTree = new RedBlackTree();
redBlackTree.insert(6);
redBlackTree.insert(4);
redBlackTree.insert(5);
redBlackTree.insert(7);
redBlackTree.insert(3);
redBlackTree.insert(8);
redBlackTree.remove(6);
redBlackTree.remove(3);
redBlackTree.remove(8);
redBlackTree.remove(7);
redBlackTree.remove(4);
redBlackTree.remove(5);
System.out.println("MAX:" + redBlackTree.findMax());
System.out.println("MIN:" + redBlackTree.findMin());
redBlackTree.preOrder(redBlackTree.root);
redBlackTree.inOrder(redBlackTree.root);
redBlackTree.postOrder(redBlackTree.root);
redBlackTree.levelOrder(redBlackTree.root);
}
/**
* 红黑树中是否含有node节点
*
* @param node
* 递归实现
* @return
*/
public boolean containsRec(RedBlackNode node, RedBlackNode root) {
/*
* 红黑树为空
*/
if (root == NIL) {
return false;
}
/*
* 搜索右子树
*/
if (node.value > root.value) {
return contains(node, root.right);
}
/*
* 搜索左子树
*/
if (node.value < root.value) {
return contains(node, root.left);
}
/*
* 包含node节点
*/
return true;
}
/**
* 红黑树中是否含有node节点
*
* @param node
* @return
*/
public boolean contains(RedBlackNode node, RedBlackNode root) {
/*
* 红黑树为空
*/
if (root == NIL) {
return false;
}
while (node.value != root.value) {
/*
* 搜索右子树
*/
if (node.value > root.value) {
root = root.right;
}
/*
* 搜索左子树
*/
else {
root = root.left;
}
/*
* 未在红黑树中为找到node节点
*/
if (root == NIL) {
return false;
}
}
return true;
}
/**
* 返回红黑树中的最小节点
*
* @param node
* @return
*/
public int findMin() {
RedBlackNode value = findMin(root);
if (value == null) {
return -1;
} else {
return value.value;
}
}
/**
* 在指定红黑树中搜寻最小节点 递归搜索
*
* @param node
* @param root
* @return
*/
private RedBlackNode findMin(RedBlackNode root) {
/*
* 指定红黑树为空树
*/
if (root == NIL) {
return null;
}
/*
* 如果红黑树的左子树非空，则搜索其左子树
*/
if (root.left != NIL) {
return findMin(root.left);
}
return root;
}
/**
* 返回红黑树中的最大节点
*
* @return
*/
public int findMax() {
RedBlackNode value = findMax(root);
if (value == null) {
return -1;
} else {
return value.value;
}
}
/**
* 搜索指定红黑树中的最大节点 递归实现
*
* @param root
* @return
*/
private RedBlackNode findMax(RedBlackNode root) {
/*
* 红黑树为空
*/
if (root == NIL) {
return null;
}
/*
* 搜索右子树
*/
if (root.right != NIL) {
return findMax(root.right);
}
return root;
}
/**
* 得到祖父节点
*
* @param node
* @return
*/
private RedBlackNode getGrandParent(RedBlackNode node) {
/* 父亲节点为空 */
if (node.parent == null) {
return null;
}
return node.parent.parent;
}
/**
* 得到叔父节点
*
* @param node
* @return
*/
private RedBlackNode getUncle(RedBlackNode node) {
RedBlackNode grandParent = getGrandParent(node);
/*
* 祖父节点为空
*/
if (grandParent == null) {
return null;
}
/*
* 父亲节是祖父节点的左儿子
*/
if (node.parent == grandParent.left) {
return grandParent.right;
}
/*
* 父亲节点时祖父节点的右儿子
*/
else {
return grandParent.left;
}
}
/**
* 左旋 RR型 注意更新root、rightChild、rightChild.left的父亲指针指向
*
* @param root
* @return
*/
private RedBlackNode rolateWithRightChild(RedBlackNode root) {
/*
* parent记录root的父亲节点
*/
RedBlackNode parent = root.parent;
/*
* rightChild root节点的右儿子
*/
RedBlackNode rightChild = root.right;
/*
* 如果rightChild的左儿子非空，更新rightChild.left的parent
*/
if (rightChild.left != NIL) {
rightChild.left.parent = root;
}
root.right = rightChild.left;
rightChild.left = root;
/*
* 更新root的parent
*/
root.parent = rightChild;
/*
* root节点为根节点时，根节点改变
*/
if (parent == null) {
this.root = rightChild;
}
/*
* root节点为父亲的右儿子
*/
else if (root == parent.right) {
parent.right = rightChild;
}
/*
* root节点为父亲的左儿子
*/
else {
parent.left = rightChild;
}
/*
* 更新rightChild的parent
*/
rightChild.parent = parent;
return rightChild;
}
/**
* 右旋 LL型
*
* @param root
* @return
*/
private RedBlackNode rolateWithLeftChild(RedBlackNode root) {
/*
* parent记录root的父亲节点
*/
RedBlackNode parent = root.parent;
/*
* leftChild root节点的左儿子
*/
RedBlackNode leftChild = root.left;
root.left = leftChild.right;
/*
* 如果leftChild的右儿子非空，则更新leftChild.right的parent
*/
if (leftChild.right != NIL) {
leftChild.right.parent = root;
}
leftChild.right = root;
/*
* 更新root的parent
*/
root.parent = leftChild;
/*
* 如果root节点之前是根节点，则根节点指向更新
*/
if (parent == null) {
this.root = leftChild;
}
/*
* root节点为父亲的左儿子
*/
else if (root == parent.left) {
parent.left = leftChild;
}
/*
* root节点为父亲的右儿子
*/
else {
parent.right = leftChild;
}
/*
* 更新leftChild的parent
*/
leftChild.parent = parent;
return leftChild;
}
/**
* 双旋转 RL型
*
* @param root
* @return
*/
private RedBlackNode doubleWithRightChild(RedBlackNode root) {
/*
* 先右旋再左旋
*/
rolateWithLeftChild(root.right);
return rolateWithRightChild(root);
}
/**
* 双旋转 LR型
*
* @param root
* @return
*/
private RedBlackNode doubleWithLeftChild(RedBlackNode root) {
/*
* 先左旋再右旋
*/
rolateWithRightChild(root.left);
return rolateWithLeftChild(root);
}
/**
* 插入值为value的节点
*
* @param value
*/
public void insert(int value) {
/*
* 插入节点的左右儿子为NIL,颜色为红色
*/
RedBlackNode node = new RedBlackNode(value, NIL, NIL, Color.Red);
/*
* 如果已经含有此节点
*/
if (contains(node, root)) {
return;
}
insert(node, root);
/*
* 红黑树节点数目增加一个
*/
size++;
}
/**
* 向红黑树中插入节点node
*
* @param node
* @param root
* @return
*/
public void insert(RedBlackNode node, RedBlackNode root) {
/*
* 如果根节点为空，则将插入的节点染成黑色即可
*/
if (this.root == NIL) {
node.color = Color.Black;
this.root = node;
} else {
/*
* 记录插入节点的父亲
*/
RedBlackNode parent = root;
/*
* 找到node节点应该插入的位置
*/
while (node.value != root.value) {
/*
* 更新parent
*/
parent = root;
/*
* 插入到右子树
*/
if (node.value > root.value) {
root = root.right;
/*
* 到达NIl节点,作为右儿子插入
*/
if (root == NIL) {
node.parent = parent;
parent.right = node;
break;
}
}
/* 插入到左子树 */
else {
root = root.left;
/*
* 作为左儿子插入
*/
if (root == NIL) {
node.parent = parent;
parent.left = node;
break;
}
}
}
/*
* 执行插入修复操作
*/
insertFixUp(node);
}
}
/**
* node节点插入后进行修复
*
* @param node
*/
private void insertFixUp(RedBlackNode node) {
/*添加修复操作不会超过2次
* node节点经过前一次处理后上升到根节点，颜色为红色，染成黑色，更新根节点指针
*/
if (node.parent == null) {
node.color = Color.Black;
/*
* 更新root引用
*/
this.root = node;
return;
}
/*
* node节点的父亲颜色是黑色，无需调整
*/
if (node.parent.color == Color.Black) {
return;
}
/*
* 得到node节点的叔父、父亲、祖父节点
*/
RedBlackNode uncle = getUncle(node);
RedBlackNode grandParent = getGrandParent(node);
RedBlackNode parent = node.parent;
/*
* node节点的父节点、叔父节点颜色为红色，祖父节点为黑色 策略：将node节点的父节点、叔父节点颜色染成黑色，祖父节点染成红色。
* 此时祖父节点可能与其父节点颜色冲突，递归解决
*/
if (uncle.color == Color.Red) {
node.parent.color = Color.Black;
uncle.color = Color.Black;
grandParent.color = Color.Red;
/*
* 递归修复grandParent
*/
insertFixUp(grandParent);
}
/*
* LL型 叔父节点是黑色 策略：将父亲节点染成黑色，祖父节点染成红色,右旋转
*/
else if (node == parent.left && parent == grandParent.left) {
parent.color = Color.Black;
grandParent.color = Color.Red;
rolateWithLeftChild(grandParent);
}
/*
* RL型 叔父节点是黑色 策略：node节点染成黑色，祖父节点染成红色，先右旋转再左旋转
*/
else if (node == parent.left && parent == grandParent.right) {
node.color = Color.Black;
grandParent.color = Color.Red;
doubleWithRightChild(grandParent);
}
/*
* RR型 叔父节点黑色策略：将父亲节点染成黑色、祖父节点染成红色，左旋转
*/
else if (node == parent.right && parent == grandParent.right) {
parent.color = Color.Black;
grandParent.color = Color.Red;
rolateWithRightChild(grandParent);
}
/*
* LR型 叔父节点黑色 策略：node节点染成黑色，祖父节点染成红色，先左旋，再右旋
*/
else {
node.color = Color.Black;
grandParent.color = Color.Red;
doubleWithLeftChild(grandParent);
}
}
/**
* 删除值为value的节点
*
* @param val
*/
public void remove(int val) {
RedBlackNode node = new RedBlackNode(val, Color.Red);
remove(node, root);
}
/**
* 删除root中的节点node
*
* @param node
* @param root
* @return
*/
private RedBlackNode remove(RedBlackNode node, RedBlackNode root) {
/*
* 红黑树为空
*/
if (root == NIL) {
return null;
}
/*
* 节点在右子树
*/
if (node.value > root.value) {
root.right = remove(node, root.right);
}
/*
* 节点在左子树
*/
if (node.value < root.value) {
root.left = remove(node, root.left);
}
if (node.value == root.value) {
/*
* 待删除节点的左右子树非空
*/
if (root.left != NIL && root.right != NIL) {
/*
* 用右子树的最小值节点替代待删除的节点
*/
RedBlackNode replace = findMin(root.right);
root.value = replace.value;
/*
* 问题转化为删除右子树中的replace节点
*/
root.right = remove(replace, root.right);
}
/*
* 待删除节点只有左子树或只有右子树或无左右子树
*/
else {
/*
* 被删除节点的父节点
*/
RedBlackNode parent = root.parent;
/*
* 被删除的节点
*/
RedBlackNode deleteNode = root;
/*
* 被删除节点的位置尤其儿子取代
*/
root = (root.left != NIL) ? root.left : root.right;
/*
* 如果被删除节点是根节点,将后继节点染黑后作为新的根节点
*/
if (parent == null) {
deleteNode.left.parent = parent;
deleteNode.right.parent = parent;
root.color = Color.Black;
this.root = root;
} else {
/*
* node节点是作为parent的左儿子还是右儿子
*/
boolean isLeftChild = false;
if (deleteNode == parent.left) {
isLeftChild = true;
}
/*
* 被删除节点的儿子的父亲指向祖父
*/
root.parent = parent;
/*
* 将root接到其祖父
*/
if (isLeftChild) {
parent.left = root;
} else {
parent.right = root;
}
/*
* 修复被删除节点
*/
removeFixUp(root, deleteNode);
/*
* 清除deleteNode的所有引用
*/
deleteNode.parent = null;
deleteNode.left = null;
deleteNode.right = null;
}
}
}
/*
* 将NIL节点的父亲置为null，NIL节点的颜色在修复过程中可能会被染成红色，将其恢复成黑色
*/
NIL.parent = null;
NIL.color = Color.Black;
/*
* 红黑树节点数目减少一个
*/
size--;
return root;
}
/**
* 删除node的父节点后进行修复红黑树性质的操作
* 修复操作旋转次数不会超过3次
* @param node
*/
private void removeFixUp(RedBlackNode node, RedBlackNode deleteNode) {
/*
* 如果被删除节点是根节点，直接将node节点颜色染黑让其作为新的根节点
*/
if (deleteNode.parent == null) {
node.color = Color.Black;
this.root = node;
return;
}
/*
* 如果被删除节点的颜色是红色的，对红黑树的五条性质不造成影响，无需处理
*/
if (deleteNode.color == Color.Red) {
return;
}
/*
* 如果被删除节点的后继节点颜色为红色，将其染成黑色既可
*/
if (node.color == Color.Red) {
node.color = Color.Black;
return;
}
/*
* 如果被删除节点的后继节点颜色为黑色，那么从被删除节点父亲节点到被删除节点NIL节点的路径上将少一个黑色节点
*/
if (node.color == Color.Black) {
/*
* 得到node的叔叔节点，叔叔节点的左儿子、右儿子,祖父
*/
RedBlackNode uncle = getBrother(node);
RedBlackNode uncleLeftChild = uncle.left;
RedBlackNode uncleRightChild = uncle.right;
RedBlackNode grandParent = node.parent;
while (true) {
/*
* node节点现在是其祖父的左儿子
*/
if (node == grandParent.left) {
/*
* 状态-1 如果叔叔节点颜色是红色
* 策略：将祖父节点染成红色，叔叔节点染成染成黑色后左旋，使其装态转化为2或3或4以便进一步调整
*/
if (uncle.color == Color.Red) {
uncle.color = Color.Black;
grandParent.color = Color.Red;
rolateWithRightChild(grandParent);
/*
* 更新node指向
*/
node = grandParent.right;
grandParent = node.parent;
uncle = getBrother(node);
uncleLeftChild = uncle.left;
uncleRightChild = uncle.right;
}
/*
* 状态-2
* 叔叔节点为黑色，其左右儿子也为黑色(此时叔叔节点可能为NIL节点，如果其为NIL节点，其左右儿子将为NULL
* ，要注意空指针判断) 策略：将叔叔节点染成红色，现在祖父是多了一重黑色，向状态1，3，4转化
*/
else if (isBlack(uncleLeftChild)
&& isBlack(uncleRightChild)) {
/*
* 更新叔叔节点颜色
*/
uncle.color = Color.Red;
/*
* 更新node指向
*/
node = grandParent;
grandParent = node.parent;
/*
* node现在指向了根节点
*/
if (grandParent == null) {
node.color = Color.Black;
this.root = node;
break;
}
uncle = getBrother(node);
uncleLeftChild = uncle.left;
uncleRightChild = uncle.right;
/*
* 当前节点是红黑型的节点，将当前节点颜色染成黑色，调整完成
*/
if (grandParent.color == Color.Red) {
grandParent.color = Color.Black;
break;
}
}
/*
* 状态-3 叔叔节点颜色为黑色，其左儿子颜色为红色，右儿子颜色为黑色
* 策略：将叔叔节点的左儿子染成黑色，叔叔节点染成红色，右旋向状态4转化
*/
else if (uncleLeftChild.color == Color.Red
&& uncleRightChild.color == Color.Black) {
uncle.color = Color.Red;
uncleLeftChild.color = Color.Black;
rolateWithLeftChild(uncle);
}
/*
* 状态-4 叔叔节点颜色为黑色，右儿子颜色为红色，左儿子颜色任意
* 策略：将uncle节点颜色与祖父节点颜色互换，叔叔节点右儿子染成黑色，左旋转调整完成。
* 此次操作是祖父的左子树路径增加了一个黑色节点，但叔叔节点右子树少了一个黑色节点，把叔叔节点的右儿子染成黑色弥补
*/
else {
Color temp = uncle.color;
uncle.color = grandParent.color;
grandParent.color = temp;
uncleRightChild.color = Color.Black;
rolateWithRightChild(grandParent);
/*
* 调整完成
*/
break;
}
}
/*
* node节点现在使其祖父的右儿子 镜像对称的四种情形
*/
if (node == grandParent.right) {
/*
* 状态-1 如果叔叔节点颜色是红色
* 策略：将祖父节点染成红色，叔叔节点染成黑色后右旋，使其状态转化为2或3或4以便进一步调整
*/
if (uncle.color == Color.Red) {
uncle.color = Color.Black;
grandParent.color = Color.Red;
rolateWithLeftChild(grandParent);
/*
* 更新node指向
*/
node = grandParent.left;
grandParent = node.parent;
uncle = getBrother(node);
uncleLeftChild = uncle.left;
uncleRightChild = uncle.right;
}
/*
* 状态-2 叔叔节点为黑色，叔叔节点的左右儿子颜色为黑色
* 策略：将叔叔节点染成红色，现在祖父节点多了一重黑色。如果祖父节点自身颜色为红色
* ，将祖父节点染成黑色，调整结束。否则修改node指向使其指向祖父
*/
else if (isBlack(uncleRightChild)
&& isBlack(uncleLeftChild)) {
uncle.color = Color.Red;
/*
* 修改node指向
*/
node = grandParent;
grandParent = node.parent;
/*
* node节点提升到了根节点位置
*/
if (grandParent == null) {
node.color = Color.Black;
this.root = node;
break;
}
uncle = getBrother(node);
uncleLeftChild = uncle.left;
uncleRightChild = uncle.right;
/* 如果祖父节点自身颜色为红色，将祖父节点染成黑色 ，调整完成 */
if (node.color == Color.Red) {
node.color = Color.Black;
break;
}
}
/*
* 状态-3 叔叔节点为黑色，其左儿子为黑色，右儿子为红色
* 策略：将叔叔节点染成红色，右儿子染成黑色，右旋向状态-4转换
*/
else if (uncleLeftChild.color == Color.Black
&& uncleRightChild.color == Color.Red) {
uncle.color = Color.Red;
uncleRightChild.color = Color.Black;
rolateWithRightChild(uncle);
}
/*
* 状态-4 叔叔节点为黑色，左儿子为红色，右儿子颜色任意
* 策略：将叔叔节点的颜色与祖父颜色互换，叔叔节点的左儿子染成黑色，右旋。调整完成。
*/
else {
Color temp = uncle.color;
uncle.color = grandParent.color;
grandParent.color = temp;
uncleLeftChild.color = Color.Black;
rolateWithLeftChild(grandParent);
/*
* 调整完成
*/
break;
}
}
}
}
/* 最后再次把根节点染成黑色（应为node可能上升到根节点 处 */
this.root.color = Color.Black;
}
/**
* node颜色为黑色或是null节点是认为其实黑色
*
* @param node
* @return
*/
private boolean isBlack(RedBlackNode node) {
if (node == null || node.color == Color.Black) {
return true;
}
return false;
}
/**
* 得到node节点兄弟节点
*
* @param node
* @return
*/
private RedBlackNode getBrother(RedBlackNode node) {
/*
* 当前节点是根节点
*/
if (node.parent == null) {
return null;
}
/*
* 兄弟节点是右儿子
*/
if (node == node.parent.left) {
return node.parent.right;
}
/*
* 兄弟节点是左儿子
*/
return node.parent.left;
}
/*
* 获取当前红黑树的节点数目
*/
public int getSize() {
return size;
}
/**
* 非递归先序遍历红黑树
*
* @param root
*/
public void preOrder(RedBlackNode root) {
/*
* 红黑树节点数目为零
*/
if (root == NIL) {
return;
}
System.out.println("先序遍历：");
Stack<RedBlackNode> stack = new Stack<RedBlackNode>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
System.out.print(root.value + " ");
if (root.right != NIL) {
stack.push(root.right);
}
if (root.left != NIL) {
stack.push(root.left);
}
}
System.out.println();
}
/**
* 非递归中序遍历红黑树
*
* @param root
*/
public void inOrder(RedBlackNode root) {
if (root == NIL) {
return;
}
System.out.println("中序遍历：");
Stack<RedBlackNode> stack = new Stack<RedBlackNode>();
while (root != NIL || !stack.isEmpty()) {
while (root != NIL) {
stack.push(root);
root = root.left;
}
root = stack.pop();
System.out.print(root.value + " ");
root = root.right;
}
System.out.println();
}
/**
* 非递归后序遍历红黑树
*
* @param root
*/
public void postOrder(RedBlackNode root) {
if (root == NIL) {
return;
}
System.out.println("后序遍历：");
RedBlackNode pre = NIL;
Stack<RedBlackNode> stack = new Stack<RedBlackNode>();
while (root != NIL || !stack.isEmpty()) {
while (root != NIL) {
stack.push(root);
root = root.left;
}
root = stack.peek();
while (root.right == NIL || root.right == pre) {
System.out.print(root.value + " ");
stack.pop();
pre = root;
if (stack.isEmpty()) {
System.out.println();
return;
}
root = stack.peek();
}
root = root.right;
}
}
/**
* 层序遍历红黑树
*
* @param root
*/
public void levelOrder(RedBlackNode root) {
if (root == NIL) {
return;
}
System.out.println("层序遍历:");
Queue<RedBlackNode> queue = new ArrayDeque<RedBlackNode>();
queue.offer(root);
while (!queue.isEmpty()) {
root = queue.poll();
System.out.print(root.value + "--" + root.color + " ");
if (root.left != NIL) {
queue.offer(root.left);
}
if (root.right != NIL) {
queue.offer(root.right);
}
}
System.out.println();
}
}
/**
* 红黑树节点类
*
* @author 过路的守望
*
*/
class RedBlackNode {
/*
* @value 节点值
*
* @color 节点颜色
*
* @left @right 节点左右儿子
*
* @parent 父节点
*/
int value;
Color color;
RedBlackNode left;
RedBlackNode right;
RedBlackNode parent;
public RedBlackNode(int value, RedBlackNode left, RedBlackNode right,
Color color) {
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
public RedBlackNode(int value, Color color) {
this.value = value;
this.color = color;
}
/*
* 用来构造NIL节点
*/
public RedBlackNode(Color color) {
this.color = color;
}
}
/*
* 枚举类-节点颜色
*/
enum Color {
Black, Red;
}