题目一：实现一个红黑树类，要求具备红黑树的基本性质，而且有插入和删除方法。
红黑树是一种二叉排序树或者说是查找树。它在每个节点上增加了一个域表示该节点的颜色，节点只有两种颜色Red或Black，因此被称为红黑树。红黑树必须具备如下性质：（1）每个节点要么是红的，要么是黑的。（2）根节点是黑的。（3）所有叶节点都是黑色（红黑树引入了NULL节点来作为其叶节点，需要注意的是一般在画图时都会忽略这些NULL节点）。（4）如果一个节点是红的，那么它的俩个儿子都是黑的。（5）对于任一节点而言，它到它的任意一个叶结点的每一条路径都包含相同数目的黑结点。
红黑树的作用：调整平衡二叉树。
平衡二叉树（AVL）是一种具有很好的性能的排序二叉树。平衡二叉树特点：（1）非叶子节点最多拥有两个子节点；（2）非叶子节值大于左边子节点、小于右边子节点；（3）树的左右两边的层级数相差不会大于1;（4）没有值相等重复的节点;
红黑树的插入步骤：
插入可以分两步来完成：第一步将新的红色节点插入，第二步分析判断属于哪一种情形，并进行调整处理。调整需要分以下情形来分别处理：
1.新节点不存在父节点。这种情形处理很简单，只要将新节点的颜色修改为黑色即可，该节点实际上就是红黑树的根节点。
2.新节点的父节点的颜色为黑色。如果父节点的颜色为黑色，则无需做任何调整。
3.新节点的父节点和叔父节点均为红色。
调整的方法是：1.将其父节点P和叔父节点U的颜色变为黑色，2.新节点N颜色不变，3.其祖父节点G(randpa)（节点50）颜色改为红色。调整后的结果如下图所示：
此时插入并没有完成，由于新节点的祖父节点的颜色改变了，因而我们还需要判断这个改变是否会违背红黑树的限制，如果会就需要根据具体的情形继续进行调整，这个过程要一直递归的进行直到确保红黑树的限制都被满足。（此时假设G就是根节点，则它满足情形一，即不存在父节点的情形，直接将其颜色修改为黑色即可）。简单的说就是如果某个节点的颜色在调整过程中被变成了红色，就要将它看做新节点，来进行分析判断并进行调整处理。
[if !supportLists]4. [endif]新节点的父节点是红色，叔父节点是黑色或不存在，新节点是其父节点的左孩子，父节点是祖父节点的左孩子。
调整的方法是：首选对以新节点的祖父节点G为根的子树进行一次右旋，可以得到：
然后再将节点P和G的颜色互换，得到：
显然N,P,G,U的颜色已经满足红黑树的要求，再考察这个调整对路径上黑节点数目的影响：
调整前，节点N到根节点的路径上需要经过黑节点G，调整之后需要经过黑节点P，黑节点数目不变。
调整前，节点P到根节点的路径上需要经过黑节点G，调整之后需要经过黑节点P，黑节点数目不变。
调整前，节点G到根节点的路径上需要经过黑节点G，调整之后需要经过黑节点P，黑节点数目不变。
调整前，节点U到根节点的路径上需要经过黑节点U,G，调整之后需要经过黑节点U,P，黑节点数目不变。
因而完成这两步调整后，插入即可结束
5.新节点的父节点是红色，叔父节点是黑色或不存在，并且新节点是其父节点的右孩子，父节点是祖父节点的左孩子。
调整的方法是：首先对以新节点的父节点P为根的子树进行一次左旋，可以得到：
调整后得到的情形和情形4相同，按照情形进行处理即可（即做一次右旋，然后交换颜色），也就是说在这种情形下需要先做一次左旋，再做一次右旋。 情形4和情形5讨论的是父节点是祖父节点的左孩子的情形。父节点是祖父节点的右孩子的情形和分析的情形对称。
红黑树的删除步骤：
首先，找到待删结点，然后分以下几种情况：
二叉查找树的删除分三种情况：
已知：平衡状态下红黑树要么是单支黑-红，要么有两个子节点。
[if !supportLists]1. [endif]要删除的节点正好是叶子节点，直接删除就OK了；
2. 只有左孩子或者右孩子，直接把这个孩子上移放到要删除的位置就好了；
3. 有两个孩子，就需要选一个合适的孩子节点作为新的根节点，该节点称为继承节点。
1.要删除的节点正好是叶子节点，直接删除就 OK 了
2.有左孩子或者右孩子，直接把这个孩子上移放到要删除的位置就好了
3.有两个孩子，就需要选一个合适的孩子节点作为新的根节点，该节点称为 继承节点。
调整思想
为了保证删除节点父亲节点左右两边黑色节点数一致，需要重点关注父亲节点没删除的那一边节点是不是黑色。如果删除后父亲节点另一边比删除的一边黑色节点多，就要想办法搞到平衡，具体的平衡方法有如下几种方法：
[if !supportLists]1. [endif]把父亲节点另一边（即删除节点的兄弟树）其中一个节点弄成红色，也少一个黑色
[if !supportLists]2. [endif]或者把另一边多的黑色节点转过来一个
删除节点在父亲节点的左子树还是右子树，调整方式都是对称的，这里以当前节点为父节点的左孩子为例进行分析。
第三：若删除节点有左右两个儿子，即左右子树。需要按照二叉搜索树的删除规律，从右子树中找最小的替换删除节点（该节点至多有一个右子树，无左子树），将该节点记为y， 删除节点记为z，y的右子树记为x（可能为空）。
删除规则：用y替换z，交换y与z颜色，同时y = z，改变y的指向，让y指向最终删除节点。为了便于理解，可以先这样假设：将y与z的数据交换，但颜色不交换，这样，实际相当于将删除转移到了y节点，而z处保持原先状态（处于平衡）。此时可以完全不用了理会z节点，直接删除y节点即可。因为y最多只有一个右子树，无左子树，这便转移到了“第二”。
对于删除y节点，有几种考虑：
1.若y为红色，则这种情况如上述”第一“所述，并不影响平衡性。
2.若y为黑色，则删除y后，x替换了y的位置，这样x子树相对于兄弟节点w为根的子树少了一个黑节点，影响平衡，需要进行调整。
剩下的调整工作就是将x子树中找一合适红色节点，将其置黑，使得x子树与w子树达到平衡。若x为红色，直接将x置为黑色，即可达到平衡。
若x为黑色，则分下列几种情况：
情况1： x的兄弟w为红色，则w的子树必然全黑，w父亲p也为黑。改变p与w的颜色，同时对p做一次左旋，这样就将情况1转变为情况2,3,4的一种。
情况2： x的兄弟w为黑色，x与w的父亲颜色可红可黑。因为x子树相对于其兄弟w子树少一个黑色节点，可以将w置为红色，这样，x子树与w子树黑色节点一致，保持了平衡。new x为x与w的父亲。new x相对于它的兄弟节点new w少一个黑色节点。如果new x为红色，则将new x置为黑，则整棵树平衡。
情况3： w为黑色，w左孩子红色，右孩子黑色。 交换w与左孩子的颜色，对w进行右旋。转换为情况4。
情况4： w为黑色，右孩子为红色。交换w与父亲p颜色，同时对p做左旋。这样左边缺失的黑色就补回来了，同时，将w的右孩子置黑，这样左右都达到平衡。
情况2是最好理解的，减少右子树的一个黑色节点，使x与w平衡，将不平衡点上移至x与w的父亲，进行下一轮迭代。情况1：如果w为红色，通过旋转，转成成情况1,2,3进行处理。而情况3转换为情况4进行处理。也就是说，情况4是最接近最终解的情况。情况4：右儿子是红色节点，那么将缺失的黑色交给右儿子，通过旋转，达到平衡。
代码：
/**
* Java 语言: 红黑树
*
* @author glt
* @date 2019/7/23
*/
public class RedBlackCD> {
private RBTNodemRoot; // 根结点
private static final boolean RED =false;
private static final boolean BLACK =true;
public class RBTNode> {
boolean color; // 颜色
T key; // 关键字(键值)
RBTNodeleft; // 左孩子
RBTNoderight; // 右孩子
RBTNodeparent; // 父结点
public RBTNode(T key, boolean color, RBTNode parent, RBTNode left, RBTNode right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
public StringtoString() {
return "" +key + (this.color ==RED ?"(R)" :"B");
}
}
public RedBlackCD() {
mRoot =null;
}
private RBTNodeparentOf(RBTNode node) {
return node !=null ? node.parent :null;
}
private boolean colorOf(RBTNode node) {
return node !=null ? node.color :BLACK;
}
private boolean isRed(RBTNode node) {
return ((node !=null) && (node.color ==RED)) ?true :false;
}
private boolean isBlack(RBTNode node) {
return !isRed(node);
}
private void setBlack(RBTNode node) {
if (node !=null)
node.color =BLACK;
}
private void setRed(RBTNode node) {
if (node !=null)
node.color =RED;
}
private void setParent(RBTNode node, RBTNode parent) {
if (node !=null)
node.parent = parent;
}
private void setColor(RBTNode node, boolean color) {
if (node !=null)
node.color = color;
}
/*
* (递归实现)查找"红黑树x"中键值为key的节点
*/
private RBTNodesearch(RBTNode x, T key) {
if (x ==null)
return x;
int cmp = key.compareTo(x.key);
if (cmp <0)
return search(x.left, key);
else if (cmp >0)
return search(x.right, key);
else
return x;
}
public RBTNodesearch(T key) {
return search(mRoot, key);
}
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
private void leftRotate(RBTNode x) {
// 设置x的右孩子为y
RBTNode y = x.right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.left;
if (y.left !=null)
y.left.parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.parent;
if (x.parent ==null) {
this.mRoot = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
}else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/*
* 对红黑树的节点(y)进行右旋转
*
* 右旋示意图(对节点y进行左旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
private void rightRotate(RBTNode y) {
// 设置x是当前节点的左孩子。
RBTNode x = y.left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.right;
if (x.right !=null)
x.right.parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.parent;
if (y.parent ==null) {
this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
}else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
else
y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
/*
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 插入的结点 // 对应《算法导论》中的z
*/
private void insertFixUp(RBTNode node) {
RBTNode parent, gparent;
// 若“父节点存在，并且父节点的颜色是红色”
while (((parent = parentOf(node)) !=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1条件：叔叔节点是红色
RBTNode uncle = gparent.right;
if ((uncle !=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
RBTNode tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
}else {//若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件：叔叔节点是红色
RBTNode uncle = gparent.left;
if ((uncle !=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
RBTNode tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 将根节点设为黑色
setBlack(this.mRoot);
}
/*
* 将结点插入到红黑树中
*
* 参数说明：
* node 插入的结点 // 对应《算法导论》中的node
*/
private void insert(RBTNode node) {
int cmp;
RBTNode y =null;
RBTNode x =this.mRoot;
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x !=null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp <0)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y !=null) {
cmp = node.key.compareTo(y.key);
if (cmp <0)
y.left = node;
else
y.right = node;
}else {
this.mRoot = node;
}
// 2. 设置节点的颜色为红色
node.color =RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
}
/*
* 新建结点(key)，并将其插入到红黑树中
*
* 参数说明：
* key 插入结点的键值
*/
public void insert(T key) {
RBTNode node =new RBTNode(key, BLACK, null, null, null);
// 如果新建结点失败，则返回。
if (node !=null)
insert(node);
}
/*
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 待修正的节点
*/
private void removeFixUp(RBTNode node, RBTNode parent) {
RBTNode other;
while ((node ==null || isBlack(node)) && (node !=this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left ==null || isBlack(other.left)) &&
(other.right ==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
}else {
if (other.right ==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node =this.mRoot;
break;
}
}else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left ==null || isBlack(other.left)) &&
(other.right ==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
}else {
if (other.left ==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node =this.mRoot;
break;
}
}
}
if (node !=null)
setBlack(node);
}
/*
* 删除结点(node)，并返回被删除的结点
*
* 参数说明：
* node 删除的结点
*/
private void remove(RBTNode node) {
RBTNode child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ((node.left !=null) && (node.right !=null)) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
RBTNode replace = node;
// 获取后继节点
replace = replace.right;
while (replace.left !=null)
replace = replace.left;
// "node节点"不是根节点(只有根节点不存在父节点)
if (parentOf(node) !=null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
}else {
// "node节点"是根节点，更新根节点。
this.mRoot = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = colorOf(replace);
// "被删除节点"是"它的后继节点的父节点"
if (parent == node) {
parent = replace;
}else {
// child不为空
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)
removeFixUp(child, parent);
node =null;
return;
}
//只有一个孩子
if (node.left !=null) {
child = node.left;
}else {
child = node.right;
}
parent = node.parent;
// 保存"取代节点"的颜色
color = node.color;
if (child !=null)
child.parent = parent;
// "node节点"不是根节点
if (parent !=null) {
if (parent.left == node)
parent.left = child;
else
parent.right = child;
}else {
this.mRoot = child;
}
if (color ==BLACK)
removeFixUp(child, parent);
node =null;
}
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明：
* tree 红黑树的根结点
* z 删除的结点
*/
public void remove(T key) {
RBTNode node;
if ((node = search(mRoot, key)) !=null)
remove(node);
}
}
