红黑树
1 红黑树-简介
1.1 定义
- 定义:红黑树是一种每个节点都带有颜色属性的二叉查找树,节点颜色为红色或黑色。
- 发明:红黑树由Rudolf Bayer在1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),后由Guibas和Robert Sedgewick修改为现今的“红黑树”。
1.2 基本性质
- 节点颜色:每个节点是红色或黑色。
- 根节点颜色:根节点是黑色。
- 叶子节点:叶子节点(NIL节点,空节点)是黑色。
- 红色节点:如果一个节点是红色的,则它的两个子节点都是黑色的(这保证了路径上不会有两个连续的红色节点)。
- 黑色节点路径:从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树保证了在最坏情况下的基本操作(查找、插入、删除)的时间复杂度为O(log n),其中n是树中元素的数目。这是因为红黑树的性质确保了树的高度不会过高,从而保证了操作的效率。
1.3 插入节点的步骤
查找插入位置
- 对红黑树进行二分查找,直到找到新节点的插入位置(即红黑树的叶子节点)。
插入节点并设为红色
- 将新节点插入到找到的位置,并将节点颜色设为红色。
调整红黑树以恢复性质
- 如果新节点是根节点
- 直接将新节点颜色改为黑色,因为根节点必须是黑色的。
- 如果新节点的父节点是黑色
- 不需要进行任何调整,因为新节点的插入没有违反红黑树的性质。
- 如果新节点的父节点是红色
叔叔节点也是红色
- 将父节点和叔叔节点都设置为黑色。
- 将祖父节点设置为红色。
- 将祖父节点视为新的插入节点,递归进行上述检查。
- 在这里插入图片描述
叔叔节点是黑色
左左插入(新节点在父节点的左子树,且父节点在祖父节点的左子树)
- 将父节点设置为黑色。
- 将祖父节点设置为红色。
- 对祖父节点进行右旋。
左右插入(新节点在父节点的右子树,且父节点在祖父节点的左子树)
- 对父节点进行左旋,这样原来的父节点就变成了新节点的子节点,且新节点成为了其父节点的左子节点。
- 按照左左插入的情况处理新的父子关系。
右右插入(新节点在父节点的右子树,且父节点在祖父节点的右子树)
- 这是左左插入的镜像情况,处理方式相同,但方向相反(即将父节点设为黑色,祖父节点设为红色,并对祖父节点进行左旋)。
右左插入(新节点在父节点的左子树,且父节点在祖父节点的右子树)
- 对父节点进行右旋,这样原来的父节点就变成了新节点的子节点,且新节点成为了其父节点的右子节点。
- 按照右右插入的情况处理新的父子关系。
- 如果新节点是根节点
1.4 删除节点的步骤
一、总体流程
在删除节点时,需依次查看删除节点的颜色、兄弟节点的颜色、侄子节点的颜色(先远侄子,再近侄子),最后是父节点的颜色。
顺序为:当前节点->兄弟节点->远侄子节点->近侄子节点->父节点。
(补充说明:删除节点分为叶子节点和非叶子节点两种情况。若为非叶子节点,则先与子节点的值进行交换,直至转化为删除叶子节点的情况。)
二、具体情况分析
删除的是叶子节点且为红色
- 可直接删除,无需后续处理。
删除的是叶子节点且为黑色
- 需进一步处理。
删除节点下有一个子节点
- 将当前删除的节点与子节点的值进行交换,从而转化为删除叶子节点的情况。
- 3.1 若转化后的叶子节点为红色,对应情况 1,直接删除。
- 3.2 若转化后的叶子节点为黑色,对应情况 2,进行后续处理。
- 将当前删除的节点与子节点的值进行交换,从而转化为删除叶子节点的情况。
删除节点有两个子节点
将当前节点与后续节点中的一个节点值进行交换,转变为删除叶子节点的情况。
- 4.1 若转变后没有叶子节点,对应情况 1 或 2。
- 4.2 若转变后有一个叶子节点,对应情况 3。
- 4.3 若转变后有两个叶子节点,对应情况 4。
经过上述步骤的转换,情况已转化为删除叶子节点。其中叶子节点为红色的情况已处理完毕,接下来重点关注删除叶子节点为黑色的情形。
删除的叶子节点为黑色
5.1 删除节点的兄弟节点为红色若删除节点为左节点:将父节点和兄弟节点颜色互换,然后对父节点进行左旋。
若删除节点为右节点:将父节点和兄弟节点颜色互换,然后对父节点进行右旋。
5.2 删除节点兄弟节点为黑色,远侄子节点为红色
若删除节点为左节点:此时删除节点的远侄子节点为兄弟节点的右节点。将父节点和兄弟节点颜色对调,并把远侄子节点变成黑色,接着对父节点进行左旋,最后删除当前需要删除的节点。
若删除节点为右节点:此时删除节点的远侄子节点为兄弟节点的左节点。将父节点和兄弟节点颜色对调,并把远侄子节点变成黑色,接着对父节点进行右旋,最后删除当前需要删除的节点。
5.3 删除节点兄弟节点是黑色,近侄子节点是红色
若删除节点为左节点:近侄子节点和兄弟节点颜色互换,并将近侄子节点进行右旋,此时转变为 5.2 情况。
若删除节点为右节点:近侄子节点和兄弟节点颜色互换,将近侄子节点进行左旋,此时转变为 5.2 情况。
5.4 父节点是红色,兄弟节点和兄弟节点的两个孩子(只能是空节点)都是黑色的情况
- 将父节点变成黑色,兄弟节点变成红色,然后删除当前节点。
5.5 父节点和兄弟节点及兄弟节点的两个子节点,都是黑色
- 将兄弟节点变成红色,删除节点。这样删除节点后,父节点的左右两个黑色节点数相等,但经过祖父节点的路径黑色节点数少 1 个。此时,以父节点为起始节点(无需再处理原删除节点),继续根据上述情况进行平衡操作,判断所属情况并做相应调整,如此一直向上,直至新的起始节点为根节点。
2 红黑树代码示例
2.1 插入
核心代码
/**
* 新增节点
* @param data
*/
public void addNode(Integer data) {
MyRedBlackTreeNode<Integer> node = new MyRedBlackTreeNode<>(data);
addNode(root,node);
fixTree(node); // 核心方法,用于调整红黑树
}
/**
* 新增节点:递归函数
* @param root
* @param node
*/
private void addNode(MyRedBlackTreeNode<Integer> root, MyRedBlackTreeNode<Integer> node) {
if (node.data <= root.data){
if (root.left == null){
root.left = node;
node.parent = root;
}else{
addNode(root.left, node);
}
} else {
if (root.right == null){
root.right = node;
node.parent = root;
}else{
addNode(root.right, node);
}
}
}
/**
* 红黑树调整
* @param node
*/
private void fixTree(MyRedBlackTreeNode<Integer> node) {
// 第一种情况:node节点作为根节点,将当前节点修改为黑色
// 第二种情况:node节点的父节点为黑色节点,不需要做调整
if (node.parent == null || node.parent.color == MyRedBlackTreeNode.BLACK) {
return;
}
while (node.parent != null && node.parent.color == MyRedBlackTreeNode.RED){
if (node.parent.parent == null){
node.parent.color = MyRedBlackTreeNode.BLACK;
continue;
}
// 第三种情况:node节点的父节点为红色
if (node.parent.parent.left == node.parent){ // 父节点在祖父节点的左子树
MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.right; // 获取到叔叔节点
// 3.1 叔叔节点为红色
// - 将父节点和叔叔节点都设置为黑色。
//- 将祖父节点设置为红色。
//- 将祖父节点视为新的插入节点,递归进行上述检查。
if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
node.parent.color = MyRedBlackTreeNode.BLACK;
uncleNode.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
node = node.parent.parent;
continue;
}
// 3.2 叔叔节点为黑色
// 3.2.2 新节点在父节点的右子树,且父节点在祖父节点的左子树
// - 对父节点进行左旋,这样原来的父节点就变成了新节点的子节点,且新节点成为了其父节点的左子节点。
// - 按照左左插入的情况处理新的父子关系。
if (node.parent.right == node){
node = node.parent;
leftRotate(node);
}
// 3.2.1 新节点在父节点的左子树,且父节点在祖父节点的左子树
// - 将父节点设置为黑色。
//- 将祖父节点设置为红色。
//- 对祖父节点进行右旋。
node.parent.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
rightRotate(node.parent.parent);
} else if (node.parent.parent.right == node.parent) { // 父节点在祖父节点的右子树
MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.left; // 获取到叔叔节点
// 3.1 叔叔节点为红色
// - 将父节点和叔叔节点都设置为黑色。
//- 将祖父节点设置为红色。
//- 将祖父节点视为新的插入节点,递归进行上述检查。
if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
node.parent.color = MyRedBlackTreeNode.BLACK;
uncleNode.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
node = node.parent.parent;
continue;
}
// 3.2 叔叔节点为黑色
// 3.2.4 新节点在父节点的右子树,且父节点在祖父节点的左子树
if (node.parent.left == node){
node = node.parent;
rightRotate(node);
}
// 3.2.3 新节点在父节点的左子树,且父节点在祖父节点的右子树
// 父节点设为黑色,祖父节点设为红色,并对祖父节点进行左旋
node.parent.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
leftRotate(node.parent.parent);
}
}
root.color = MyRedBlackTreeNode.BLACK;
}
完整代码
/**
* 红黑树
*/
public class MyRedBlackTreeDemo {
private MyRedBlackTreeNode<Integer> root;
public MyRedBlackTreeDemo(Integer data) {
root = new MyRedBlackTreeNode<>(data);
root.setColor(MyRedBlackTreeNode.BLACK); // 根节点为黑色
}
/**
* 新增节点
* @param data
*/
public void addNode(Integer data) {
MyRedBlackTreeNode<Integer> node = new MyRedBlackTreeNode<>(data);
addNode(root,node);
fixTree(node); // 核心方法,用于调整红黑树
}
/**
* 新增节点:递归函数
* @param root
* @param node
*/
private void addNode(MyRedBlackTreeNode<Integer> root, MyRedBlackTreeNode<Integer> node) {
if (node.data <= root.data){
if (root.left == null){
root.left = node;
node.parent = root;
}else{
addNode(root.left, node);
}
} else {
if (root.right == null){
root.right = node;
node.parent = root;
}else{
addNode(root.right, node);
}
}
}
/**
* 红黑树调整
* @param node
*/
private void fixTree(MyRedBlackTreeNode<Integer> node) {
// 第一种情况:node节点作为根节点,将当前节点修改为黑色
// 第二种情况:node节点的父节点为黑色节点,不需要做调整
if (node.parent == null || node.parent.color == MyRedBlackTreeNode.BLACK) {
return;
}
while (node.parent != null && node.parent.color == MyRedBlackTreeNode.RED){
if (node.parent.parent == null){
node.parent.color = MyRedBlackTreeNode.BLACK;
continue;
}
// 第三种情况:node节点的父节点为红色
if (node.parent.parent.left == node.parent){ // 父节点在祖父节点的左子树
MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.right; // 获取到叔叔节点
// 3.1 叔叔节点为红色
// - 将父节点和叔叔节点都设置为黑色。
//- 将祖父节点设置为红色。
//- 将祖父节点视为新的插入节点,递归进行上述检查。
if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
node.parent.color = MyRedBlackTreeNode.BLACK;
uncleNode.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
node = node.parent.parent;
continue;
}
// 3.2 叔叔节点为黑色
// 3.2.2 新节点在父节点的右子树,且父节点在祖父节点的左子树
// - 对父节点进行左旋,这样原来的父节点就变成了新节点的子节点,且新节点成为了其父节点的左子节点。
// - 按照左左插入的情况处理新的父子关系。
if (node.parent.right == node){
node = node.parent;
leftRotate(node);
}
// 3.2.1 新节点在父节点的左子树,且父节点在祖父节点的左子树
// - 将父节点设置为黑色。
//- 将祖父节点设置为红色。
//- 对祖父节点进行右旋。
node.parent.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
rightRotate(node.parent.parent);
} else if (node.parent.parent.right == node.parent) { // 父节点在祖父节点的右子树
MyRedBlackTreeNode<Integer> uncleNode = node.parent.parent.left; // 获取到叔叔节点
// 3.1 叔叔节点为红色
// - 将父节点和叔叔节点都设置为黑色。
//- 将祖父节点设置为红色。
//- 将祖父节点视为新的插入节点,递归进行上述检查。
if (uncleNode != null && uncleNode.color == MyRedBlackTreeNode.RED){
node.parent.color = MyRedBlackTreeNode.BLACK;
uncleNode.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
node = node.parent.parent;
continue;
}
// 3.2 叔叔节点为黑色
// 3.2.4 新节点在父节点的右子树,且父节点在祖父节点的左子树
if (node.parent.left == node){
node = node.parent;
rightRotate(node);
}
// 3.2.3 新节点在父节点的左子树,且父节点在祖父节点的右子树
// 父节点设为黑色,祖父节点设为红色,并对祖父节点进行左旋
node.parent.color = MyRedBlackTreeNode.BLACK;
node.parent.parent.color = MyRedBlackTreeNode.RED;
leftRotate(node.parent.parent);
}
}
root.color = MyRedBlackTreeNode.BLACK;
}
/**
* 左旋
* @param node
* @return
*/
private MyRedBlackTreeNode<Integer> leftRotate(MyRedBlackTreeNode<Integer> node) {
if (node == null || node.right == null){
return node;
}
MyRedBlackTreeNode<Integer> rightNode = node.right;
node.right = rightNode.left;
if (rightNode.left != null){
rightNode.left.parent = node;
}
rightNode.parent = node.parent;
if (node.parent != null && node.parent.left == node){
node.parent.left = rightNode;
} else if (node.parent != null && node.parent.right == node) {
node.parent.right = rightNode;
}else{
root = rightNode;
}
node.parent = rightNode;
rightNode.left = node;
return rightNode;
}
/**
* 右旋
* @param node
* @return
*/
private MyRedBlackTreeNode<Integer> rightRotate(MyRedBlackTreeNode<Integer> node) {
if (node == null || node.left == null){
return node;
}
MyRedBlackTreeNode<Integer> leftNode = node.left;
node.left = leftNode.right;
if (leftNode.right != null){
leftNode.right.parent = node;
}
leftNode.parent = node.parent;
if (node.parent != null && node.parent.left == node){
node.parent.left = leftNode;
} else if (node.parent != null && node.parent.right == node) {
node.parent.right = leftNode;
}else{
root = leftNode;
}
node.parent = leftNode;
leftNode.right = node;
return leftNode;
}
/**
* 展示树的结构
* @param node
* @return
*/
public void show() {
if (root == null) {
System.out.println("EMPTY!");
return ;
}
// 得到树的深度
int treeDepth = getHeight(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] = " ";
}
}
// 从根节点开始,递归处理整个树
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());
}
}
/**
* 获取树的高度
* @param node
* @return
*/
private int getHeight(MyRedBlackTreeNode<Integer> node) {
if (node == null){
return 0;
}
// 递归求取当前节点的最大的高度
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
/**
* 将节点的值写入到二维数组中
* @param node
* @param rowIndex
* @param columnIndex
* @param res
* @param treeDepth
*/
private void writeArray(MyRedBlackTreeNode<Integer> currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null)
return;
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.data+"["+(currNode.color == MyRedBlackTreeNode.BLACK ? "B" : "R")+"]");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层,则返回
if (currLevel == treeDepth)
return;
// 计算当前行到下一行,每个元素之间的间隔(下一行的列索引与当前元素的列索引之间的间隔)
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断,若有左儿子,则记录相应的"/"与左儿子的值
if (currNode.left != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断,若有右儿子,则记录相应的"\"与右儿子的值
if (currNode.right != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
}
2.2 测试&结果
public class MyRedBlackTreeTest {
public static void main(String[] args) {
MyRedBlackTreeDemo tree = new MyRedBlackTreeDemo(10);
tree.addNode(5);
tree.addNode(15);
tree.addNode(2);
tree.addNode(7);
tree.show();
System.out.println("--------------------------------------");
tree.addNode(8);
tree.show();
System.out.println("--------------------------------------");
tree.addNode(9);
tree.show();
System.out.println("--------------------------------------");
tree.addNode(6);
tree.show();
}
}
结果
10[R]
/ \
5[B] 15[B]
/ \
2[R]7[R]
--------------------------------------
10[B]
/ \
5[R] 15[B]
/ \
2[B] 7[B]
\
8[R]
--------------------------------------
10[B]
/ \
5[R] 15[B]
/ \
2[B] 8[B]
/ \
7[R]9[R]
--------------------------------------
8[B]
/ \
5[R] 10[R]
/ \ / \
2[B] 7[B]9[B] 15[B]
/
6[R]