前几天在网上学习了 AVL 树的概念和实现方法，但光在网上看文章来学习，多少有点片面，很多细节网上的文章解释的不是很清楚，就比如删除节点该如何操作。所以，翻出了我吃灰多年的《算法导论》，其中讲到了二叉搜索树（BST）和红黑树，虽然没有 AVL，但是举一反三，也能对 AVL 有更深刻的理解。

我分了两篇文章，分别记录 BST 和红黑树的笔记。

什么是 BST

二叉搜索树 (Binaray Search Tree)

顾名思义，一棵二叉搜索树是以一棵二叉树来组织的，树中的每个节点，除了 Key 和承载的数据外，还有属性 parent、 left、 right，分别指向父节点、左子树和右子树。如果某个子节点或父节点不存在，则相应的属性为 Nil。根节点是唯一一个父节点为 Nil 的节点

二叉搜索树中，对任何一个节点 N，其左子树的 key 最大不超过 N.key，右子树的 key 最小不低于 N.key

在一个高度为 h 的 BST 中，元素的插入、删除、查找都可以在 O(h) 时间内完成

BST API

《算法导论》中介绍了 BST 的一些常规操作 API，我用 Golang 简单了实现了一遍。

先看看基础骨架

 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


// Node 节点
type Node struct {
	key                 int
	parent, left, right *Node
}

// NewNode 创建一个新的节点
func NewNode(key int) *Node {
	return &Node{key: key}
}

// NewBST 创建一个 BST
func NewBST() *BST {
	return &BST{}
}

// BST 二叉搜索树 binary search tree
type BST struct {
	root *Node
}

// Search 查找 BST 中的节点
func (b *BST) Search(key int) *Node { return nil }

// Max BST 中最大的节点
func (b *BST) Max(n *Node) *Node { return nil}

// Min BST 中最小的节点
func (b *BST) Min(n *Node) *Node { return nil }

// Successor 查找一个节点的后继节点
func (b *BST) Successor(n *Node) *Node { return nil }

// Predecessor 查找一个节点的前驱节点
func (b *BST) Predecessor(n *Node) *Node { return nil }

// Insert 插入一个节点到 BST 中
func (b *BST) Insert(n *Node) {}

// Delete 从 BST 中删除一个元素
func (b *BST) Delete(n *Node) {}

// Transplant 替换一个节点，这个方法用以辅助 Delete 函数
func (b *BST) Transplant(n *Node, v *Node) {}

TL;DR

如果不想看下面的长篇大论，可以直接点击这里看源码

查找

我们经常需要查找存储在 BST 中的关键字。除了 Search 操作外，BST 还支持 Minimum(最小节点)、Maximum(最大节点)、Successor(后继节点)、Predecessor(前驱节点) 的查询操作。

这些 API 都可以使用递归来实现，但使用迭代可以得到更好的运行效率，因为不用维护递归的调用栈。

Search(搜索)

我们从根节点出发，不断的把节点的 key 和传入的 key 相比较，如果两者相等，则这是节点就是要查找的节点。如果节点的 key 比传入的 key 小，则结果应该在当前节点的右边，反之则在左边。直到遍历到树的叶子节点，如果还没有结果则表示没有找到对应着 key 的 Node。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// Search 查找 BST 中的节点
func (b *BST) Search(key int) *Node {
	node := b.root
	for node != nil {
		if node.key == key {
			break
		}
		if key > node.key {
			node = node.right
		} else {
			node = node.left
		}
	}
	return node
}

Max(最大节点)

因为 BST 的性质，最大的节点一定是树的最右侧的节点，所以我们只需要给出最右侧的节点即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// Max BST 中最大的节点
func (b *BST) Max(n *Node) *Node {
	if n == nil {
		return nil
	}
	node := n
	for node.right != nil {
		node = node.right
	}
	return node
}

Min(最小节点)

和 Max 方法相反，Min 只需要给出最左侧的节点即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// Min BST 中最小的节点
func (b *BST) Min(n *Node) *Node {
	if n == nil {
		return nil
	}
	node := n
	for node.left != nil {
		node = node.left
	}
	return node
}

Successor(后继节点)

如果树中所有节点的 key 都各不相同，则一个节点 X 的后继节点，是所有大于 X.key 的节点中最小的节点

当查找一个节点的后继时，我们需要使用中序遍历的顺序来查找它的后继。而这又分两种情况：

当一个节点的右子树不为空时，后继节点为右子树中的最左节点(右子树中的最小节点)
当节点 X 没有右子树，但有一个后继节点 Y，那么后继节点 Y 是左子树是 X 的祖先节点中的第一个节点

文字解释太难以理解了，我们使用中序遍历的顺序来理解下面的一个 BST

当查找节点 2 的后继节点时，其后继节点应该是 3。
当查找节点 5 的后继节点时，其后继节点应该是 6。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// Successor 查找一个节点的后继节点
func (b *BST) Successor(n *Node) *Node {
	if n == nil {
		return nil
	}

	if n.right != nil {
		return b.Min(n.right)
	}

	var (
		node      = n
		successor = n.parent
	)

	for successor != nil && successor.right == node {
		node = successor
		successor = successor.parent
	}
	return successor
}

Predecessor(前驱节点)

查找前驱节点的逻辑和上面的后继节点逻辑镜像翻转即可，逻辑是一样的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// Predecessor 查找一个节点的前驱节点
func (b *BST) Predecessor(n *Node) *Node {
	if n.left != nil {
		return b.Max(n.left)
	}

	var (
		node        = n
		predecessor = n.parent
	)

	for predecessor != nil && predecessor.left == node {
		node = predecessor
		predecessor = predecessor.parent
	}
	return predecessor
}

插入

BST 的插入相对简单，因为没有自平衡机制，只需要按照 BST 的规则插入即可。

但是随着元素的不断加入，树的高度也在变化，在极端情况下，如果 n 个元素严格按照递增的顺序被插入(1,2,3…)，那么这棵树就变成了一个高度为 n-1(不包含 root 节点) 的链表了，这样的 BST 效率是极差的，所以才会有 AVL、红黑树这样的平衡树。

但这篇文章只讨论 BST，平衡机制先不聊了。

循环片段找到插入的节点 n 的 preant，然后分别修改他们的 parent 指针的 children 指针实现插入

 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


// Insert 插入一个节点到 BST 中
func (b *BST) Insert(n *Node) {
	if b.root == nil {
		b.root = n
		return
	}

	var (
		node   = b.root
		parent = node.parent
	)

	for node != nil {
		// 已存在的节点，不处理
		if node.key == n.key {
			return
		}

		parent = node
		if n.key > node.key {
			node = node.right
		} else {
			node = node.left
		}
	}

	if n.key > parent.key {
		parent.right = n
	} else {
		parent.left = n
	}
	n.parent = parent
}

删除

删除节点大概是 BST 中最麻烦的操作了，因为会分好几种情况，我们一个一个的说

1. 没有子节点

当要删除的节点 N 没有子节点时，这是最简单的操作，只需要斩断 N.parent 和 N 的联系即可

如下面的例子，要删除节点 1 不需要什么操作，直接删除即可

2. 只有左子节点

当要删除的节点 N 有左子节点，但没有右子节点时，我们让 N.left 取代 N 的位置

1
2
3
4
5
6
7
8
9


+---------+-------+
| delete node 2   |
+---------+-------+
|      3  |    3  |
|     /   |   /   |
|    2    |  1    |
|   /     |       |
|  1      |       |
+---------+-------+

3. 只有右子节点

和第 2 条相反，当节点 N 有右子节点但没有左子节点时，让 N.right 取代 N 的位置

1
2
3
4
5
6
7
8
9


+---------+-------+
|  delete node 2  |
+---------+-------+
|  1      |  1    |
|   \     |   \   |
|    2    |    3  |
|     \   |       |
|      3  |       |
+---------+-------+

4. 有左右子节点

当节点 N 同时拥有左右子节点时，情况稍微复杂点。

我们首先找到节点 N 的后继节点 Y，因为 N 有右子节点，后继节点 Y 一定是 N 节点的右子树中的最小节点，并且 Y 没有左子节点。这个时候又分两种情况：

如果 Y 不是 N 的右子节点，我们首先要让 Y.right -> Z 替换 Y 的位置，同时将 Y.right 指向 N.right，然后让 Y 替换 N 的位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


+-----------+----------+----------+
| step 1    | step 2   | step 3   |
+-----------+----------+----------+
|    2(N)   |    2(N)  |    3(Y)  |
|   / \     |   / \    |   / \    |
|  1   5    |  1   5   |  1   5   |
|     /     |     /    |     /    |
|    3(Y)   |    4(Z)  |    4(Z)  |
|     \     |          |          |
|     4(Z)  |   3(Y)   |   2(N)   |
+-----------+----------+----------+

否则我们直接让 Y 替换 N 的位置

1
2
3
4
5
6
7
8
9


+------------+----------+
| step 1     | step 2   |
+------------+----------+
|    2(N)    |    3(Y)  |
|   / \      |   / \    |
|  1   3(Y)  |  1   4   |
|       \    |          |
|        4   |  2(N)    |
+------------+----------+

理论到此为止，我们来实现代码。上面提到后继节点 Y 替换节点 N，我们需要实现 Transplant方法

这个方法没有处理 v 的 child node，需要调用方自己处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// Transplant 替换一个节点，这个方法用以辅助 Delete 函数
func (b *BST) Transplant(n *Node, v *Node) {
	if n == b.root {
		b.root = v
		if v != nil {
			v.parent = nil
		}
		return
	}
	if n.parent.left == n {
		n.parent.left = v
	} else {
		n.parent.right = v
	}
	if v != nil {
		v.parent = n.parent
	}
}

然后我们利用这个方法来实现 Delete 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// Delete 从 BST 中删除一个元素
func (b *BST) Delete(n *Node) {
	if n.left == nil {
		b.Transplant(n, n.right)
		return
	}
	if n.right == nil {
		b.Transplant(n, n.left)
		return
	}

	successor := b.Successor(n)
	if successor != n.right {
		// 后继节点不是 n 的直属右节点的话，这个后继节点一定没有左节点
    // 所以我们不需要处理 successor.left
		b.Transplant(successor, successor.right)
		successor.right = n.right
		successor.right.parent = successor
	}
	b.Transplant(n, successor)

	successor.left = n.left
	successor.left.parent = successor
}

测试

国际惯例，写完代码要用测试用例来验证。

测试的代码太多了，就不贴上了，可以点击上面提到的源码链接查看。

测试结果：

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


$ go test -v -cover ./...
=== RUN   TestBST_Delete
=== RUN   TestBST_Delete/only_left_child_node
=== RUN   TestBST_Delete/only_right_child_node
=== RUN   TestBST_Delete/no_child_node
=== RUN   TestBST_Delete/has_left_and_right_child_nodes
=== RUN   TestBST_Delete/has_non-right_successor_node
--- PASS: TestBST_Delete (0.00s)
    --- PASS: TestBST_Delete/only_left_child_node (0.00s)
    --- PASS: TestBST_Delete/only_right_child_node (0.00s)
    --- PASS: TestBST_Delete/no_child_node (0.00s)
    --- PASS: TestBST_Delete/has_left_and_right_child_nodes (0.00s)
    --- PASS: TestBST_Delete/has_non-right_successor_node (0.00s)
=== RUN   TestBST_Insert
=== RUN   TestBST_Insert/1
=== RUN   TestBST_Insert/2
=== RUN   TestBST_Insert/3
=== RUN   TestBST_Insert/4
=== RUN   TestBST_Insert/5
--- PASS: TestBST_Insert (0.00s)
    --- PASS: TestBST_Insert/1 (0.00s)
    --- PASS: TestBST_Insert/2 (0.00s)
    --- PASS: TestBST_Insert/3 (0.00s)
    --- PASS: TestBST_Insert/4 (0.00s)
    --- PASS: TestBST_Insert/5 (0.00s)
=== RUN   TestBST_Successor
=== RUN   TestBST_Successor/has_right_child_node
=== RUN   TestBST_Successor/has_multi_right_child_nodes
=== RUN   TestBST_Successor/no_right_child_nodes
=== RUN   TestBST_Successor/no_right_child_nodes_1
=== RUN   TestBST_Successor/no_successor
--- PASS: TestBST_Successor (0.00s)
    --- PASS: TestBST_Successor/has_right_child_node (0.00s)
    --- PASS: TestBST_Successor/has_multi_right_child_nodes (0.00s)
    --- PASS: TestBST_Successor/no_right_child_nodes (0.00s)
    --- PASS: TestBST_Successor/no_right_child_nodes_1 (0.00s)
    --- PASS: TestBST_Successor/no_successor (0.00s)
=== RUN   TestBST_Search
=== RUN   TestBST_Search/#00
=== RUN   TestBST_Search/#01
--- PASS: TestBST_Search (0.00s)
    --- PASS: TestBST_Search/#00 (0.00s)
    --- PASS: TestBST_Search/#01 (0.00s)
=== RUN   TestBST_Predecessor
=== RUN   TestBST_Predecessor/has_left_child
=== RUN   TestBST_Predecessor/has_multi_left_child_nodes
=== RUN   TestBST_Predecessor/no_left_child_node
=== RUN   TestBST_Predecessor/no_predecessor
--- PASS: TestBST_Predecessor (0.00s)
    --- PASS: TestBST_Predecessor/has_left_child (0.00s)
    --- PASS: TestBST_Predecessor/has_multi_left_child_nodes (0.00s)
    --- PASS: TestBST_Predecessor/no_left_child_node (0.00s)
    --- PASS: TestBST_Predecessor/no_predecessor (0.00s)
=== RUN   TestBST_Max
=== RUN   TestBST_Max/#00
=== RUN   TestBST_Max/#01
=== RUN   TestBST_Max/#02
--- PASS: TestBST_Max (0.00s)
    --- PASS: TestBST_Max/#00 (0.00s)
    --- PASS: TestBST_Max/#01 (0.00s)
    --- PASS: TestBST_Max/#02 (0.00s)
=== RUN   TestBST_Min
=== RUN   TestBST_Min/#00
=== RUN   TestBST_Min/#01
=== RUN   TestBST_Min/#02
--- PASS: TestBST_Min (0.00s)
    --- PASS: TestBST_Min/#00 (0.00s)
    --- PASS: TestBST_Min/#01 (0.00s)
    --- PASS: TestBST_Min/#02 (0.00s)
PASS
coverage: 97.4% of statements
ok      github.com/ningzio/algorithm/bst        0.367s  coverage: 97.4% of statements

番外

BST 排序

前面我们提到过，BST 可以在 O(h) 时间内完成插入一个节点，并且我们可以通过中序遍历输出排序后的结果。

在理想的情况下（平衡二叉树），一棵树的高度为节点数量 n 的对数 log n ，所以 h = log n

我们每次插入一个元素，需要 log n 的时间，那么插入 n 个元素的时间复杂度为 O(n * log n)

所以，在理想的情况下，我们可以使用 BST 实现在 O(n * log n) 时间内完成对一组随机序列的排序，然后使用中序遍历输出所有严肃

但是还有另外一个问题，如何处理重复元素？BST 的设计初衷是为了查找（如其名），一般不允许有重复的 Key，就如上面的写法，遇到重复的 Key 会直接覆盖。但是如果我们用 BST 来做排序的话，肯定是要处理重复元素的。

书中也给出了几种方案：

简单且实用方案

为节点 X 新增一个 .L([]*Node) 属性，当遇到相同的值 Y 时，将 Y 添加到 X.L中，当需要输出排序结果时，将 X.L 中的内容一并输出。

花里胡哨解法

为节点 X 新增一个 .b属性。当遇到相同值 Y 时：

如果 X.b 的属性为 false，将 X.b 的值修改为 true，并让 X 成为 Y 的左子节点
如果 X.b 的属性为 true，将 X.b 的值修改为 false，并让 X 成为 Y 的右子节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


+---------------+----------------+----------------+----------------+------------------+----------------+
| insert x      | insert x1      | inset x2       | insert x3      | insert y (y > x) | insert x4      |
+---------------+----------------+----------------+----------------+------------------+----------------+
|  x            |    x1          |    x1          |    x3          |    x3            |     x3         |
|               |   /            |   /            |   / \          |   / \            |    / \         |
|               |  x             |  x2            |  x2  x1        |  x2  x1          |   x4  x1       |
|               |                |   \            |   \            |   \    \         |  / \   \       |
|               |                |    x           |    x           |    x    y        | x2  x   y      |
|               |                |                |                |                  |                |
|  x.b = false  |  x1.b = false  |  x1.b = true   |  x3.b = false  |  x3.b = false    |  x3.b = false  |
|               |  x.b = true    |  x2.b = false  |  x1.b = true   |  x1.b = true     |  x1.b = true   |
|               |                |  x.b = true    |  x2.b = false  |  x2.b = false    |  x4.b = false  |
|               |                |                |  x.b = true    |  x.b = true      |  x2.b = true   |
|               |                |                |                |                  |  x.b = true    |
+---------------+----------------+----------------+----------------+------------------+----------------+

这样可以保证相同的节点可以均衡的分配到树中，而不会向着一个方向一直倾斜而变成了一个链表。

树的遍历

树的三种遍历方式，我们来看看分别使用三种遍历方式得到的结果

前序遍历： [5, 3, 1, 7, 6, 9]

跟节点 -> 左子节点 -> 右子节点

中序遍历： [1, 3, 5, 6, 7, 9]

左子节点 -> 根节点 -> 右子节点

后序遍历： [1, 3, 5, 6, 9, 7]

左子节点 -> 右子节点 -> 根节点

什么是 BST#

BST API#

TL;DR#

查找#

Search(搜索)#

Max(最大节点)#

Min(最小节点)#

Successor(后继节点)#

Predecessor(前驱节点)#

插入#

删除#

1. 没有子节点#

2. 只有左子节点#

3. 只有右子节点#

4. 有左右子节点#

测试#

番外#

BST 排序#

简单且实用方案#

花里胡哨解法#

树的遍历#