红黑树
要想真正的学会红黑树，不应该是无脑背判断啊条件什么的，而是应该沿着红黑树的前身2-3-4树来真正学会这种数据结构，当然我也只是认为加上2-3-4树可以对红黑树的理解。不喜勿喷(●ˇ∀ˇ●)
1. 2-3-4树
2-3-4树是四阶的 B树(Balance Tree)，他属于一种多路查找树，2-3-4树是对完美平衡二叉树的扩展，它的结构有以下限制：
- 所有叶子节点都拥有相同的深度。
-
节点只能是 2-节点、3-节点、4-节点之一。
- 2-节点：包含 1 个元素的节点，有 2 个子节点；
- 3-节点：包含 2 个元素的节点，有 3 个子节点；
- 4-节点：包含 3 个元素的节点，有 4 个子节点；
-
所有节点必须至少包含1个元素，元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点； 而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。
2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，所以一般使用它的等同——红黑树
2-3-4树可以说是一种规范，一种标准，而红黑树就是实现了2-3-4树这个模型，所以红黑树的操作都可以追溯到2-3-4树上
2-3-4树的插入
对应关系
每个红黑树都会对应一个2-3-4树，而一个2-3-4树会对应多个红黑树，就是因为3结点有两种表现形式
每一个红色结点都是和上面的黑色结点是一起的，只有黑色结点在2-3-4树中才会贡献层数，红色结点只是挂在黑色结点上，所以在实现了2-3-4树模型的红黑树中，也是只需要黑色平衡就可以了
红黑树和 2-3-4树的结点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4树还是红 黑树，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和删除结点时尽量通过子 树内部调整来达到平衡，2-3-4树实现平衡是通过结点元素数变化，红黑树是通过结点旋转和变色。
2.红黑树实现
2.1.概述
红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下5大性质：
- 节点是红色或黑色。 （2-3-4树中三种结点对应红黑树都是红色加黑色的形式）
- 根是黑色。 （2结点是黑色，3结点和4结点都可以通过旋转保持上黑下红的形式）
- 所有叶子都是黑色（叶子是NIL节点）。 （感觉这一条是为了迎合性质四的，反正我是没咋看懂，，，）
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节 点。） （2-3-4树模型中红色和黑色是一个结点，每一个红色结点都是挂在黑色结点上的，4结点的两个红色分配在左右，也不可能有两个红色结点出现）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（黑色平衡）。（2-3-4树叶子结点都在同一层中，每个结点都只有一个黑色结点，所有对应红黑树就是黑色结点才会贡献层数，也就是黑色平衡）
红黑树的实现情况比较多，建议画图来实现代码，防止混淆加忘记，我在最后加了我写的可以直接运行的代码，所以篇幅比较大，不想看的可以直接拿代码跑一跑(●ˇ∀ˇ●)。
2.2.右旋
以某个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点 的左子节点，右子节点保持不变。
代码实现
/**
* 右旋
* gn gn
* / /
* n rn
* / \ / \
* rn ln --> rr n
* / \ / \
* rr rl rl ln
*/
private void rightRotate(RBNode n){
if (n != null){
// 获取左孩子
RBNode rn = n.left;
// 1、将rl放到n的左孩子上
// rn.right为null不影响赋值
n.left = rn.right;
if (rn.right != null){
rn.right.parent = n;
}
// 2、将rn放的n的位置
rn.parent = n.parent;
// 如果父节点为空，就将rn指向根节点
if (n.parent == null){
this.root = rn;
}
// 判断rn该插入到父节点的左右哪个孩子结点
else if (n == n.parent.left){
n.parent.left = rn;
}else {
n.parent.right = rn;
}
// 3、将换好位置的rn与n互相绑定
rn.right = n;
n.parent = rn;
}
}
2.3.左旋
以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点 的右子节点，左子节点保持不变。
/**
* 左旋就是将右旋反过来
* @param n
*/
private void leftRotate(RBNode n){
if (n != null){
RBNode rl = n.right;
n.right = rl.left;
if (rl.left != null){
rl.left.parent = n;
}
rl.parent = n.parent;
if (n.parent == null){
this.root = rl;
} else if (n == n.parent.left){
n.parent.left = rl;
}else {
n.parent.right = rl;
}
rl.left = n;
n.parent = rl;
}
}
2.4.插入
2-3-4树的新增一定是在叶子结点上的，那么实现了2-3-4树的红黑树，插入也一定是在叶子结点上的，所有也就只有四种情况（按照2-3-4树进行分的情况，然后转化为对应的红黑树情况）：
- 没有结点，插入第一个结点为根节点
- 插入与二节点结合成一个三节点
- 插入与三节点结合成一个四节点
- 插入与四结点结合，四节点往上分裂
情况一
情况二
情况三
情况四
代码实现
插入一定会插入在二叉树的叶子结点上，所以需要先遍历要插入结点的父节点，然后将结点插入上去，最后才是红黑树的调整。
步骤：
-
判断根节点是否存在
-
查询插入结点的父节点
-
将新插入结点与父节点关联
-
红黑树平衡调整
-
2-3-4树：插入第一个结点，将当前结点设为根节点。
红黑树：将插入结点变成黑色，新创建的结点默认就是黑色，所有也不需要调整
-
2-3-4树：插入一个结点与2结点结合，变成一个三节点
红黑树：插入到黑色结点下面，不需要调整
-
2-3-4树：插入一个结点与3结点结合，变成一个四节点
红黑树：这里有四种情况（左三，右三，左中右，右中左），这里只有左三和右三需要调整，也就是父节点为红色，爷爷结点为黑色，左中右和右中左都是父节点是黑色结点不需要调整
新增结点+上黑下红 --> 旋转变色 --> 中间结点为黑色，左右两个结点为红色（爷爷结点下来变红，父亲结点上去变黑）
-
2-3-4树：插入一个结点与4结点结合，4结点分裂，中间结点上去待合并，新增结点与左右两个2结点结合
红黑树：父节点和叔叔结点是红色，爷爷结点是黑色（判断条件是叔叔结点是红色） --> 变色 --> 父亲和叔叔变黑，爷爷变红，以爷爷结点继续往上递归进行判断
-
public void put(K key,V value){
RBNode node = this.root;
// 1、判断根节点是否存在
if (node == null){
// 如果不存在，则直接将当前结点设置为根节点，新创建结点默认是黑色
root = new RBNode<K, V>(null, key, value == null? (V) key :value);
return;
}
// 2、查找插入结点的父节点
RBNode<K,V> parent = node;
int cmp;
if (key == null){
throw new NullPointerException();
}
do {
parent = node;
// 如果key值大于父节点，往右子树进行寻找
// 如果key值小于父节点，往左子树进行寻找
// 如果key值命中，直接替换值然后返回
cmp = key.compareTo(parent.key);
if (cmp > 0){
node = node.right;
}else if (cmp < 0){
node = node.left;
}else {
node.value = value;
return;
}
}while (node != null);
node = new RBNode<K, V>(parent, key, value == null? (V) key :value);
// 3、将新插入结点与父节点关联
node.parent = parent;
if (cmp > 0){
parent.right = node;
}else {
parent.left = node;
}
// 上面三步插入是二叉树与红黑树通用的插入方法，下面调整才是红黑树平衡的重点
// 插入完之后，调整
fixAfterPut(node);
}
private void fixAfterPut(RBNode<K,V> node){
// 插入结点都为红色
setColor(node,RED);
// 只有3、4情况才需要调整，这里的循环是递归操作情况4，并且插入的父节点都是红色
while (node != null && node != this.root && parentOf(node).color == RED){
// 插入结点在左边,也就是叔叔结点在右边
if (parentOf(node) == parentOf(parentOf(node)).left){
// 获取爷爷结点和叔叔结点
RBNode<K,V> gParent = parentOf(parentOf(node));
RBNode<K,V> uncle = rightOf(gParent);
// 情况4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
// 在当前子树进行调整完之后，以爷爷结点为当前结点，继续递归往上进行调整
// 如果递归到根节点就退出，然后将根节点染色，层数加一
// 如果递归到当前结点的父节点为黑色，那么调整成功，直接退出循环
node = gParent;
}else { // 情况3
// 这是情况3的一种特殊情况，插入到父节点的右孩子
// 需要进行一次左旋，就调整成正宗的左3
if (node == rightOf(parentOf(node))){
// 这是将父节点为当前结点，因为左旋后父节点会下来到子节点的位置
// 如果不这样那左旋之后当前结点就会变成原来的父节点
node = parentOf(node);
leftOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
rightRotate(gParent);
}
}else { // 插入结点在右边
RBNode<K,V> gParent = parentOf(parentOf(node));
RBNode<K, V> uncle = leftOf(gParent);
// 情况4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
node = gParent;
}else { // 情况3
if (node == leftOf(parentOf(node))){
node = parentOf(node);
rightOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
leftRotate(gParent);
}
}
}
// 情况4，如果递归到根节点，就把树的层数加一
setColor(this.root,BLACK);
}
2.5.删除
红黑树的删除与二叉树的删除很相似，就是多了一步调整的步骤，所有先来研究二叉树的删除，然后再扩展到红黑树的删除，当然2-3-4树也类似，在这里用二叉树是比较方便，也可以自己想想2-3-4树的删除操作。
二叉树
删除操作的情况只有三种：
- 删除结点是叶子结点，那么直接删除
- 删除结点有一个子节点，那么用子节点来替代删除结点
-
删除结点有两个子节点，直接删除情况太复杂，可以找到待删除结点的前驱结点和后继结点来替代删除
- 找到前驱结点或后继结点后，复制前驱结点或后继结点的值，覆盖掉待删除结点的值，然后删除前驱结点或后继结点。也就是说删除该节点不是真正的删除，而是拿前驱或后继结点的值来覆盖。
- 将删除有两个孩子的情况转化为删除只有一个孩子或没有孩子的情况，也就是将复杂的情况3转化为较简单的情况1和2，复杂的问题简单化。
找前驱和后继代码
/**
* 找前驱结点
* 方法：找该节点的左子树，找到后从左子树的右孩子一直往下找
*/
private RBNode<K,V> predecessor(RBNode<K,V> node){
if (node == null){
return null;
}
// 如果有左孩子，那么就从左孩子的右孩子一直往下找
else if (leftOf(node) != null){
RBNode<K,V> lNode = leftOf(node);
// 如果右孩子为空，那么就说明找到了，直接退出返回
while (rightOf(lNode) !=null){
lNode = rightOf(lNode);
}
return lNode;
}else {
// 在删除操作中是不会出现这种情况的，这种情况一般是叶子结点或者只有一个孩子的情况来找前驱
// 在删除操作中如果是这种情况就直接删除了，不用废这力气
// 这里是找前驱结点的情况，所有把这种情况也一块写下来了
// 获取父节点
RBNode<K, V> parent = parentOf(node);
// 获取自己
RBNode<K,V> child = node;
// 判断当前结点是否是父节点的左结点，如果是就说明找到了，退出返回
// 如果父节点为空，也就是找到根节点还没有找到，那么说明当前结点没有前驱结点，返回null
while (parent!=null&&child==leftOf(parent)){
child = parent;
parent = parentOf(parent);
}
// 当然如果没有前驱结点也可以返回自己，作为自己的前驱结点，我的选择的返回了null
// if (parent == null){
// return node;
// }
return parent;
}
}
/**
* 找后继结点
* 与找前驱相反
* @param node
* @return
*/
private RBNode<K,V> successor(RBNode<K,V> node){
if (node == null){
return null;
}
else if (rightOf(node) != null){
RBNode<K,V> rNode = rightOf(node);
while (leftOf(rNode) !=null){
rNode = leftOf(rNode);
}
return rNode;
}else {
RBNode<K, V> parent = parentOf(node);
RBNode<K,V> child = node;
while (parent!=null&&child==rightOf(parent)){
child = parent;
parent = parentOf(parent);
}
// if (parent == null){
// return node;
// }
return parent;
}
}
删除结点
// 按照key找到该节点
private RBNode<K,V> getNode(K key) {
RBNode<K,V> node = this.root;
// 从根节点开始遍历，如果大于往右走，小于往左走，等于则返回
// 出循环则说明没有找到
while (node != null){
// int cmp = node.key.compareTo(key); // 这个不能反着来，不知道为啥。。。
int cmp = key.compareTo(node.key);
if (cmp > 0 ){
node = node.right;
}else if (cmp < 0 ){
node = node.left;
}else {
return node;
}
}
return null;
}
// 对外公开的方法
public V remove(K key){
// 先找到待删除的结点
RBNode<K,V> node = getNode(key);
if (node == null){
return null;
}
// 获取要返回的值
V oldValue = node.value;
// 删除结点
deleteNode(node);
return oldValue;
}
/**
* 1. 删除结点是叶子结点，那么直接删除
* 2. 删除结点有一个子节点，那么用子节点来替代删除结点
* 3. 删除结点有两个子节点，直接删除情况太复杂，可以找到待删除结点的前驱结点和后继结点来替代删除
* @param node
*/
private void deleteNode(RBNode<K,V> node) {
// 删除结点有两个孩子的情况，先把删除的结点替换为前驱或者后继结点
if (leftOf(node)!=null && rightOf(node)!= null){
// 这是使用的是后继结点
RBNode<K, V> rep = successor(node);
// 使用前驱结点
// RBNode<K, V> rep = predecessor(node);
node.key = rep.key;
node.value = rep.value;
// 把前驱或者后继结点指向node
// 前驱或者后继结点一定是叶子结点或只有一个孩子的结点，把问题简单化
node = rep;
}
// 替换结点，如果左孩子不存在就返回右孩子，当然如果右孩子也不存在那么就是null，也就是叶子结点了，也就是两种情况:1.有一个孩子，2.没有孩子
RBNode<K,V> replacement = leftOf(node)!=null?leftOf(node):rightOf(node);
// 替换节点有一个孩子的情况
if (replacement != null){
// 这里的待删除结点可能是前驱也可能是后继，两种情况都判断了，调整代码时比较方便
// 将删除结点的父亲给替代结点，也就是将子节点给关联起来
replacement.parent = parentOf(node);
// 如果删除结点是只有一个孩子的根节点，那么把替代结点设置为跟结点
if (parentOf(node) == null){
this.root=replacement;
}
// 当前删除结点是后继结点，treemap使用的
else if (node == leftOf(parentOf(node))){
node.parent.left = replacement;
}
// 当前删除结点是前驱结点
else {
node.parent.right = replacement;
}
// 引用全部为null，等待虚拟机回收垃圾
node.parent = node.left = node.right = null;
// 只有删除结点为黑色才有调整的必要，（如果是红色的话，子节点一定是黑色，把子节点替换上了不会影响黑色结点的层数，所以也就不需要红黑树调整了
if (node.color == BLACK){
// replacement一定是红色
fixAfterRemove(replacement);
}
}
// 如果删除结点是根节点，直接删除，这里的根节点是没有孩子的根节点，
// 也就是树上只有一个结点，也就是根节点，直接把树清空
else if (parentOf(node) == null){
this.root = null;
}
// 替换结点是叶子结点的情况
else {
// 只有删除结点为黑色才有调整的必要
if (node.color == BLACK){
fixAfterRemove(replacement);
}
//先调整，再删除
if(node.parent!=null){
if(node==node.parent.left){
node.parent.left=null;
}
else if(node==node.parent.right){
node.parent.right=null;
}
node.parent=null;
}
}
}
红黑树删除后调整
/**
* 调整
* 情况一：自己能搞定的，也就是三节点和四节点，
* 如果是三节点，那么删除后将替代结点变色就可以了
* 如果是四结点，那么只可能删除四节点的两边结点，也就是两个的红色子节点
* 情况二：自己搞不定，找兄弟借，兄弟不借，父亲下来，然后兄弟上去一个，
* 兄弟不能直接给，会破坏树的顺序，判断条件就是没有孩子的黑色结点，
* 父亲下来了，那么父亲的位置就会空一个，会破坏2-3-4树的完整性，兄弟结点需要找一个上去
* 情况三：兄弟没得借，强行删除，兄弟受到牵连，也就是2-3-4树中，自己、兄弟、父亲都是二节点，父亲也不能向下融合删除
* 兄弟变红，以父亲为当前结点向上递归进行判断，进行按照情况二、三继续进行判断
*
* @param node
*/
private void fixAfterRemove(RBNode<K,V> node) {
while (node != root && colorOf(node)==BLACK){
// 删除结点是左孩子的情况
if(node == leftOf(parentOf(node))){
// 获取叔叔结点，但是不一定是真正的叔叔结点（这个叔叔结点如果是红色就不是真正的叔叔结点），需要进行判断
RBNode<K,V> uncle = rightOf(parentOf(node));
// 获取真正的叔叔结点
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
leftRotate(parentOf(node));
// 更新叔叔结点
uncle = rightOf(parentOf(node));
}
// 情况三，兄弟也没有，那么兄弟情同手足，自损变成红色，并且向父亲求助，也就是向上递归，
// 如果父亲是红色那么变成黑色就平衡了，也就是循环判断里面，如果是红色就退出循环，在循环下面机械能变色，如果不是那么继续自损并且向上求助
// 对应2-3-4树就是兄弟结点借不到， 如果父亲是三节点，那么就向下融合一个变成四节点然后删除，如果父节点也是二结点，那么以父节点为当前结点继续向上递归判断
// 这两个判断是兄弟结点的左右孩子都为空，black在colorOf方法中是null的替换
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
setColor(uncle,RED);
// 向上循环，如果递归到根节点，那么直接退出
node = parentOf(node);
}
// 情况二，找兄弟借，兄弟有的借，兄弟结点上去，父亲结点下来，这样满足二叉树的顺序
else {
// 兄弟结点是三节点和四节点的情况类似
// 如果是三节点，孩子在右边直接旋转就行，在左边算是例外，需要把左孩子旋转到右边然后在旋转
// 如果是四节点，那么有两种情况，第一种是给一个孩子，第二种是给两个孩子，
// 第一种需要旋转两次（正常的红黑树），先按叔叔结点进行一次右旋，把三个结点放在一条线上，在按父节点左旋
// 第二种是旋转一次（treemap中使用的，我在这也用这种），直接按照父节点左旋，减少了旋转次数，优化了效率
// 三节点把孩子旋转到右边后，与四节点操作一样了，不再需要判断了
// 如果右孩子为空，那么兄弟的孩子一定是在左边，因为删除的这个肯定是一个三节点
if (colorOf(rightOf(uncle))==BLACK){
// 不能直接进行旋转，父节点是一个三节点，所以一定要有三个孩子，直接旋转会破坏2-3-4树定义
// 要先把兄弟结点的左孩子旋转到右边，然后在借出去
setColor(leftOf(uncle),BLACK);
setColor(uncle,RED);
// 这个时候叔叔结点下去了，需要更新叔叔结点
uncle = rightOf(parentOf(node));
}
// 将叔叔结点变成和父节点一样的颜色
setColor(uncle, colorOf(parentOf(node)));
setColor(rightOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
// 左孩子如果有的话，不用变色
leftRotate(parentOf(node));
// 将删除结点设为root，也就是退出循环的意思
node = root;
}
}
// 删除结点是右孩子的情况，和左孩子正好相反
else {
RBNode<K,V> uncle = leftOf(parentOf(node));
// 获取真正的叔叔结点
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
rightRotate(parentOf(node));
uncle = leftOf(parentOf(node));
}
// 情况三，兄弟也没有，那么兄弟情同手足，都自损变成红色，并且向父亲求助，也就是向上递归，
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
setColor(uncle,RED);
// 向上循环
node = parentOf(node);
}
// 情况二，找兄弟借，兄弟有的借，兄弟结点上去，父亲结点下来，这样满足二叉树的顺序
else {
if (colorOf(leftOf(uncle))==BLACK){
setColor(rightOf(uncle),BLACK);
setColor(uncle,RED);
uncle = leftOf(parentOf(node));
}
setColor(uncle, colorOf(parentOf(node)));
setColor(leftOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
leftRotate(parentOf(node));
node = root;
}
}
}
// 情况一，删除的结点有一个孩子，而且这个孩子肯定是红色的，直接变色成黑色
// 情况三，根节点变为黑色
setColor(node,BLACK);
}
删除总结
- 按照key值找到该节点，并获取删除结点的value值进行删除成功后的返回
- 开始删除结点，先判断该节点是否是最麻烦的情况（有两个孩子），如果是就找到该节点的前驱节点或者后继结点，我这里选择后继结点，这里删除并不是真正的删除，只是把后继结点的值覆盖待删除结点的值，然后删除后继结点即可
- 然后按照只有一个结点或者是叶子结点的情况进行删除操作（删除有一个孩子结点的情况，就用这个孩子进行替代，然后按孩子结点进行红黑树调整，如果删除的是叶子结点就先按叶子结点调整，然后再删除），只有删除结点为黑色才有调整的必要，如果是红色直接删除就可以了，不影响红黑树，删除有一个孩子的情况，替代之后的这个孩子一定是红色，所以可能会对红黑树的平衡有影响，删除叶子结点的话，被删除结点是黑色结点的情况，对红黑树肯定有影响需要调整再删除。
-
下边是对2-3-4树删除对应到红黑树中的调整：
-
自己能搞定的，也就是2-3-4树中的三节点或者四节点
- 如果是三节点，那么删除后将替代结点变色就可以了，要删除的结点在删除阶段就已经删除了，只需要在调整中将移上来的孩子结点变为黑色就行了
- 如果是四节点，不会进入调整中，因为删除的肯定是四节点的两个红色孩子结点，不影响红黑树
-
自己搞不定的，也就是2-3-4树中的二节点，兄弟结点能借，但兄弟结点不借，父节点下来，兄弟节点上去
- 兄弟不能直接给，会破坏树的顺序，判断条件就是没有孩子的黑色结点（不是三、四结点），
- 父亲下来了，那么父亲的位置就会空一个，会破坏2-3-4树的完整性，兄弟结点需要找一个上去
-
兄弟没得借，那么当前结点强行删除，兄弟受到牵连，也就是2-3-4树中，自己、兄弟、父亲都是二节点，父亲也不能向下融合删除，如果向下融合的话在2-3-4树中就会少一层，破坏性质
- 兄弟变红，以父亲为当前结点向上递归进行判断，进行按照情况二、三继续进行判断，如果迭代到了根部还没有解决，那么就结束迭代，红黑树就会少一层黑色结点
-
自己能搞定的，也就是2-3-4树中的三节点或者四节点
删除结点模拟
3.总代码
红黑树代码
public class RBTree<K extends Comparable<K>,V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
private RBNode root;
public RBNode getRoot() {
return root;
}
public void setRoot(RBNode root) {
this.root = root;
}
private RBNode parentOf(RBNode node){
// 如果该节点不为空，返回父节点，
// 如果为空，那父节点肯定也为空
return node!=null?node.parent:null;
}
private RBNode leftOf(RBNode node){
return node!= null?node.left:null;
}
private RBNode rightOf(RBNode node){
return node!= null?node.right:null;
}
private boolean colorOf(RBNode node){
// 如果该结点为空，就返回BLACK，就是一个判空操作
// treeMap源码就是这样写的
return node== null ?BLACK:node.color;
}
private void setColor(RBNode node,boolean color){
if (node != null){
node.color = color;
}
}
/**
* 右旋
* gn gn
* / /
* n rn
* / \ / \
* rn ln --> rr n
* / \ / \
* rr rl rl ln
*/
private void rightRotate(RBNode n){
if (n != null){
// 获取左孩子
RBNode rn = n.left;
// 1、将rl放到n的左孩子上
// rn.right为null不影响赋值
n.left = rn.right;
if (rn.right != null){
rn.right.parent = n;
}
// 2、将rn放的n的位置
rn.parent = n.parent;
// 如果父节点为空，就将rn指向根节点
if (n.parent == null){
this.root = rn;
}
// // 判断rn该插入到父节点的左右哪个孩子结点
else if (n == n.parent.left){
n.parent.left = rn;
}else {
n.parent.right = rn;
}
// 3、将换好位置的rn与n互相绑定
rn.right = n;
n.parent = rn;
}
}
/**
* 左旋就是将右旋反过来
* @param n
*/
private void leftRotate(RBNode n){
if (n != null){
RBNode rl = n.right;
n.right = rl.left;
if (rl.left != null){
rl.left.parent = n;
}
rl.parent = n.parent;
if (n.parent == null){
this.root = rl;
} else if (n == n.parent.left){
n.parent.left = rl;
}else {
n.parent.right = rl;
}
rl.left = n;
n.parent = rl;
}
}
/**
* 插入
* @param key
* @param value
*/
public void put(K key,V value){
RBNode node = this.root;
// 1、判断根节点是否存在
if (node == null){
// 如果不存在，则直接将当前结点设置为根节点，新创建结点默认是黑色
root = new RBNode<K, V>(null, key, value == null? (V) key :value);
return;
}
// 2、查找插入结点的父节点
RBNode<K,V> parent = node;
int cmp;
if (key == null){
throw new NullPointerException();
}
do {
parent = node;
// 如果key值大于父节点，往右子树进行寻找
// 如果key值小于父节点，往左子树进行寻找
// 如果key值命中，直接替换值然后返回
cmp = key.compareTo(parent.key);
if (cmp > 0){
node = node.right;
}else if (cmp < 0){
node = node.left;
}else {
node.value = value;
return;
}
}while (node != null);
node = new RBNode<K, V>(parent, key, value == null? (V) key :value);
// 3、将新插入结点与父节点关联
node.parent = parent;
if (cmp > 0){
parent.right = node;
}else {
parent.left = node;
}
// 上面三步插入是二叉树与红黑树通用的插入方法，下面调整才是红黑树平衡的重点
// 插入完之后，调整
fixAfterPut(node);
}
/**
* 1.2-3-4树：插入第一个结点，将当前结点设为根节点
* 红黑树：将插入结点变成黑色，新创建的结点默认就是黑色，所有也不需要调整
* 2.2-3-4树：插入一个结点与2结点结合，变成一个三节点
* 红黑树：插入到黑色结点下面，不需要调整
* 3.2-3-4树：插入一个结点与3结点结合，变成一个四节点
* 红黑树：父节点为红色，爷爷结点为黑色，这里有四种情况（左三，右三，左中右，右中左），这里只有左三和右三需要调整
* 新增结点+上黑下红 --> 旋转变色 --> 中间结点为黑色，左右两个结点为红色（爷爷结点下来变红，父亲结点上去变黑）
* 4.2-3-4树：插入一个结点与4结点结合，4结点分裂，中间结点上去待合并，新增结点与左右两个2结点结合
* 红黑树：父节点和叔叔结点是红色，爷爷结点是黑色 --> 变色 --> 父亲和叔叔变黑，爷爷变红，以爷爷结点继续进行这四种判断
* @param node
*/
private void fixAfterPut(RBNode<K,V> node){
// 插入结点都为红色
setColor(node,RED);
// 只有3、4情况才需要调整，这里的循环是递归操作情况4
while (node != null && node != this.root && parentOf(node).color == RED){
// 插入结点在左边,也就是叔叔结点在右边
if (parentOf(node) == parentOf(parentOf(node)).left){
RBNode<K,V> gParent = parentOf(parentOf(node));
RBNode<K,V> uncle = rightOf(gParent);
// 情况4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
// 在当前子树进行调整完之后，以爷爷结点为当前结点，继续递归往上进行调整
// 如果递归到根节点就退出，然后将根节点染色，层数加一
// 如果递归到当前结点的父节点为黑色，那么调整成功，直接退出循环
node = gParent;
}else { // 情况3
// 这是情况3的一种特殊情况，插入到父节点的右孩子
// 需要进行一次左旋，就调整成正宗的左3
if (node == rightOf(parentOf(node))){
node = parentOf(node);
leftOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
rightRotate(gParent);
}
}else { // 插入结点在右边
RBNode<K,V> gParent = parentOf(parentOf(node));
RBNode<K, V> uncle = leftOf(gParent);
// 情况4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
node = gParent;
}else { // 情况3
if (node == leftOf(parentOf(node))){
node = parentOf(node);
rightOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
leftRotate(gParent);
}
}
}
setColor(this.root,BLACK);
}
/**
* 找前驱结点
* 方法：找该节点的左子树，找到后从左子树的右孩子一直往下找
* @param node
* @return
*/
private RBNode<K,V> predecessor(RBNode<K,V> node){
if (node == null){
return null;
}
// 如果有左孩子，那么就从左孩子的右孩子一直往下找
else if (leftOf(node) != null){
RBNode<K,V> lNode = leftOf(node);
// 如果右孩子为空，那么就说明找到了，直接退出返回
while (rightOf(lNode) !=null){
lNode = rightOf(lNode);
}
return lNode;
}else {
// 在删除操作中是不会出现这种情况的，这种情况一般是叶子结点或者只有一个孩子
// 在删除操作中如果是这种情况就直接删除了
// 这里是找前驱结点的情况，所有把这种情况也一块写下来了
// 获取父节点
RBNode<K, V> parent = parentOf(node);
// 获取自己
RBNode<K,V> child = node;
// 判断当前结点是否是父节点的左结点，如果是就说明找到了，退出返回
// 如果父节点为空，也就是找到根节点还没有找到，那么说明当前结点没有前驱结点，返回null
while (parent!=null&&child==leftOf(parent)){
child = parent;
parent = parentOf(parent);
}
// if (parent == null){
// return node;
// }
return parent;
}
}
/**
* 找后继结点
* 与找前驱相反
* @param node
* @return
*/
private RBNode<K,V> successor(RBNode<K,V> node){
if (node == null){
return null;
}
else if (rightOf(node) != null){
RBNode<K,V> rNode = rightOf(node);
while (leftOf(rNode) !=null){
rNode = leftOf(rNode);
}
return rNode;
}else {
RBNode<K, V> parent = parentOf(node);
RBNode<K,V> child = node;
while (parent!=null&&child==rightOf(parent)){
child = parent;
parent = parentOf(parent);
}
// if (parent == null){
// return node;
// }
return parent;
}
}
/**
* 删除结点，返回删除结点的值
* @param key
* @return
*/
public V remove(K key){
// 先找到待删除的结点
RBNode<K,V> node = getNode(key);
if (node == null){
return null;
}
// 获取要返回的值
V oldValue = node.value;
// 删除结点
deleteNode(node);
return oldValue;
}
/**
* 1. 删除结点是叶子结点，那么直接删除
* 2. 删除结点有一个子节点，那么用子节点来替代删除结点
* 3. 删除结点有两个子节点，直接删除情况太复杂，可以找到待删除结点的前驱结点和后继结点来替代删除
* @param node
*/
private void deleteNode(RBNode<K,V> node) {
// 删除结点有两个孩子的情况，先把删除的结点替换为前驱或者后继结点
if (leftOf(node)!=null && rightOf(node)!= null){
// 这是使用的是后继结点
RBNode<K, V> rep = successor(node);
// 使用前驱结点
// RBNode<K, V> rep = predecessor(node);
node.key = rep.key;
node.value = rep.value;
// 把前驱或者后继结点指向node
// 前驱或者后继结点一定是叶子结点或只有一个孩子的结点
node = rep;
}
// 替换结点，如果左孩子不存在就返回右孩子，当然如果右孩子也不存在那么就是null，也就是叶子结点了
RBNode<K,V> replacement = leftOf(node)!=null?leftOf(node):rightOf(node);
// 替换节点有一个孩子的情况
if (replacement != null){
// 这里的待删除结点可能是前驱也可能是后继，两种情况都判断了，调整代码时比较方便
// 将删除结点的父亲给替代结点，也就是将子节点给关联起来
replacement.parent = parentOf(node);
// 如果删除结点是只有一个孩子的根节点，那么把替代结点设置为跟结点
if (parentOf(node) == null){
this.root=replacement;
}
// 当前删除结点是后继结点
else if (node == leftOf(parentOf(node))){
node.parent.left = replacement;
}
// 当前删除结点是前驱结点
else {
node.parent.right = replacement;
}
// 引用全部为null，等待虚拟机回收垃圾
node.parent = node.left = node.right = null;
// 只有删除结点为黑色才有调整的必要
if (node.color == BLACK){
// 替代结点一定是红色
fixAfterRemove(replacement);
}
}
// 如果删除结点是根节点，直接删除，这里的根节点是没有孩子的根节点，
// 也就是树上只有一个结点，也就是根节点，直接把树清空
else if (parentOf(node) == null){
this.root = null;
}
// 替换结点是叶子结点的情况
else {
// 只有删除结点为黑色才有调整的必要
if (node.color == BLACK){
fixAfterRemove(node);
}
//这里调整完之后，把与父亲的指针断掉，变成垃圾等待回收
if(node.parent!=null){
if(node==node.parent.left){
node.parent.left=null;
}
else if(node==node.parent.right){
node.parent.right=null;
}
node.parent=null;
}
}
}
/**
* 调整
* 情况一：自己能搞定的，也就是三节点和四节点，
* 如果是三节点，那么删除后将替代结点变色就可以了
* 如果是四结点，那么只可能删除四节点的两边结点，也就是两个的红色子节点
* 情况二：自己搞不定，找兄弟借，兄弟不借，父亲下来，然后兄弟上去一个，
* 兄弟不能直接给，会破坏树的顺序，判断条件就是没有孩子的黑色结点，
* 父亲下来了，那么父亲的位置就会空，会破坏2-3-4树的完整性，兄弟结点需要找一个上去
* 情况三：兄弟没得借，都自损，也就是2-3-4树中，自己、兄弟、父亲都是二节点，也就是父亲也不能向下融合删除了
* 兄弟变红，以父亲为当前结点向上递归进行判断，进行按照情况二、三进行判断
*
* @param node
*/
private void fixAfterRemove(RBNode<K,V> node) {
while (node != root && colorOf(node)==BLACK){
// 删除结点是左孩子的情况
if(node == leftOf(parentOf(node))){
// 获取叔叔结点，但是不一定是真正的叔叔结点（这个叔叔结点如果是红色就不是真正的叔叔结点），需要进行判断
RBNode<K,V> uncle = rightOf(parentOf(node));
// 获取真正的叔叔结点
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
leftRotate(parentOf(node));
uncle = rightOf(parentOf(node));
}
// 情况三，兄弟也没有，那么兄弟情同手足，都自损变成红色，并且向父亲求助，也就是向上递归，
// 如果父亲是红色那么变成黑色就平衡了，也就是循环判断里面，如果是红色就退出循环然后变色，如果不是那么继续自损并且向上求助
// 对应2-3-4树就是兄弟结点借不到， 如果父亲是三节点，那么就向下融合一个变成四节点然后删除，
// 如果父节点也是二结点，那么以父节点为当前结点继续向上递归判断
// 这两个判断是兄弟结点的左右孩子都为空，black在colorOf方法中是null的替换
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
// 情况复杂
setColor(uncle,RED);
// 向上循环，如果递归到根节点，那么直接退出
node = parentOf(node);
}
// 情况二，找兄弟借，兄弟有的借，兄弟结点上去，父亲结点下来，这样满足二叉树的顺序
else {
// 兄弟结点是三节点还是四节点的情况类似
// 如果是三节点，孩子在右边直接旋转就行，在左边算是例外，需要把左孩子旋转到右边然后在旋转
// 如果是四节点，那么有两种情况，第一种是给一个孩子，第二种是给两个孩子，
// 第一种需要旋转两次（正常的红黑树），先按叔叔结点进行一次右旋，把三个结点放在一条线上，在按父节点左旋
// 第二种是旋转一次（treemap中使用的，我在这也用这种），直接按照父节点左旋，减少了旋转次数，优化了效率
// 三节点把孩子旋转到右边后，与四节点操作一样了，不再需要判断了
// 如果右孩子为空，那么兄弟的孩子一定是在左边，因为删除的这个肯定是一个三节点
if (colorOf(rightOf(uncle))==BLACK){
// 不能直接进行旋转，父节点是一个三节点，所以一定要有三个孩子，直接旋转会破坏2-3-4树
// 要先把兄弟结点的左孩子旋转到右边，然后在借出去
setColor(leftOf(uncle),BLACK);
setColor(uncle,RED);
// 这个时候叔叔结点下去了，需要在进行赋值
uncle = rightOf(parentOf(node));
}
// 将叔叔结点变成和父节点一样的颜色
setColor(uncle, colorOf(parentOf(node)));
setColor(rightOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
// 左孩子如果有的话，不用变色
leftRotate(parentOf(node));
// 将删除结点设为root，也就是退出循环的意思
node = root;
}
}
// 删除结点是右孩子的情况，和左孩子正好相反
else {
RBNode<K,V> uncle = leftOf(parentOf(node));
// 获取真正的叔叔结点
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
rightRotate(parentOf(node));
uncle = leftOf(parentOf(node));
}
// 情况三，兄弟也没有，那么兄弟情同手足，都自损变成红色，并且向父亲求助，也就是向上递归，
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
// 情况复杂
setColor(uncle,RED);
// 向上循环
node = parentOf(node);
}
// 情况二，找兄弟借，兄弟有的借，兄弟结点上去，父亲结点下来，这样满足二叉树的顺序
else {
if (colorOf(leftOf(uncle))==BLACK){
setColor(rightOf(uncle),BLACK);
setColor(uncle,RED);
uncle = leftOf(parentOf(node));
}
setColor(uncle, colorOf(parentOf(node)));
setColor(leftOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
leftRotate(parentOf(node));
node = root;
}
}
}
// 情况一，删除的结点有一个孩子，而且这个孩子肯定是红色的，直接变色成黑色
// 情况三，父亲变为黑色
setColor(node,BLACK);
}
private RBNode<K,V> getNode(K key) {
RBNode<K,V> node = this.root;
// 从根节点开始遍历，如果大于往右走，小于往左走，等于则返回
// 出循环则说明没有找到
while (node != null){
int cmp = key.compareTo(node.key);
if (cmp > 0 ){
node = node.right;
}else if (cmp < 0 ){
node = node.left;
}else {
return node;
}
}
return null;
}
static class RBNode<K extends Comparable<K>,V>{
private RBNode<K,V> parent;
private RBNode<K,V> left;
private RBNode<K,V> right;
private K key;
private V value;
private boolean color = BLACK;
public RBNode() {
}
public RBNode(RBNode<K,V> parent, K key, V value) {
this.parent = parent;
this.key = key;
this.value = value;
}
public RBNode<K, V> getParent() {
return parent;
}
public void setParent(RBNode<K, V> parent) {
this.parent = parent;
}
public RBNode<K, V> getLeft() {
return left;
}
public void setLeft(RBNode<K, V> left) {
this.left = left;
}
public RBNode<K, V> getRight() {
return right;
}
public void setRight(RBNode<K, V> right) {
this.right = right;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
}
}
控制台打印红黑树
public class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 0、默认无色
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
//1、颜色表示
if(currNode.isColor()){//黑色，加色后错位比较明显
res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.getValue()+"\033[0m") ;
}else {
res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.getValue()+"\033[0m") ;
}
//2、R,B表示
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
if (root == null) System.out.println("EMPTY!");
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
测试红黑树
import java.util.Scanner;
public class RBTreeTest {
public static void main(String[] args) {
//新增节点
// insertOpt();
//删除节点
deleteOpt();
}
/**
* 插入操作
*/
public static void insertOpt(){
Scanner scanner=new Scanner(System.in);
RBTree<String,Object> rbt=new RBTree<>();
while (true){
System.out.println("请输入你要插入的节点:");
String key=scanner.next();
System.out.println();
//这里代码最多支持3位数，3位以上的话红黑树显示太错位了，这里就不重构代码了,大家可自行重构
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
rbt.put(key,null);
TreeOperation.show(rbt.getRoot());
}
}
/**
* 删除操作
*/
public static void deleteOpt(){
RBTree<String,Object> rbt=new RBTree<>();
// 测试1：预先造10个节点（1-10）
String keyA=null;
for (int i = 1; i <11 ; i++) {
if((i+"").length()==1){
keyA="00"+i;
}else if((i+"").length()==2){
keyA="0"+i;
}
rbt.put(keyA,null);
}
TreeOperation.show(rbt.getRoot());
//以下开始删除
Scanner scanner=new Scanner(System.in);
while (true){
System.out.println("请输入你要删除的节点:");
String key=scanner.next();
System.out.println();
//这里代码最多支持3位数，3位以上的话红黑树显示太错位了，这里就不重构代码了,大家可自行重构
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
//1 2 3 88 66 77 100 5 4 101
rbt.remove(key);
TreeOperation.show(rbt.getRoot());
}
}
}
