左倾红黑树的go语言实现

简介

红黑树经常能在计算机底层代码中见到，比如

• C++的map，multimap, set, multiset
• Linux中rdtree用以管理内存和进程
• Java中的HashMap

左倾红黑树是对红黑树的一种改进，在保持红黑树的优良性能情况下使得实现更加的容易。本文解释其原理并使用GO语言对它进行了实现。

无论左倾红黑树还是红黑树都是对它们的原型2-3-4树的一种实现。2-3-4树有一个非常好的性质：树上所有从根结点到叶子结点的路径都是等长的。这意味着查找、插入、删除这三种操作时间复杂度都是$O(log(n))$级别的。关于2-3-4树在此不再赘述。那么为什么不直接实现2-3-4树呢？原因是直接实现2-3-4树太复杂了，因为2-3-4树有三种结点类型，它们分别是2结点、3结点、4结点。插入和删除要考虑这三种结点之间的相互换，情况很多。

而红黑树和左倾红黑树把2-3-4树中的结点拆分了，转换成了一种二叉搜索树（BST），用颜色进行结点类型的区分，这样树中就只有一种结点了。下图介绍2-3-4树到红黑树和左倾红黑树的转换过程：

转换后的树有如下性质：

1. 每个结点要么是红要么是黑
2. 根结点是黑的
3. 每个结点的空指针都是黑的
4. 如果一个结点是红的，那么两个孩子都是黑的
5. 所有从根结点到空指针所经过的黑结点个数是一样的

前四点很容易可观察得出，最后一点可由2-3-4树的性质推导得出。对它们的操作无非：

• 插入一个元素
• 删除一个元素
• 获取一个元素

我们需要在插入及删除后保证以上五个性质不变。由于左倾红黑树固定了2结点只有一种情况，实现上更加简洁容易，本文基于go语言对它进行了实现。

代码

树结点及其操作

首先定义树结点_RDNode,以及结点的基本操作，这些基本操作在插入和删除数据时者要用到，代码如下：

• isRed() 判断一个结点是不是红的。如果结点是空指针，则不是红的（即它是黑的）
• rotateLeft() 子树的左旋
• rotateRight() 子树的右旋
• flipColors() 子树的颜色翻转
• fixUp() 子树的颜色修复

const (
	RDTREE_COLOR_RED   bool = true
	RDTREE_COLOR_BLACK bool = false
)

type _RDNode[K Ordered, V interface{}] struct {
	key   K              // 键
	value V              // 值
	left  *_RDNode[K, V] // 左孩子
	right *_RDNode[K, V] // 右孩子
	color bool           // 结点的颜色
}

func isRed[K Ordered, V any](node *_RDNode[K, V]) bool {
	return node != nil && node.color == RDTREE_COLOR_RED
}

func rotateLeft[K Ordered, V any](node *_RDNode[K, V]) *_RDNode[K, V] {
	x := node.right
	node.right = x.left
	x.left = node
	x.color, node.color = node.color, x.color //交换颜色
	return x
}

func rotateRight[K Ordered, V any](node *_RDNode[K, V]) *_RDNode[K, V] {
	x := node.left
	node.left = x.right
	x.right = node
	x.color, node.color = node.color, x.color
	return x
}

func flipColors[K Ordered, V any](node *_RDNode[K, V]) {
	node.color = !node.color
	node.left.color = !node.left.color
	node.right.color = !node.right.color
}

func fixUp[K Ordered, V any](node *_RDNode[K, V]) *_RDNode[K, V] {
	if isRed(node.right) && !isRed(node.left) {
		node = rotateLeft(node)
	}
	if isRed(node.left) && isRed(node.left.left) {
		node = rotateRight(node)
	}
	if isRed(node.left) && isRed(node.right) {
		flipColors(node)
	}
	return node
}
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
46
47
48
49
50
51

子树的左旋和右旋算是子树的基本操作了，主要作用是对子树平衡进行调整。在红黑树、AVL树中都会用到。下图描述了左旋和右旋的过程。注意旋转过程中颜色也会发生交换，见代码，我为了偷懒就不画图啦。
（下图是偷的图，颜色与红黑无关，请忽略）

颜色翻转: 过程如下。从2-3-4树的角度来说就是把4结点进行分裂，试图把中间的值放入父结点中。

fixup()是左倾红黑树特有的操作。因为左倾红黑树的插入和删除操作都是递归进行的，因此该函数可以用来在递归回溯过程中修复因为颜色翻转或新插入结点等导致出现的连续的两个红结点。左倾红黑树有两个不同版本：

• 基于2-3-4树版本
• 基于2-3树版本（即只存在2结点和3结点，不存在4结点）

我们的上述代码是以“基于2-3树版本”为例的。在这个版本中，只有可以会出现3种情况的连续红色。图示如下。

• 对于情况1：我们令子树右旋，变成情况3，再继续处理情况3
• 对于情况2：我们令子树的左孩子左旋，变成情况1，再继续处理情况1
• 对于情况3：我们令子树颜色翻转

这样处理后，当前子树就没有连续的红色了。但由于父结点也可能是红色的，颜色翻转可能在父结点也出现有连续红色的情况，我们在处理父结点时再进行修复了。

树结构定义

树结构如下：
tree 指针引用了根结点
size 变量表示树结点的个数

type RDMap[K Ordered, V any] struct {
	tree *_RDNode[K, V]
	size int
}

func NewRDMap[K Ordered, V any]() *RDMap[K, V] {
	return &RDMap[K, V]{
		tree: nil,
		size: 0,
	}
}
1
2
3
4
5
6
7
8
9
10
11

获取元素个数

直接返回size即可。

func (this *RDMap[K, V]) Size() int {
	return this.size
}
1
2
3

获取元素值

按照BST一样的方式进行查找元素值

func (this *RDMap[K, V]) Get(key K) (V, bool) {
	tree := this.tree
	for tree != nil {
		if tree.key == key {
			return tree.value, true
		} else if tree.key < key {
			tree = tree.right
		} else {
			tree = tree.left
		}
	}
	return *new(V), false
}
1
2
3
4
5
6
7
8
9
10
11
12
13

插入

插入元素时，以递归的方式进行。与BST相同。新插入的结点一定是红色的。 且由于左倾红黑树需要平衡，因此递归回来的时候，调用 fixUp(tree) 对连续的红色（3种情况）进行修复。
最后，把根结点置黑色。

func (this *RDMap[K, V]) set(tree *_RDNode[K, V], node *_RDNode[K, V]) *_RDNode[K, V] {
	if tree == nil {
		this.size++
		return node
	}
	if tree.key == node.key {
		tree.value = node.value
	} else if tree.key < node.key {
		tree.right = this.set(tree.right, node)
	} else {
		tree.left = this.set(tree.left, node)
	}
	return fixUp(tree)
}

func (this *RDMap[K, V]) Set(key K, value V) {
	node := &_RDNode[K, V]{
		key:   key,
		value: value,
		left:  nil,
		right: nil,
		color: RDTREE_COLOR_RED,
	}
	// 递归放置，并置根结点的颜色为黑色
	this.tree = this.set(this.tree, node)
	this.tree.color = RDTREE_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

删除

删除的代码比较繁琐。总的说来有以下几点：

1. 递归进行删除
2. 把所有结点的删除都变成红色叶结点的删除。因此：
   (1). 如果发现要删除的是叶子结点，直接删除即可。
   (2). 如果发现要删除不是叶结点，则把它与中序遍历后继结点进行交换（值交换），继续递归删除
   (3). 为了保证删除叶子结点时一定是红的，递归过程中临时破坏红黑树的性质以保证下一个结点或下一个结点的左孩子是红的，在递归回溯回来过程中进行修复。
3. 置根结点为黑色

func (this *RDMap[K, V]) delete(tree *_RDNode[K, V], key K) *_RDNode[K, V] {
	// 如果是叶子结点，直接删除
	if tree.key == key && tree.right == nil {
		this.size--
		return nil
	}
	// 如果是非叶子结结，根据key值大小决定递归处理
	if tree.key > key {
		// 保证下一个结点或下一个结点的左孩子为红
		if !isRed(tree.left) && !isRed(tree.left.left) {
			flipColors(tree)
			if isRed(tree.right.left) {
				tree.right = rotateRight(tree.right)
				tree = rotateLeft(tree)
				flipColors(tree)
			}
		}
		// （1）向左递归删除
		tree.left = this.delete(tree.left, key)
	} else {
		// 同样保证下一个结点或下一个结点的左孩子为红
		if isRed(tree.left) {
			tree = rotateRight(tree)
		}
		if !isRed(tree.right) && !isRed(tree.right.left) {
			flipColors(tree)
			if isRed(tree.left.left) {
				tree = rotateRight(tree)
				flipColors(tree)
			}
		}
		// (2) 向右递归删除
		if tree.key == key {
			// 到找后继结点
			node := tree.right
			for node.left != nil {
				node = node.left
			}
			// 把后断结点的值补到当前位值，递归删除后继结点
			tree.key, node.key = node.key, tree.key
			tree.value, node.value = node.value, tree.value
		}
		tree.right = this.delete(tree.right, key)
	}
	return fixUp(tree)
}

func (this *RDMap[K, V]) Delete(key K) {
	this.tree = this.delete(this.tree, key)
	this.tree.color = RDTREE_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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

测试

测试结果表明我们的实现是正确的。

测试插入

func TestRDMap(t *testing.T) {
	m := structure.NewRDMap[int, string]()
	for i := 0; i < 100; i++ {
		m.Set((i), fmt.Sprint(i+100))
		fmt.Println("insert: ", i)
	}

	m.Set(20, fmt.Sprint("999"))
	fmt.Println("size:", m.Size())
	for i := 100; i < 10000; i++ {
		m.Set((i), fmt.Sprint(i+100))
		fmt.Println("insert: ", i)
	}

	for i := 0; i < 10000; i++ {
		v, ok := m.Get((i))
		if ok {
			fmt.Println(v)
		} else {
			fmt.Println("error !")
		}
	}

	fmt.Println("size:", m.Size())
}
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

结果：

测试删除

func TestRDMapDelete(t *testing.T) {
	m := structure.NewRDMap[int, string]()
	for i := 0; i < 10000; i++ {
		m.Set((i), fmt.Sprint(i+100))
		fmt.Println("insert: ", i)
	}

	for i := 3000; i < 7000; i++ {
		m.Delete(i)
	}

	for i := 0; i < 10000; i++ {
		v, ok := m.Get((i))
		if ok {
			fmt.Println(v)
		} else {
			fmt.Println("error !")
		}
	}

	fmt.Println("size:", m.Size())

	for i := 3000; i < 7000; i++ {
		m.Set(i, fmt.Sprint(i+100))
	}
	for i := 0; i < 10000; i++ {
		v, ok := m.Get((i))
		if ok {
			fmt.Println(v)
		} else {
			fmt.Println("error !")
		}
	}

	fmt.Println("size:", m.Size())
}

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

一开始插入10000个数，删除4000个之后，还剩6000个。


之后，又把删除的4000个补上了，size 又变成了10000。

参考

[1] https://sedgewick.io/talks/#ll-red-black-trees
[2] https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf