二叉查找树

二叉查找树

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

• 中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。
• 支持重复数据的二叉查找树
  • 在实际的软件开发中，一般利用对象的某个字段作为键值（key）来构建二叉查找树，我们把对象中的其他字段叫作卫星数据。
  • 如果存储的两个对象键值相同，这种情况该怎么处理呢？
    • 二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
    • 每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树。
      • 放在右子树，比放在左子树，操作更简单
      • 当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。 这样就可以把键值等于要查找值的所有节点都找出来。
      • 对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

1. 二叉查找树的查找操作(前提: 不存在键值相同的情况)

• 先取根节点，如果它等于我们要查找的数据，那就返回。
• 如果要查找的数据比根节点的值大，那就在右子树中递归查找。
• 如果要查找的数据比根节点的值小，那就在左子树中递归查找；

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

type BST struct {
	tree *TreeNode
	//比对函数，0:v==nodeV,正数:v>nodeV,负数:v<nodeV
	compareFunc func(v, nodeV interface{}) int
}
func (this *BST) Find(v interface{}) *TreeNode {
	p := this.tree
	for nil != p {
		compareResult := this.compareFunc(v, p.Val)
		if compareResult == 0 {
			return p
		} else if compareResult > 0 { //v > nodeV
			p = p.Right
		} else { //v < nodeV
			p = p.Left
		}
	}
	return nil
}

2. 二叉查找树的插入操作(前提: 不存在键值相同的情况)

从根节点开始，依次比较要插入的数据和节点的大小关系。

• 如果要插入的数据比节点的数据大，
  • 并且节点的右子树为空，就将新数据直接插到右子节点的位置；
  • 如果不为空，就再递归遍历右子树，查找插入位置。
• 同理，如果要插入的数据比节点数值小，
  • 并且节点的左子树为空，就将新数据插入到左子节点的位置；
  • 如果不为空，就再递归遍历左子树，查找插入位置。

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

func (this *BST) Insert(v interface{}) {
	if this.tree == nil {
		this.tree = NewTreeNode(v)
		return
	}
	p := this.tree
	for nil != p {
		compareResult := this.compareFunc(v, p.Val)
		if compareResult > 0 {
			if nil == p.Right {
				p.Right = NewTreeNode(v)
				return
			}
			p = p.Right
		} else {
			if nil == p.Left {
				p.Left = NewTreeNode(v)
				return
			}
			p = p.Left
		}
	}
}

3. 二叉查找树的删除操作(前提: 不存在键值相同的情况)

针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

• 如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
• 如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
• 如果要删除的节点有两个子节点，这就比较复杂了。
  • 找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。
  • 然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了）
    • 删除过程遵循第一条规则或者第二条规则。

 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

func (this *BST) Delete(v interface{}) bool {
	var pp *TreeNode = nil // pp记录的是p的父节点
	p := this.tree         // p指向要删除的节点，初始化指向根节点
	for nil != p && p.Val != v {
		pp = p
		compareResult := this.compareFunc(v, p.Val)
		if compareResult > 0 {
			p = p.Right
		} else {
			p = p.Left
		}
	}

	if nil == p { //需要删除的节点不存在
		return false
	}

	// 要删除的节点有两个子节点
	if p.Left != nil && p.Right != nil {
		// 查找右子树中最小节点
		minP := p.Right
		minPP := p // minPP表示minP的父节点
		for minP.Left != nil {
			minPP = minP
			minP = minP.Left
		}
		p.Val = minP.Val // 将minP的数据替换到p中
		p = minP         // 下面就变成了删除minP了
		pp = minPP
	}

	// 删除节点是叶子节点或者仅有一个子节点
	var child *TreeNode
	if p.Left != nil {
		child = p.Left
	} else if p.Right != nil {
		child = p.Right
	} else {
		child = nil
	}

	if pp == nil {
		this.tree = child // 删除的是根节点
	} else if pp.Left == p {
		pp.Left = child
	} else {
		pp.Right = child
	}
	return true
}

4. 时间复杂度分析 不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。

如何求一棵包含 n 个节点的完全二叉树的高度？
树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。

• 包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。
• 对于完全二叉树来说，最后一层的节点个数有点儿不遵守上面的规律了。它包含的节点个数在 1 个到 2^(L-1) 个之间（我们假设最大层数是 L）
• 所以，n满足如下关系：

  n >= 1+2+4+8+...+2^(L-2)+1
  n <= 1+2+4+8+...+2^(L-2)+2^(L-1)
  

  借助等比数列的求和公式，我们可以计算出，L 的范围是[log2(n+1), log2n +1]。完全二叉树的层数小于等于 log2n +1，也就是说，完全二叉树的高度小于等于 log2n。

有了如此高效的散列表，为什么还需要二叉树？

1. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。

3. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

4. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

平衡二叉查找树

平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。
这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

最常用的平衡二叉查找树是红黑树。

红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

上一篇 « 二叉树 下一篇 » 堆