红黑树的性质
红黑树是一课二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以使RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。
树中每个结点包含5个属性：color、key、left、right、parent。如果一个结点没有子结点或父结点，则该结点相应属性的值为null。一棵红黑树是满足下面红黑性质的二叉搜索树：
- 每个结点或是红色的，或是黑色的；
- 根结点是黑色的；
- 每个叶结点是黑色的；
- 如果一个结点是红色的，则它的两个子结点都是黑色的；
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
为了便于处理红黑树代码中的边界条件，可以使用一个哨兵来代表null。对于一棵红黑树，哨兵是一个与树中的普通结点有相同属性的对象。它的color属性为BLACK，其他属性可以设置为任意值。如下图所示为一棵使用了哨兵的红黑树示例。
旋转
当对树执行插入或操作时，对树做了修改，所做的修改可能会导致树不满足红黑树的性质，因此需要进行旋转来维护红黑树的性质。旋转可分为左旋和右旋。下图展示了一棵子树旋转后的结果。
java代码实现
下面是使用java简单实现了红黑树，以及红黑树的插入和删除操作。
/**
* 数据结构-红黑树
*/
public class RBTree {
/**
* 哨兵
*/
private final Node sentinel = new Node(Color.BLACK);
/**
* 根节点
*/
private Node root = sentinel;
/**
* 根据关键字搜索节点
*
* @param key 关键字
* @return key所在的节点
*/
public Node search(int key) {
Node node = root;
while (node != null && key != node.key) {
// 如果key小于当前节点的key，则往左孩子节点找，否则往右孩子节点找
if (key < node.key) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
/**
* 插入关键字为key的节点
*
* @param key 关键字
*/
public void insert(int key) {
Node y = sentinel;
Node x = root;
while (x != sentinel) {
y = x;
if (key < x.key) {
x = x.left;
} else {
x = x.right;
}
}
Node newNode = new Node();
newNode.key = key;
newNode.parent = y;
if (y == sentinel) {
root = newNode;
} else if (key < y.key) {
y.left = newNode;
} else {
y.right = newNode;
}
newNode.left = sentinel;
newNode.right = sentinel;
newNode.color = Color.RED;
insertFixUp(newNode);
}
/**
* 删除关键字为key的节点
*
* @param key 关键字
*/
public void delete(int key) {
Node node = search(key);
Node y = node;
Color yOriginalColor = y.color;
Node x;
if (node.left == sentinel) {
x = node.right;
transplant(node, node.right);
} else if (node.right == sentinel) {
x = node.left;
transplant(node, node.left);
} else {
y = min(node.right);
yOriginalColor = y.color;
x = y.right;
if (y.parent == node) {
x.parent = y;
} else {
transplant(y, y.right);
y.right = node.right;
y.right.parent = y;
}
transplant(node, y);
y.left = node.left;
y.left.parent = y;
y.color = node.color;
}
if (yOriginalColor == Color.BLACK) {
deleteFixUp(x);
}
}
/**
* 获取以node为根的子树中key最小的节点
*
* @param node 子树根节点
* @return 子树中key最小的节点
*/
public Node min(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
public Node getRoot() {
return root;
}
/**
* 删除一个节点后，维护树的红黑性质
*
* @param node 节点
*/
private void deleteFixUp(Node node) {
while (node != root && node.color == Color.BLACK) {
if (node == node.parent.left) {
Node w = node.parent.right;
if (w.color == Color.RED) {
w.color = Color.BLACK;
node.parent.color = Color.RED;
leftRotate(node.parent);
w = node.parent.right;
}
if (w.left.color == Color.BLACK && w.right.color == Color.BLACK) {
w.color = Color.RED;
node = node.parent;
} else if (w.right.color == Color.BLACK) {
w.left.color = Color.BLACK;
w.color = Color.RED;
rightRotate(w);
w = node.parent.right;
}
w.color = node.parent.color;
node.parent.color = Color.BLACK;
w.right.color = Color.BLACK;
leftRotate(node.parent);
node = root;
} else {
Node w = node.parent.left;
if (w.color == Color.RED) {
w.color = Color.BLACK;
node.parent.color = Color.RED;
leftRotate(node.parent);
w = node.parent.left;
}
if (w.right.color == Color.BLACK && w.left.color == Color.BLACK) {
w.color = Color.RED;
node = node.parent;
} else if (w.left.color == Color.BLACK) {
w.right.color = Color.BLACK;
w.color = Color.RED;
leftRotate(w);
w = node.parent.left;
}
w.color = node.parent.color;
node.parent.color = Color.BLACK;
w.left.color = Color.BLACK;
rightRotate(node.parent);
node = root;
}
}
node.color = Color.BLACK;
}
/**
* 将node1替换成node2，以支持删除操作
*
* @param node1 节点1
* @param node2 节点2
*/
private void transplant(Node node1, Node node2) {
if (node1.parent == sentinel) {
root = node2;
} else if (node1 == node1.parent.left) {
node1.parent.left = node2;
} else {
node1.parent.right = node2;
}
node2.parent = node1.parent;
}
/**
* 插入一个节点后，维护树的红黑性质
*
* @param node 插入的节点
*/
private void insertFixUp(Node node) {
while (node.parent.color == Color.RED) {
if (node.parent == node.parent.parent.left) {
Node temp = node.parent.parent.right;
if (temp.color == Color.RED) {
node.parent.color = Color.BLACK;
temp.color = Color.BLACK;
node.parent.parent.color = Color.RED;
node = node.parent.parent;
} else if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
} else {
node.parent.color = Color.BLACK;
node.parent.parent.color = Color.RED;
rightRotate(node.parent.parent);
}
} else {
Node temp = node.parent.parent.left;
if (temp.color == Color.RED) {
node.parent.color = Color.BLACK;
temp.color = Color.BLACK;
node.parent.parent.color = Color.RED;
node = node.parent.parent;
} else if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
} else {
node.parent.color = Color.BLACK;
node.parent.parent.color = Color.RED;
leftRotate(node.parent.parent);
}
}
}
root.color = Color.BLACK;
}
/**
* 在节点node上进行左旋操作
*
* @param node 节点
*/
private void leftRotate(Node node) {
Node right = node.right;
// 将node的右子树的左子树放到node的右子树位置
node.right = right.left;
if (right.left != sentinel) {
right.left.parent = node;
}
// 设置node的右子树的父节点为node的父节点
right.parent = node.parent;
if (node.parent == sentinel) {
root = right;
} else if (node == node.parent.left) {
node.parent.left = right;
} else {
node.parent.right = right;
}
// 将node放到node的右子树的左子树位置
right.left = node;
node.parent = right;
}
/**
* 在节点node上进行右旋操作
*
* @param node 节点
*/
private void rightRotate(Node node) {
Node left = node.left;
node.left = left.right;
if (left.right != sentinel) {
left.right.parent = node;
}
left.parent = node.parent;
if (node.parent == sentinel) {
root = left;
} else if (node == node.parent.right) {
node.parent.right = left;
} else {
node.parent.left = left;
}
left.right = node;
node.parent = left;
}
private enum Color {
/**
* 红色
*/
RED,
/**
* 黑色
*/
BLACK
}
public static class Node {
/**
* 节点颜色
*/
private Color color;
/**
* 节点关键字
*/
private int key;
/**
* 左孩子节点
*/
private Node left;
/**
* 右孩子节点
*/
private Node right;
/**
* 父节点
*/
private Node parent;
private Node() {
}
private Node(Color color) {
this.color = color;
}
public Color getColor() {
return color;
}
public int getKey() {
return key;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public Node getParent() {
return parent;
}
}
}
