一、简介
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树.
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。
由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
二、性质
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
三、红黑树可视化
借助可视化红黑树更容易理解其原理。
注：本站改版使用二叉查找树定义一，英文原版使用二叉查找树定义二。
本站改版访问地址：https://wjx.wiki/usr/uploads/2018/10/RedBlack.html
英文原版访问地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
四、操作
因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量O(logn)的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为O(logn)次。
新增
我们首先以二叉查找树的方法增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换和树旋转来调整。）下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意：
- 性质1和性质3总是保持着。
- 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
- 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。
将新增操作分为两步：
第一步 新增节点。按照二叉查找树定义一，即左<根<右，插入即可。
第二步 旋转变色。需要根据如下情形，作相应的处理。
-
情形1
新节点位于树的根上，没有父节点，直接涂为黑色，即可完成新增操作。
-
情形2
新节点的父节点是黑色（新节点默认是红色），则无需额外处理，即可完成新增操作。
-
情形3
如果父节点和叔父节点都是红色。则将二者涂为黑色，祖父节点涂为红色。若祖父节点的父节点也是红色，会违反性质4，需要在祖父节点上递归检查处理各种情形；若祖父节点的父节点为黑色，则无需额外处理，即可完成新增操作。
-
情形4
父节点是红色而叔父节点是黑色或缺少，并且新节点是右子节点而父节点是左子节点。此时，需要父节点绕新节点进行左旋转。接着按情形6处理。
-
情形5
父节点是红色而叔父节点是黑色或缺少，并且新节点是左子节点而父节点是右子节点。此时，需要父节点绕新节点进行右旋转。接着按情形7处理。
-
情形6
父节点是红色而叔父节点是黑色或缺少，并且新节点和父节点均为左子节点。此时，需要祖父节点绕父节点进行右旋转，并互换颜色。即可完成新增操作。
- 情形7
父节点是红色而叔父节点是黑色或缺少，并且新节点和父节点均为右子节点。此时，需要祖父节点绕父节点进行左旋转，并互换颜色。即可完成新增操作。
至此便完成了红黑树的新增操作。
删除
如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题（为了表述方便，这里所指的儿子，为非叶子节点的儿子）。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值转移到要删除的节点中（如在这里所展示的那样）。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值（没有复制颜色），不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。
在本文余下的部分中，我们只需要讨论删除只有一个儿子的节点（如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子）。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。
需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。下面就可能出现的所有情形逐一处理。
同样将删除操作分为两步：
第一步 删除节点。
-
删除节点没有子节点，直接删除。若删除节点是黑色，则需通过旋转变色来修补缺失的黑色节点；若删除节点是红色，则无需处理，即可完成删除操作。
-
删除节点有一个子节点，直接删除。并用子节点替换删除节点位置，且颜色换成删除节点的颜色（黑色），即可完成删除操作。
- 删除节点有两个节点时，先将前驱节点的值复制到删除节点，且前驱节点若是有子节点，则将前驱节点的父节点设置为前驱节点子节点的父节点，然后删除掉前驱节点。若前驱节点是黑色，则需要通过旋转变色来修补缺失的黑色节点；前驱节点是红色则无需处理。
第二步 旋转变色。需要根据如下情形，作相应的处理。
-
情形1
双黑色节点的兄弟节点及2个侄子节点均是黑色(叶子节点默认是黑色)，推高黑色水平。即若父节点是红色，则涂为黑色；若父节点是黑色，则涂为双黑色，继续递归处理检查各种情形。
-
情形2
双黑色节点的兄弟节点是红色。 则通过父节点绕兄弟节点旋转，使兄弟节点变为黑色。继续递归处理检查各种情形。
-
情形3
双黑色节点的兄弟节点是黑色。但双黑色节点是左子节点且右侄节点是黑色。 则通过兄弟节点绕左侄节点进行右旋转，使右侄节点变红。继续递归处理检查各种情形
-
情形4
双黑色节点的兄弟节点是黑色。但双黑色节点是右子节点且左侄节点是黑色。 则通过兄弟节点绕右侄节点进行左旋转，使左侄节点变红。继续递归处理检查各种情形。
-
情形5
双黑色节点的兄弟节点是黑色。但双黑色节点是左子节点且右侄节点是红色。则通过父节点绕兄弟节点进行左旋转。即可完成删除操作。
- 情形6
双黑色节点的兄弟节点是黑色。但双黑色节点是右子节点且左侄节点是红色。则通过父节点绕兄弟节点进行右旋转。即可完成删除操作。
至此便完成了红黑树的删除操作。
因为使用的是二叉查找树的定义一，因此根据左<根<右,通过递归可以快速查找到所需节点数据。同时，插入时若节点key相等即可作为更新操作。至此便完成了红黑树的增删改查。
五、Java版红黑树手撸源码
1、颜色枚举类
package com.example.demo.RedBlackTree;
public enum Color {
RED,BLACK,DOUBLEBLACK
}2、红黑树节点类
package com.example.demo.RedBlackTree;
import lombok.Data;
@Data
public class RedBlackNode {
private int data;
private Color color = Color.RED;
private RedBlackNode parentNode;
private RedBlackNode leftNode;
private RedBlackNode rightNode;
public RedBlackNode() {
}
public RedBlackNode(Color color) {
this.color = color;
}
public RedBlackNode(int data, RedBlackNode parentNode, RedBlackNode leftNode, RedBlackNode rightNode) {
this.data = data;
this.parentNode = parentNode;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
public RedBlackNode(int data, Color color, RedBlackNode parentNode, RedBlackNode leftNode, RedBlackNode rightNode) {
this.data = data;
this.color = color;
this.parentNode = parentNode;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}3、红黑树主类
package com.example.demo.RedBlackTree;
public class RedBlackTree {
private RedBlackNode treeRoot;
public void insert(int data) {
if (treeRoot == null) {
//根据性质2,直接生成黑色根节点即可！
treeRoot = new RedBlackNode(data, Color.BLACK, null, null, null);
} else {
insertData(data, this.treeRoot);
}
}
public void insertArray(int... datas) {
for (int data : datas) {
insert(data);
}
}
public void print() {
StringBuilder sb = new StringBuilder();
getAllDataByLDR(sb, this.treeRoot);
System.out.println(sb.toString());
}
/**
* 递归查找待插入的位置
*
* @param newData
* @param tree
*/
private void insertData(int newData, RedBlackNode tree) {
int treeData = tree.getData();
if (newData < treeData) {
if (tree.getLeftNode() == null) {
RedBlackNode newNode = new RedBlackNode(newData, tree, null, null);
tree.setLeftNode(newNode);
fixDoubleRed(tree.getLeftNode());
} else {
insertData(newData, tree.getLeftNode());
}
} else if (newData > treeData) {
if (tree.getRightNode() == null) {
RedBlackNode newNode = new RedBlackNode(newData, tree, null, null);
tree.setRightNode(newNode);
fixDoubleRed(tree.getRightNode());
} else {
insertData(newData, tree.getRightNode());
}
} else {
System.out.println("更新操作！");
}
}
public boolean delete(int data) {
return deleteData(data, this.treeRoot);
}
public void deleteArray(int... datas) {
for (int data : datas) {
delete(data);
}
}
/**
* 递归查找待删除节点
*
* @param data
* @param tree
* @return true 则找到并删除节点，false 未找到节点。
*/
private boolean deleteData(int data, RedBlackNode tree) {
if (tree == null) {
return false;
}
if (data == tree.getData()) {
deleteAndFixNode(tree);
return true;
} else if (data < tree.getData()) {
return deleteData(data, tree.getLeftNode());
} else {
return deleteData(data, tree.getRightNode());
}
}
/**
* 删除节点
*
* @param tree 待删除的节点
*/
private void deleteAndFixNode(RedBlackNode tree) {
RedBlackNode parentNode = tree.getParentNode();
RedBlackNode leftNode = tree.getLeftNode();
RedBlackNode rightNode = tree.getRightNode();
boolean isNeedFix = tree.getColor() == Color.BLACK;
if (leftNode == null && rightNode == null) {
if (tree == treeRoot) {
treeRoot = null;
} else if (isLeftChild(tree)) {
parentNode.setLeftNode(null);
if (isNeedFix) {
RedBlackNode doubleBlackNode = addDoubleBlackNode(parentNode, true);
fixExtraBlack(doubleBlackNode);
}
} else {
parentNode.setRightNode(null);
if (isNeedFix) {
RedBlackNode doubleBlackNode = addDoubleBlackNode(parentNode, false);
fixExtraBlack(doubleBlackNode);
}
}
} else if (leftNode == null) {
rotateLeft(rightNode);
rightNode.setColor(Color.BLACK);
rightNode.setLeftNode(null);
} else if (rightNode == null) {
rotateRight(leftNode);
leftNode.setColor(Color.BLACK);
leftNode.setRightNode(null);
} else {
RedBlackNode precursorNode = getPrecursorNode(tree.getLeftNode());
tree.setData(precursorNode.getData());
if (precursorNode.getLeftNode() != null) {
rotateRight(precursorNode.getLeftNode());
precursorNode.getParentNode().setColor(Color.BLACK);
if (isLeftChild(precursorNode)) {
precursorNode.getParentNode().setLeftNode(null);
} else {
precursorNode.getParentNode().setRightNode(null);
}
} else {
RedBlackNode precursorParentNode = precursorNode.getParentNode();
isNeedFix = precursorNode.getColor() == Color.BLACK;
if (isLeftChild(precursorNode)) {
precursorParentNode.setLeftNode(null);
if (isNeedFix) {
RedBlackNode doubleBlackNode = addDoubleBlackNode(precursorParentNode, true);
fixExtraBlack(doubleBlackNode);
}
} else {
precursorParentNode.setRightNode(null);
if (isNeedFix) {
RedBlackNode doubleBlackNode = addDoubleBlackNode(precursorParentNode, false);
fixExtraBlack(doubleBlackNode);
}
}
}
}
}
/**
* 用双黑色节点代替被删除的节点
*
* @param parentNode 双黑色节点的父节点
* @param isLeftChild 是否为左子节点
* @return 双黑色节点
*/
private RedBlackNode addDoubleBlackNode(RedBlackNode parentNode, boolean isLeftChild) {
RedBlackNode doubleBlackNode = new RedBlackNode(Color.DOUBLEBLACK);
doubleBlackNode.setParentNode(parentNode);
if (isLeftChild) {
parentNode.setLeftNode(doubleBlackNode);
} else {
parentNode.setRightNode(doubleBlackNode);
}
return doubleBlackNode;
}
/**
* 获取前驱节点 <br/>
* 可用while实现
*
* @param node 左子树
* @return 前驱节点
*/
private RedBlackNode getPrecursorNode(RedBlackNode node) {
if (node.getRightNode() != null) {
return getPrecursorNode(node.getRightNode());
}
return node;
}
/**
* 通过旋转变色修复双黑色节点
*
* @param doubleBlackNode 双黑色节点
*/
private void fixExtraBlack(RedBlackNode doubleBlackNode) {
if (doubleBlackNode == treeRoot) {
doubleBlackNode.setColor(Color.BLACK);
return;
}
RedBlackNode parentNode = doubleBlackNode.getParentNode();
RedBlackNode sibling = parentNode.getLeftNode();
if (isLeftChild(doubleBlackNode)) {
sibling = parentNode.getRightNode();
}
RedBlackNode siblingLeftNode = sibling.getLeftNode();
RedBlackNode siblingRightNode = sibling.getRightNode();
if (isBlackNode(sibling) && isBlackNode(siblingLeftNode) && isBlackNode(siblingRightNode)) {
fixDoubleBlackNode(doubleBlackNode);
if (pushBlack(sibling)) {
fixExtraBlack(parentNode);
}
} else if (!isBlackNode(sibling)) {
if (isLeftChild(sibling)) {
rotateRight(sibling);
} else {
rotateLeft(sibling);
}
sibling.setColor(Color.BLACK);
parentNode.setColor(Color.RED);
fixExtraBlack(doubleBlackNode);
} else if (isLeftChild(doubleBlackNode) && isBlackNode(siblingRightNode)) {
rotateRight(siblingLeftNode);
sibling.setColor(Color.RED);
sibling.getParentNode().setColor(Color.BLACK);
fixExtraBlack(doubleBlackNode);
} else if (!isLeftChild(doubleBlackNode) && isBlackNode(siblingLeftNode)) {
rotateLeft(siblingRightNode);
sibling.setColor(Color.RED);
sibling.getParentNode().setColor(Color.BLACK);
fixExtraBlack(doubleBlackNode);
} else if (isLeftChild(doubleBlackNode) && !isBlackNode(siblingRightNode)) {
Color color = sibling.getParentNode().getColor();
rotateLeft(sibling);
if (color == Color.RED) {
sibling.setColor(Color.RED);
sibling.getLeftNode().setColor(Color.BLACK);
}
sibling.getRightNode().setColor(Color.BLACK);
fixDoubleBlackNode(sibling.getLeftNode().getLeftNode());
} else if (!isLeftChild(doubleBlackNode) && !isBlackNode(siblingLeftNode)) {
Color color = sibling.getParentNode().getColor();
rotateRight(sibling);
if (color == Color.RED) {
sibling.setColor(Color.RED);
sibling.getRightNode().setColor(Color.BLACK);
}
sibling.getLeftNode().setColor(Color.BLACK);
fixDoubleBlackNode(sibling.getRightNode().getRightNode());
}
}
/**
* 叶子结点默认为黑色
*
* @param node
* @return
*/
private boolean isBlackNode(RedBlackNode node) {
return (node == null || node.getColor() == Color.BLACK);
}
/**
* 双黑色涂为黑色，若双黑色节点无子节点，则清除双黑色节点。
*
* @param doubleBlackNode
*/
private void fixDoubleBlackNode(RedBlackNode doubleBlackNode) {
if (isLeftChild(doubleBlackNode)) {
doubleBlackNode.setColor(Color.BLACK);
if (doubleBlackNode.getData() == 0 && doubleBlackNode.getLeftNode() == null && doubleBlackNode.getRightNode() == null) {
doubleBlackNode.getParentNode().setLeftNode(null);
}
} else {
doubleBlackNode.setColor(Color.BLACK);
if (doubleBlackNode.getData() == 0 && doubleBlackNode.getLeftNode() == null && doubleBlackNode.getRightNode() == null) {
doubleBlackNode.getParentNode().setRightNode(null);
}
}
}
/**
* 推高黑水平，父节点红转黑、黑转双黑，兄弟节点由黑转红。
*
* @param sibling 兄弟节点
* @return true 即需要修复双黑节点
*/
private boolean pushBlack(RedBlackNode sibling) {
sibling.setColor(Color.RED);
if (sibling.getParentNode().getColor() == Color.BLACK) {
sibling.getParentNode().setColor(Color.DOUBLEBLACK);
return true;
}
sibling.getParentNode().setColor(Color.BLACK);
return false;
}
/**
* 根据性质4，需要通过旋转变色修复可能出现的连续的两个红色节点
*
* @param currentNode
*/
private void fixDoubleRed(RedBlackNode currentNode) {
RedBlackNode parentNode = currentNode.getParentNode();
if (parentNode.getColor() == Color.RED) {
RedBlackNode grandFatherNode = parentNode.getParentNode();
RedBlackNode uncleNode = grandFatherNode.getLeftNode();
if (isLeftChild(parentNode)) {
uncleNode = grandFatherNode.getRightNode();
}
if (uncleNode != null && uncleNode.getColor() == Color.RED) {
parentNode.setColor(Color.BLACK);
uncleNode.setColor(Color.BLACK);
grandFatherNode.setColor(Color.RED);
if (grandFatherNode == treeRoot) {
grandFatherNode.setColor(Color.BLACK);
} else if (grandFatherNode.getParentNode().getColor() == Color.RED) {
fixDoubleRed(grandFatherNode);
}
} else {
if (isLeftChild(currentNode) && !isLeftChild(parentNode)) {
rotateRight(currentNode);
parentNode = currentNode;
} else if (!isLeftChild(currentNode) && isLeftChild(parentNode)) {
rotateLeft(currentNode);
parentNode = currentNode;
}
if (isLeftChild(currentNode)) {
rotateRight(parentNode);
} else {
rotateLeft(parentNode);
}
grandFatherNode.setColor(Color.RED);
parentNode.setColor(Color.BLACK);
}
}
}
/**
* 左旋转
*
* @param centerNode 圆心节点
*/
private void rotateLeft(RedBlackNode centerNode) {
RedBlackNode parentNode = centerNode.getParentNode();
RedBlackNode grandFatherNode = parentNode.getParentNode();
RedBlackNode leftNode = centerNode.getLeftNode();
if (parentNode == treeRoot) {
centerNode.setParentNode(null);
treeRoot = centerNode;
} else {
if (isLeftChild(parentNode)) {
grandFatherNode.setLeftNode(centerNode);
} else {
grandFatherNode.setRightNode(centerNode);
}
centerNode.setParentNode(grandFatherNode);
}
if (leftNode != null) {
leftNode.setParentNode(parentNode);
}
centerNode.setLeftNode(parentNode);
parentNode.setRightNode(leftNode);
parentNode.setParentNode(centerNode);
}
/**
* 右旋转
*
* @param centerNode 圆心节点
*/
private void rotateRight(RedBlackNode centerNode) {
RedBlackNode parentNode = centerNode.getParentNode();
RedBlackNode grandFatherNode = parentNode.getParentNode();
RedBlackNode rightNode = centerNode.getRightNode();
if (parentNode == treeRoot) {
centerNode.setParentNode(null);
treeRoot = centerNode;
} else {
if (isLeftChild(parentNode)) {
grandFatherNode.setLeftNode(centerNode);
} else {
grandFatherNode.setRightNode(centerNode);
}
centerNode.setParentNode(grandFatherNode);
}
if (rightNode != null) {
rightNode.setParentNode(parentNode);
}
centerNode.setRightNode(parentNode);
parentNode.setLeftNode(rightNode);
parentNode.setParentNode(centerNode);
}
/**
* 是否左子节点
*
* @param node
* @return
*/
private boolean isLeftChild(RedBlackNode node) {
return node.getParentNode().getLeftNode() == node;
}
/**
* 中序遍历
*
* @param sb
* @param tree
*/
public void getAllDataByLDR(StringBuilder sb, RedBlackNode tree) {
if (tree == null) {
return;
}
RedBlackNode leftNode = tree.getLeftNode();
RedBlackNode rightNode = tree.getRightNode();
if (leftNode != null) {
getAllDataByLDR(sb, leftNode);
}
sb.append(tree.getData());
sb.append(":");
sb.append(tree.getColor());
sb.append(" ");
if (rightNode != null) {
getAllDataByLDR(sb, rightNode);
}
// 另一种中序遍历。
/*if (tree == null) {
return;
} else {
getAllDataByLDR(sb, tree.getLeftNode());
sb.append(tree.getData() + " ");
getAllDataByLDR(sb, tree.getRightNode());
}*/
}
/**
* 前序遍历
*
* @param sb
* @param tree
*/
public void getAllDataByDLR(StringBuilder sb, RedBlackNode tree) {
if (tree == null) {
return;
}
RedBlackNode leftNode = tree.getLeftNode();
RedBlackNode rightNode = tree.getRightNode();
sb.append(tree.getData());
sb.append(":");
sb.append(tree.getColor());
sb.append(" ");
if (leftNode != null) {
getAllDataByDLR(sb, leftNode);
}
if (rightNode != null) {
getAllDataByDLR(sb, rightNode);
}
}
public void update(int arg) {
}
public void query(int arg) {
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
tree.insertArray(67, 35, 55, 64, 1, 37, 7, 73, 68, 9, 10, 15, 69, 80);
tree.print();
tree.delete(69);
tree.deleteArray(73, 68, 9, 10, 15, 69, 80, 35, 55, 64);
tree.print();
}
}
本文由 Administrator 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站部分文章采集自互联网，因某些原因未注明出处，如有侵权，请留言告知。