Fork me on GitHub

数据结构-红黑树

R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树.红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black).

红黑树的特性:
(1)每个节点或者是黑色,或者是红色.
(2)根节点是黑色.
(3)每个叶子节点(NIL)是黑色. 注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!
(4)如果一个节点是红色的,则它的子节点必须是黑色的.
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点.
红黑树

2-3树

在介绍红黑树之前为什么要先介绍2-3树 呢?因为红黑树是完美平衡的2-3树 的一种实现.所以,理解2-3树对掌握红黑树是至关重要的.
2-3树 的一个Node可能有多个子节点(可能大于2个),而且一个Node可以包含2个键(元素)
可以把 红黑树(红黑二叉查找树) 当作 2-3树 的一种二叉结构的实现.

在前面介绍的二叉树中,一个Node保存一个值,在2-3树中把这样的节点称之为 2- 节点
如果一个节点包含了两个值(可以当作两个节点的融合),在2-3树中把这样的节点称之为 3- 节点. 完美平衡的2-3树所有空链接到根节点的距离都应该是相同的
下面看下《算法4》对 2-3-节点的定义:

  • 2- 节点,含有一个键(及其对应的值)和两条链接.该节点的左链接小于该节点的键;该节点的右链接大于该节点的键
  • 3- 节点,含有两个键(及其对应的值)和三条链接.左链接小于该节点的左键;中链接在左键和右键之间;右链接大于该节点右键

添加节点示例

红黑树

红黑树的背后思想就是用标准的二分搜索树和一些额外的信息来表示2-3树的

这额外的信息指的是什么呢?因为2-3树不是二叉树(最多有3叉),所以需要把 3- 结点 替换成2- 结点

额外的信息就是指替换3-结点的方式

2-3树的链接定义为两种类型:黑链接红链接

黑链接是2-3树中普通的链接,可以把2-3树中的 2- 结点 与它的子结点之间的链当作黑链接
红链接是2-3树中 3- 结点分解成两个 2- 结点,这两个 2- 结点之间的链接就是红链接

那么如何将2-3树和红黑树等价起来,我们规定:红链接均为左链接

根据上面对完美平衡的2-3树和红链接的介绍可以得出结论:没有一个结点同时和两个红链接相连

根据上面对完美平衡的2-3树和黑链接的介绍可以得出结论:完美平衡的2-3树是保持完美黑色平衡的,任意空链接到根结点的路径上的黑链接数量相同

据此,我们可以得出3条性质:

  1. 红链接均为左链接
  2. 没有一个结点同时和两个红链接相连
  3. 完美平衡的2-3树是保持完美黑色平衡的,任意空链接到根结点的路径上的黑链接数量相同

在红黑树中,没有一个对象来表示红链接和黑链接,通过在结点上加上一个属性(color)来标识红链接还是黑链接,color值为red表示结点是红结点,color值为black表示结点是黑结点.

黑结点 2-3树中普通的 2-结点 的颜色
红结点 2-3树中 3- 结点 分解出两个 2-结点 的最小 2-结点

添加元素


左右旋转可以参考AVL中的旋转, 但是旋转之后要进行颜色的调整

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//   node                     x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){

Node x = node.right;

// 左旋转
node.right = x.left;
x.left = node;

x.color = node.color;
node.color = RED;

return x;
}

// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){

Node x = node.left;

// 右旋转
node.left = x.right;
x.right = node;

x.color = node.color;
node.color = RED;

return x;
}

// 颜色翻转
private void flipColors(Node node){

node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
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
32
33
// 向红黑树中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 最终根节点为黑色节点
}

// 向以node为根的红黑树中插入元素(key, value),递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value){

if(node == null){
size ++;
return new Node(key, value); // 默认插入红色节点
}

if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;

if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);

if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);

if (isRed(node.left) && isRed(node.right))
flipColors(node);

return node;
}

参考:
https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

https://blog.csdn.net/johnny901114/article/details/81046088

http://www.cnblogs.com/skywang12345/p/3245399.html

https://blog.csdn.net/u012124438/article/details/78146200

动画版: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%