经典算法巡礼(八) -- 查找之二叉查找树

理论说

概念

二叉查找树是计算机科学中最重要的算法之一,它将链表插入的灵活性和有序数组查找的高效性结合在一起,即同时拥有插入灵活性和查找高效性的一种符号表实现。

性能

我们知道,链表以插入灵活性闻名,但是它的实现直接导致在查找效率上不是如此优美,平均情况下的成本数量级为O(N/2),最坏情况下为O(N)。而有序数组查找时利用二分法直接将查找效率提高至平均情况和最坏情况均为对数级别O(lgN),而查找情况下却也丑陋不堪,平均情况下增长数量级为O(N/2),最坏情况下为O(N)。二叉查找树结合两者的优势,在平均情况下查找和插入均提高至O(lgN),最坏情况下为O(N)

数据结构

二叉查找树所使用的数组结构由结点组成,每个结点均包含指向其他指点的指针(可以为空)。在二叉树中,每个结点有且只能有一个父结点,即只能有一个另外的结点包含指向该结点的指针(树的根结点除外),而每个结点都有左右两个分别指向不同结点的指针,称之为左子指针和右子指针,被指向的两个结点分别为该结点的左子结点和右子结点(可以为nil,即没有相应的子结点)。同时,二叉查找树有一个重要的性质,即结点的左子结点及其左子结点的所有递归子结点的值均小于该结点,而右子结点及其右子结点的所有递归所有子结点的值均大于该结点。这个特性使得该树成为一个按一定方式有序的树,从而支持高效查询。

一棵典型的二叉查找树如下图所示:

如图中所示,结点S为二叉查找树的根结点,它是没有父结点的,但是拥有两个子结点,左子结点为E,父子结点为X。同时,结点E又拥有两个子结点,而结点X没有子结点。另外,由于二叉查找树的性质,结点S,E,X的大小 为E<S<X。

实践说

我们实现二叉查找树中几个常用的接口,均以golang实现。

结点定义

我们首先定义结点的数据结构,根据“理论说”中表述,结点必须包含指向左子结点和右子结点的两个指针。另外,结点是数据承载的容器,所以还必须包括与数据相关的字段。我们将结点定义如下:

1
2
3
4
5
6
7
8
type Key string
type Value string
type Node struct {
key Key
value Value
left, right *Node
N int
}

上述结构中,我们包含了指向子结点的两个指针,而且具有一对Key-Value对,这表明我们结点中所存储数据为Key-Value对,另外N为结点计数器,值为以该结点为根结点的子树的结点总数,如“基础说”中E结点的N值为5。

二叉查找树定义

定义二叉查找树,有了“结点定义”后,该定义非常方便,如下所示:

1
2
3
type BST struct {
root *Node
}

由代码段明显可知,二叉查找树的定义,只要直接保存其根结点即可。

二叉查找树一般性接口定义

一般来说,二叉查找树具有以下几个类型的接口:

  • Size:二叉查找树结点数
  • Get:从二叉查找树中获取相应的值
  • Put:将相应的值插入到二叉查找树中
  • Min:从二叉查找树中获取最小值
  • Max:从二叉查找树中获取最大值
  • Floor:从二叉查找树中获取比给定值小的且是最大的值,即向下取整
  • Ceiling:从二叉查找树中获比给定值大的且是最小的值,即向上取整
  • Select:从二叉查找树中获取第k个结点的值(从0开始)
  • Rank: Select接口的反操作,即从二叉查找树中获取给定值的结点的排序值
  • DeleteMin:删除二叉查找树中最小值
  • DeleteMax:删除二叉查找树中最大值
  • Delete:删除指定结点
  • Travel: 遍历二叉查找树

接口实现:Size

1
2
3
4
5
6
7
8
9
10
func (this *BST) Size() int {
return this.size(this.root)
}
func (this *BST) size(n *Node) int {
if n != nil {
return n.N
} else {
return 0
}
}

由于我们在定义结点结构体的时候,特别增加字段N表示以该结点为根结点的子树的结点数,所以Size()接口的实现非常方便,直接返回N字段的值即可。

接口实现:Get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (this *BST) Get(key Key) *Node {
return this.get(this.root, key)
}
func (this *BST) get(n *Node, key Key) *Node {
if n == nil {
return nil
}
if n.key == key {
return n
}
if n.key > key {
return this.get(n.left, key)
}
if n.key < key {
return this.get(n.right, key)
}
return nil
}

Get()接口的实现思路比较简单,递归遍历所有结点,若寻找Key的值等于结点的值,则找到相应结点;若小于结点的值,则在该结点的左子结点上再次进行相同的操作;若大于结点的值,则相应查看右子结点。

接口实现:Put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (this *BST) Put(key Key, value Value) {
this.root = this.put(this.root, key, value)
}
func (this *BST) put(n *Node, key Key, value Value) *Node {
if n == nil {
return &Node{key: key, value: value, N: 1}
}
if n.key == key {
n.value = value
} else if n.key < key {
n.right = this.put(n.right, key, value)
} else {
n.left = this.put(n.left, key, value)
}
n.N = this.size(n.left) + this.size(n.right) + 1
return n
}

Put()接口的实现思路可以归纳为两种情况:一种是找到相应结点并修改值,另一种是未找到相应结点,在合适的位置增加结点。具体实现时,递归比较结点值,若值相等,则为情况一。若值大于,则对结点左子树进行相同操作,若值小于,则对结点右子树进行相同操作,直到子结点为nil为止,即未找到相应结点,对应于情况二,则主动在该位置增加新结点。

接口实现:Min

1
2
3
4
5
6
7
8
9
func (this *BST) Min() Key {
return this.min(this.root).key
}
func (this *BST) min(n *Node) *Node {
if n.left != nil {
return this.min(n.left)
}
return n
}

Min()接口实现比较简单,由于二叉查找树本身的特点是有序的,所以直接一直找到最深左子结点即可。

接口实现:Max

1
2
3
4
5
6
7
8
9
func (this *BST) Max() Key {
return this.max(this.root).key
}
func (this *BST) max(n *Node) *Node {
if n.right != nil {
return this.max(n.right)
}
return n
}

Max()接口与Min()接口类似,这里不再赘述。

接口实现:Floor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (this *BST) Floor(key Key) Key {
if n := this.floor(this.root, key); n != nil {
return n.key
}
return ""
}
func (this *BST) floor(n *Node, key Key) *Node {
if n == nil {
return nil
}
if key == n.key {
return n
}
if key < n.key {
return this.floor(n.left, key)
}
node := this.floor(n.right, key)
if node == nil {
return n
} else {
return node
}
return nil
}

Floor()接口实现思路如下:如果给定Key等于结点的Key,则该结点为向下取整后结点,这种情况是最简单的;如果给定Key小于结点的Key,则向下取整后结点一定存在于以结点左子结点为根结点的子树中,递归调用即可;剩下的情况就是大于结点Key的情况,在此种情况下,向下取整后结点可能在右子树中,若不在,则该结点即为所需要结点。

接口实现:Ceiling

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (this *BST) Ceiling(key Key) Key {
if n := this.ceiling(this.root, key); n != nil {
return n.key
}
return ""
}
func (this *BST) ceiling(n *Node, key Key) *Node {
if n == nil {
return nil
}
if key == n.key {
return n
}
if key > n.key {
return this.ceiling(n.right, key)
}
node := this.ceiling(n.left, key)
if node == nil {
return n
} else {
return node
}
return nil
}

Ceiling()接口与Floor()接口类似,也不再赘述。

接口实现:Select

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
func (this *BST) Select(k int) Key {
if n := this.innerSelect(this.root, k); n != nil {
return n.key
}
return ""
}
// 在go中select为关键字,所以以innerSelect代替
func (this *BST) innerSelect(n *Node, k int) *Node {
if n == nil {
return nil
}
if k <= 0 {
return n
}
if n.left == nil {
return this.innerSelect(n.right, k-1)
}
if n.left.N == k {
return n
}
if n.left.N > k {
return this.innerSelect(n.left, k)
}
if n.left.N < k {
return this.innerSelect(n.right, k-n.left.N-1)
}
return nil
}

Select()接口实现的是给定一个k值,找到这样一个结点,小于这个结点的所有结点数正好为k。由于我们定义结点数据结构时,字段N的值代码以该结点为根结点形成的树的结点数。因此,Select()接口的实现只有找到这样一个结点,该结点的左子结点的N值为k即可。

接口实现:Rank

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
func (this *BST) Rank(key Key) int {
return this.rank(this.root, key)
}
func (this *BST) rank(n *Node, key Key) int {
if n == nil {
return 0
}
if n.key == key {
if n.left != nil {
return n.left.N
} else {
return 0
}
}
if n.key > key {
return this.rank(n.left, key)
}
if n.key < key {
if n.left != nil {
return n.left.N + 1 + this.rank(n.right, key)
} else {
return 1 + this.rank(n.right, key)
}
}
return 0
}

Rank()接口即Select()接口的反操作,即找到给比定结点小的结点数。实现过程中可以分为三种情况:结点值与Key相等时,结果为结点左子结点的N值;大于Key时,保存结果的结点在该结点的左子树中;小于Key时,情况略微复杂,由三部分组成,分别为左子树的结点数,该结点和右子树中比Key小的结点数。

接口实现:DeleteMin

1
2
3
4
5
6
7
8
9
10
11
12
func (this *BST) DeleteMin() {
this.root = this.deleteMin(this.root)
}
func (this *BST) deleteMin(n *Node) *Node {
if n.left == nil {
return n.right
} else {
n.left = this.deleteMin(n.left)
n.N = this.size(n.left) + this.size(n.right) + 1
return n
}
}

DeleteMin()接口实现思路就是找到最小结点,并且删除它即可。根据二叉查找树的特点,最小结点只要沿着树的左子结点走,直到发现一个结点,其左子结点为nil,那么该结点就是最小结点。

接口实现:DeleteMax

1
2
3
4
5
6
7
8
9
10
11
12
func (this *BST) DeleteMax() {
this.root = this.deleteMax(this.root)
}
func (this *BST) deleteMax(n *Node) *Node {
if n.right == nil {
return n.left
} else {
n.right = this.deleteMax(n.right)
n.N = this.size(n.left) + this.size(n.right) + 1
return n
}
}

DeleteMax()接口与DeleteMin()接口类似,这里不再赘述。

接口实现: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
25
26
func (this *BST) Delete(key Key) {
this.root = this.delete(this.root, key)
}
func (this *BST) delete(n *Node, key Key) *Node {
if n == nil {
return nil
}
if n.key > key {
n.left = this.delete(n.left, key)
} else if n.key < key {
n.right = this.delete(n.right, key)
} else {
if n.left == nil {
return n.right
}
if n.right == nil {
return n.left
}
node := n
n = this.min(n.right)
n.right = this.deleteMin(n)
n.left = node.left
}
n.N = this.size(n.left) + this.size(n.right) + 1
return n
}

Delete()接口实现与查找类似,若结点值大于Key,则对结点左子数据进行递归操作,若结点值小于Key,则对结点右子数进行递归操作,当结点值等于Key时,则将该结点删除即可。在删除过程中,思路也很简单,即将删除结点的右子树中的最小结点代替该结点即可。

接口实现:Travel

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type oper func(*Node)
func (this *BST) Travel(f oper, sort string) {
this.travel(this.root, f, sort)
}
func (this *BST) travel(n *Node, f oper, sort string) {
if n == nil {
return
}
switch sort {
case "in-order":
this.travel(n.left, f, sort)
f(n)
this.travel(n.right, f, sort)
case "pre-order":
f(n)
this.travel(n.left, f, sort)
this.travel(n.right, f, sort)
case "post-order":
this.travel(n.left, f, sort)
this.travel(n.right, f, sort)
f(n)
}
}

Travel接口实现考虑了三种情况,即中序遍历,先序遍历和后序遍历

分析说

使用二叉查找树的算法的运行时间取决于树的形状,而树的形状又取决于键被插入的先后顺序。在最好的情况下,二叉查找树是完全平衡的,每条空链接和根结点的距离都为~lgN,但是在最坏的情况下,二叉查找树与链表无异,具体参见下图:

但是,二叉查找树的形状由于取决于键被插入的先后顺序,所以我们无法控制其一直保持基本平衡状态。那么,我们是否可以如同快速排序一般事先进行随机打乱呢?事实上这是不行的,因为二叉查找树本身是有序的,而且它携带着键值的插入顺序

为了方便我们分析,我们假设二叉查找树的键的分布是随机的,即它们插入的顺序是随机的。这里,我们直接引入两个命题:

命题一:在由N个随机键构造的二叉查找树中,查找命中平均所需的比较次数为~2lnN(约1.39lgN)。

命题二:在由N个随机键构造的二叉查找树中插入操作和查找未命中平均所需的比较次数为~2lnN(约1.39lgN)。

命题一说明,二叉查找树在查找随机键的成本方面比二分查找大约高出39%(二分查找为lnN),但是这高出的成本是值得的。因为命题二说明,二叉查找树在插入新键方面也是~2lnN,与二分查找的~N相比,对数级别的成本相对来说是高效很多

以上分析均是基于二叉查找树的正常情况,而实际上,最坏情况也是可能发生的。在最坏情况下,二叉查找树的性能完全取决于树的高度,具体如命题三所描述。

命题三:在一棵二叉查找树中,所有操作在最坏情况下所需要的时间都和树的高度成正比。

很明显,最坏情况下成本(即树的高度)一定会大于平均情况下的成本。但是具体是多少呢?事实上,随机键构造的二叉查找树的平均高度为树中结点数的对数级别,具体值趋近于2.99lgN。因此,二叉查找树的所有操作,在最坏情况下所需成本也是对数级别的,这不得不说是一个可喜的结果。

但是,请注意,我们之前有个假设:二叉查找树的键是随机插入的,但是实际应用中,这通常是理想情况下才会发生的事。而且,这种非随机插入,我们并不能如快速排序一般事先进行随机打乱操作。那么,真的无能为力了吗?当然不是!平衡查找树就是为这个而生的!