红黑树
2019-02-18 本文已影响25人
一萍之春
什么是红黑树
红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。
它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如在Java集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。
红黑树的特性
红黑树
红黑树的特性是在原有的二叉查找树的基础增加的，如下：
1、红黑树中的每一个节点非红即黑，也就是每一个节点不是红色就是黑色。
2、根节点为黑色节点。
3、叶子结点都是黑色（注意这里说叶子节点其实是上图中的 NIL 节点）。
4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
5、红色节点的子节点一定是黑色节点。
注意：
性质3：在使用Java实现的时候使用null来代替。
性质4：是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。它不是标准的平衡二叉树但是性质4是它的平衡的准则。
性质5：表示没有两个红色节点相连。
红黑树的左旋右旋
左旋
左旋动图
将右子树的左子树链接到父亲节点的右孩子结点，父亲节点作为node结点的左孩子结点便完成了旋转。
具体实现代码如下:
/**
* 左旋
*
* @param node 需要左旋的节点
*/
private void leftRotate(Node node) {
Node right = node.right;
right.parent = node.parent;
node.right = right.left;
right.left = node;
node.parent = right;
if (node.parent == null) {
root = right;
} else {
if (node == right.parent.left) {
right.parent.left = right;
} else {
right.parent.right = right;
}
}
}
右旋
右旋动图
右单旋是左单旋的镜像旋转.
当前节点node，与父亲节点和当前节点的左孩子结点位于一条直线上时，使用右单旋进行平衡。
具体实现代码如下:
/**
* 右旋
*
* @param node 需要进行右旋的节点
*/
private void rightRotate(Node node) {
Node left = node.left;
left.parent = node.parent;
node.left = left.right;
left.right = node;
node.parent = left;
if (node.parent == null) {
root = left;
} else {
if (node == left.parent.left) {
left.parent.left = node;
} else {
left.parent.right = node;
}
}
}
红黑树的插入
红黑树的插入具体可以分为两步：
- 按照二叉查找树的方式进行查入。
- 进行插入的平衡调整，以满足红黑树的要求。
- 左右旋转调整。
- 重新进行着色。
这里如同二叉查找树的操作就不进行细讲了，我们直接从插入后的平衡调整进行。
插入的平衡调整
在这里大家回想一下我们红黑树的规定的第4、5条，但我们插入一个黑色节点的时候会破坏规定的第4条，但是当我们插入一个红色节点的时候可能会破坏规则5。
因此，我们将每一个插入的节点初始的着色都为红色，这样我们就只需要维护我们的规则5了。染成红色后，我们只要关心父节点是否为红，如果是红的，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，这些操作的同时不能影响 不同路径上的黑色节点数一致的规则。
调整的情况：
情况1、父亲节点和叔叔节点都是红色：
父亲节点和叔叔节点都是红色
假设插入的是节点 N，这时父亲节点 P 和叔叔节点 U 都是红色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，这时不管 N 是 P 的左孩子还是右孩子，只要同时把 P 和 U 染成黑色，G 染成红色即可。这样这个子树左右两边黑色个数一致，也满足特征 4。依次往上迭代。
情况2、父亲节点为红色，叔叔节点为黑色并且N为左子女：
父亲节点为红色，叔叔节点为黑色并且N为左子女
将G进行一次右旋并将P节点染黑G节点染红。
情况3、父亲节点为红色，叔叔节点为黑色并且N为右子女：
父亲节点为红色，叔叔节点为黑色并且N为右子女
将P进行一次左旋就成了情况2，在按照情况2的做法进行。
如果父亲节点是爷爷节点的右子女情况2，3的处理方法左旋右旋刚好相反。
/**
* 插入节点
* @param node 插入的节点
*/
private void insert(Node node) {
if (root == null) {
root = node;
return;
}
Node x = root;
Node y = null;
while (x != null) {
y = x;
if (node.num < x.num) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y.num > node.num) {
y.left = node;
} else {
y.right = node;
}
node.color = RED;
insertFixUp(node);
}
/**
* 插入调整
* @param node 插入的节点
*/
private void insertFixUp(Node node) {
Node parent;
Node gparent;
while (node != null && (parent = node.parent) != null && parent.color == RED) {
gparent = parent.parent;
if (gparent.left.color == RED && gparent.right.color == RED) {
gparent.color = RED;
gparent.right.color = BLACK;
gparent.left.color = BLACK;
node=gparent;
} else if (isLeft(parent)) {
if (!isLeft(node)) {
node=parentOf(node);
leftRotate(parent);
}
gparent.left.color=BLACK;
gparent.color=RED;
rightRotate(gparent);
} else {//处理和上一个方式刚好相反
if (isLeft(node)){
node=parentOf(node);
rightRotate(parent);
}
gparent.right.color=BLACK;
gparent.color=RED;
leftRotate(gparent);
}
}
}
/**
* 返回其双亲节点
* @param node
* @return
*/
private Node parentOf(Node node) {
return node != null ? node.parent : null;
}
/**
* 判断当前节点是否为左子女
* @param node
* @return
*/
private boolean isLeft(Node node) {
return node.parent.left == node;
}
红黑树的删除操作
删除也分为两步：
- 先按照二叉查找树进行删除节点
- 结构调整
根据红黑树的第 4 个规则：
如果当前待删除节点是红色的，它被删除之后对当前树的特性不会造成任何破坏影响。
而如果被删除的节点是黑色的，这就需要进行进一步的调整来保证后续的树结构满足要求
按照二叉查找树删除节点
- 要删除的节点正好是叶子节点，直接删除就 OK 了；
- 只有左孩子或者右孩子，直接把这个孩子上移放到要删除的位置就好了；
- 有两个孩子，就需要选一个合适的孩子节点作为新的根节点，该节点称为 继承节点。
代码实现如下：
private void deleteNode(Node node) {
Node child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ((node.left != null) && (node.right != null)) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
Node 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.root = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = replace.color;
// "被删除节点"是"它的后继节点的父节点"
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.root = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
调整的过程
第一步：
- 兄弟如果是红的，说明孩子都是黑的
- 把兄弟搞成黑的
- 父亲搞成红的
- 左旋转父亲
- 接下来对比旋转后的兄弟
第二步：
情况1 ：兄弟节点的孩子都是黑色 - 把兄弟搞成红的
- continue 下一波
情况2: - 把不是黑的那个孩子搞黑
- 兄弟搞红
- 兄弟右旋转
- 以后对比旋转后的兄弟
- 把兄弟涂成跟父亲一样的颜色
- 然后把父亲搞黑
- 把兄弟的右孩子搞黑
- 父亲节点左旋
- 研究根节点，进入第三步
第三步： - 如果研究的不是根节点并且是黑的，重新进入第一步，研究上一级树；
- 如果研究的是根节点或者这个节点不是黑的，就退出
- 把研究的这个节点涂成黑的。
代码如下：
/**
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 待修正的节点
*/
private void removeFixUp(Node node, Node parent) {
Node other;
while ((node == null || node.color==BLACK) && (node != this.root)) {
if (parent.left == node) {
other = parent.right;
if (other.color==RED) {
// Case 1: x的兄弟w是红色的
other.color=BLACK;
parent.color=RED;
leftRotate(parent);
other = parent.right;
}
if ((other.left == null || other.left.color==BLACK) &&
(other.right == null || other.right.color==BLACK)) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
other.color=RED;
node = parent;
parent = parentOf(node);
} else {
if (other.right == null || other.right.color==BLACK) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
other.left.color=BLACK;
other.color=RED;
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
other.color=parent.color;
parent.color=BLACK;
other.right.color=BLACK;
leftRotate(parent);
node = this.root;
break;
}
} else {
other = parent.left;
if (other.color==RED) {
// Case 1: x的兄弟w是红色的
other.color=BLACK;
parent.color=RED;
rightRotate(parent);
other = parent.left;
}
if ((other.left == null || other.left.color==BLACK) &&
(other.right == null || other.right.color==BLACK)) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
other.color=RED;
node = parent;
parent = parentOf(node);
} else {
if (other.left == null || other.left.color==BLACK) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
other.right.color=BLACK;
other.color=RED;
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
other.color= parent.color;
parent.color=BLACK;
other.left.color=BLACK;
rightRotate(parent);
node = this.root;
break;
}
}
}
if (node != null)
node.color=BLACK;
}
全篇插入和删除完整代码如下：
package com.sankuai.mlx.test.tree;
import java.util.Map;
import java.util.TreeMap;
/**
* Created by tanglei14 on 15/2/2019.
*/
public class RedBlackTree {
private final boolean RED = false;
private final boolean BLACK = true;
private Node root;
public class Node {
private int num;
private Node right;
private Node left;
private Node parent;
private boolean color;//RED :false BLACK:true
public Node(int num, Node right, Node left, Node parent, boolean color) {
this.num = num;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public void setColor(boolean color) {
this.color = color;
}
}
public RedBlackTree() {
root = null;
}
private void insert(Node node) {
if (root == null) {
root = node;
return;
}
Node x = root;
Node y = null;
while (x != null) {
y = x;
if (node.num < x.num) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y.num > node.num) {
y.left = node;
} else {
y.right = node;
}
node.color = RED;
insertFixUp(node);
}
public void insert(int num) {
Node node = new Node(num, null, null, null, BLACK);
// 如果新建结点失败，则返回。
if (node != null)
insert(node);
}
/**
* 插入调整
*
* @param node 插入的节点
*/
private void insertFixUp(Node node) {
Node parent;
Node gparent;
while (node != null && (parent = node.parent) != null && parent.color == RED) {
gparent = parent.parent;
if (gparent.left.color == RED && gparent.right.color == RED) {
gparent.color = RED;
gparent.right.color = BLACK;
gparent.left.color = BLACK;
node = gparent;
} else if (isLeft(parent)) {
if (!isLeft(node)) {
node = parentOf(node);
leftRotate(parent);
}
gparent.left.color = BLACK;
gparent.color = RED;
rightRotate(gparent);
} else {
if (isLeft(node)) {
node = parentOf(node);
rightRotate(parent);
}
gparent.right.color = BLACK;
gparent.color = RED;
leftRotate(gparent);
}
}
}
/**
* 返回其双亲节点
*
* @param node
* @return
*/
private Node parentOf(Node node) {
return node != null ? node.parent : null;
}
/**
* 判断当前节点是否为左子女
*
* @param node
* @return
*/
private boolean isLeft(Node node) {
return node.parent.left == node;
}
private Node rightOf(Node node) {
return node != null ? node.right : null;
}
private Node leftOf(Node node) {
return node != null ? node.left : null;
}
/**
* 左旋
*
* @param node 需要左旋的节点
*/
private void leftRotate(Node node) {
Node right = node.right;
right.parent = node.parent;
node.right = right.left;
right.left = node;
node.parent = right;
if (node.parent == null) {
root = right;
} else {
if (node == right.parent.left) {
right.parent.left = right;
} else {
right.parent.right = right;
}
}
}
/**
* 右旋
*
* @param node 需要进行右旋的节点
*/
private void rightRotate(Node node) {
Node left = node.left;
left.parent = node.parent;
node.left = left.right;
left.right = node;
node.parent = left;
if (node.parent == null) {
root = left;
} else {
if (node == left.parent.left) {
left.parent.left = node;
} else {
left.parent.right = node;
}
}
}
public boolean remove(Integer num) {
Node node = this.getNode(num);
if (node != null) {
this.deleteNode(node);
return true;
}
return false;
}
private void deleteNode(Node node) {
Node child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ((node.left != null) && (node.right != null)) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
Node 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.root = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = replace.color;
// "被删除节点"是"它的后继节点的父节点"
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.root = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/**
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 待修正的节点
*/
private void removeFixUp(Node node, Node parent) {
Node other;
while ((node == null || node.color==BLACK) && (node != this.root)) {
if (parent.left == node) {
other = parent.right;
if (other.color==RED) {
// Case 1: x的兄弟w是红色的
other.color=BLACK;
parent.color=RED;
leftRotate(parent);
other = parent.right;
}
if ((other.left == null || other.left.color==BLACK) &&
(other.right == null || other.right.color==BLACK)) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
other.color=RED;
node = parent;
parent = parentOf(node);
} else {
if (other.right == null || other.right.color==BLACK) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
other.left.color=BLACK;
other.color=RED;
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
other.color=parent.color;
parent.color=BLACK;
other.right.color=BLACK;
leftRotate(parent);
node = this.root;
break;
}
} else {
other = parent.left;
if (other.color==RED) {
// Case 1: x的兄弟w是红色的
other.color=BLACK;
parent.color=RED;
rightRotate(parent);
other = parent.left;
}
if ((other.left == null || other.left.color==BLACK) &&
(other.right == null || other.right.color==BLACK)) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
other.color=RED;
node = parent;
parent = parentOf(node);
} else {
if (other.left == null || other.left.color==BLACK) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
other.right.color=BLACK;
other.color=RED;
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
other.color= parent.color;
parent.color=BLACK;
other.left.color=BLACK;
rightRotate(parent);
node = this.root;
break;
}
}
}
if (node != null)
node.color=BLACK;
}
private void setParent(Node child, Node parent) {
if (child != null) {
child.parent = parent;
}
}
private Node getNode(Integer num) {
Node node = root;
while (node != null) {
if (node.num > num) {
node = node.left;
} else if (node.num < num) {
node = node.right;
} else {
return node;
}
}
return null;
}
/**
* 返回指定的继任者,如果没有返回null
*/
private Node successor(Node t) {
if (t == null)
return null;
else if (t.right != null) {
Node p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Node p = t.parent;
Node ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
}
