红黑树补坑

前言

最早接触红黑树是大一下学期的时候有个同学写了一篇相关的论文,现在打算花点时间好好整理一下。

介绍

Red-Black Tree,翻译成红黑树。红黑树本身是一种二叉搜索树,所以必然是任意一个节点大于左子树所有的节点,小于右子树的所有节点。除了满足二叉搜索树,它还有以下特点:

  1. 每个节点要么是黑色,要么是红色。
  2. 根节点和叶子节点必然是黑色的。[这里稍微注意下,每个叶子节点都是null,即和我们平时写的不太一样]
  3. 如果一个节点是红色的,则它的子节点必须是黑色的。
  4. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。即黑色的高度是一样的。

显然第四点能够保证它的相对平衡性(只会因为红色节点的存在而稍微破坏一下平衡性)。因为之前学过二叉平衡树,靠的是旋转来达到高度的平衡的,但是二叉搜索树的效率低,所以才有了红黑树这种相对不那么平衡但是效率高的多的数据结构。

平衡

三个步骤确保红黑树的相对平衡:

  • 变色:很好理解,节点由红色变成黑色或者由黑色变成红色
  • 左旋:和AVL树一致
  • 右旋:和AVL树一致

查找

因为本质是二叉搜索树,所以没什么好讲的…

插入

Emmmm 插入就比较麻烦了…..首先插入必须是插入红色的节点(除了空树这种情况),因为如果是黑色的节点,就肯定会破坏“黑色节点高度一致”这一条,所以必须是插入红色的,那么接下来分类讨论即可。

空树

那不多说,这个要插入的节点必然是根节点,且根节点必须是黑色的。

节点已经存在

只需要把value替换一下,其它啥都不用做。

父节点为黑色

直接插入即可,并不会违反任何平衡性的东西。

父节点为红色

如果要插入到的节点的父节点是红色的,那么由于我们要插入的节点也是红色的,违反了“红色节点的子节点必须是黑色”这一原则,所以需要进一步推理:由于根节点是必然是黑色的,而现在的父节点是红色,所以必然有爷爷节点,且爷爷节点必然是黑色的,在此基础上进行分类讨论:

  • 如果叔叔节点存在且为红色:把父节点和叔叔节点改成黑色,把爷爷改成红色,并将爷爷节点设置为当前节点,然后重复新的判断。
  • 如果叔叔不存在,或者叔叔为黑色(这里似乎是不可能的):
    • 如果父节点为爷爷节点的左节点,同时要插入的点也是父亲节点的左节点,那么就是LL双红情况,处理的方法是:把父节点设成黑色,爷爷节点设成红色,并对爷爷节点进行右旋。
    • 如果父节点为爷爷节点的左节点,同时要插入的点是父亲节点的右节点,即LR双红的情况,处理的方法是:左旋父亲节点,就可以得到上面的LL双红情况,然后继续即可。
    • 如果父节点为爷爷节点的右节点,同时要插入的点是父亲节点的右节点,那么就是RR双红情况,处理的方法是:把父节点设成黑色,爷爷节点设成红色,并对爷爷节点进行左旋。
    • 如果父节点为爷爷节点的右节点,同时要插入的点是父亲节点的左节点,那么就是RL双红情况,处理的方法是:右旋父亲节点,得到RR双红,继续即可。

代码实现

首先是一课树的基本架构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class RBTree<K extends Comparable<K>, V> {

/**
* 根节点
*/
private RBNode<K, V> root;
private static final boolean RED = true;
private static final boolean BLACK = false;


/**
* 红黑树的节点
*/
public class RBNode<K extends Comparable<K>, V> {
private boolean color;
private K key;
private V value;
private RBNode<K, V> left;
private RBNode<K, V> right;
private RBNode<K, V> parent;

public RBNode(boolean color, K key, V value, RBNode<K, V> left, RBNode<K, V> right, RBNode<K, V> parent) {
this.color = color;
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.parent = parent;
}
}
}

接下来需要定义一下打印的方法,为了后续方便我选择的是中序遍历;然后为了方便还自己动手定义了如何左旋一个节点和如何右旋一个节点,最后就是查找节点并进行插入的过程,按照上面的进行判断非常之容易,代码这里先省略了。