数据结构-二叉搜索树.md

二叉搜索树

基本概念

• 左子树（left）：节点属性，代表指向左边子树的指针
• 右子树（right）：节点属性，代表指向右边子树的指针
• 双亲（parent）：节点属性，代表指向父节点的指针
• 关键字（key）：节点关键字，作为节点之间比较大小的值，是排序问题中要重排的值
• 卫星数据（satellite data）：节点保存的其他信息，通常与关键字是一同存取的

性质

设 x 是二叉搜索树中的一个节点：

1. 如果 y 是 x 左子树中的一个节点，那么 y.key<=x.key
2. 如果 y 是 x 右子树中的一个节点，那么 y.key>=x.key

遍历

中序遍历

输出的子树根的关键字位于其左子树的关键字值和右子树的关键字值之间。

func (t *BinarySearchTree) InorderTreeWalk(x *Node) {
	if x != nil {
		t.InorderTreeWalk(x.Left)
		fmt.Println(x.Key)
		t.InorderTreeWalk(x.Right)
	}
}

前序遍历

输出的根的关键字在其左右子树的关键字值之前。

func (t *BinarySearchTree) PreorderTreeWalk(x *Node) {
	if x != nil {
		fmt.Println(x.Key)
		t.PreorderTreeWalk(x.Left)
		t.PreorderTreeWalk(x.Right)
	}
}

后序遍历

输出的根的关键字值在其左右子树的关键字值之后。

func (t *BinarySearchTree) PostorderTreeWalk(x *Node) {
	if x != nil {
		t.PostorderTreeWalk(x.Left)
		t.PostorderTreeWalk(x.Right)
		fmt.Println(x.Key)
	}
}

查找

对一棵二叉搜索树进行查找是从树根开始查找，并沿着这棵树中的一条简单路径向下进行。

对于遇到的每个节点 x，比较关键字 k 与 x.key，查找逻辑遵循以下判断：

1. 如果两个关键字相等，查找就终止
2. 如果 k 小于 x.key,查找在 x 的左子树中继续
3. 如果 k 大于 x.key,查找在 x 的右子树中继续

伪代码

go 实现

func (t *BinarySearchTree) TreeSearch(x *Node, k int) *Node {
	if x == nil || k == x.Key {
		return x
	}
	if k < x.Key {
		return t.TreeSearch(x.Left, k)
	} else {
		return t.TreeSearch(x.Right, k)
	}
}

查找最大和最小关键字元素

通过从树根开始沿着 left 或 right 孩子指针直到遇到一个 nil，我们总能在一棵二叉搜索树中找到一个最小或最大元素。

查找最小元素伪代码

查找最小元素 go 实现

func (t *BinarySearchTree) FindMin() *Node {
	if t.IsEmpty() {
		return nil
	}
	return findMin(t.root)
}

func findMin(x *Node) *Node {
	for x.Left != nil {
		x = x.Left
	}
	return x
}

查找最大元素伪代码

查找最大元素 go 实现

func (t *BinarySearchTree) FindMax() *Node {
	if t.IsEmpty() {
		return nil
	}
	return findMax(t.root)
}
func findMax(x *Node) *Node {
	for x.Right != nil {
		x = x.Right
	}
	return x
}

后继和前驱

后继和前驱是一对相称的操作，下面只描述下后继的相关实现。

查找后继

如果所有的关键字互不相同，则一个节点 x 的后继是大于 x.key 的最小关键字的节点。

因为构造二叉搜索树的时候已经确定好节点与左右子树的大小关系了，所以一棵二叉搜索树的结构允许我们通过没有任何关键字的比较来确定一个节点的后继。

查找后继伪代码

查找后继 go 实现

func (t *BinarySearchTree) TreeSuccessor(x *Node) *Node {
	if x == nil {
		return nil
	}
	if x.Right != nil {
		return findMin(x.Right)
	} else {
		y := x.Parent
		for ; y != nil && x == y.Right; {
			x = y
			y = y.Parent
		}
		return y
	}
}

插入和删除

插入

插入以节点 z 作为输入，其中 z.key=v,z.left=nil,z.right=nil，这个过程需要修改树 T 和节点 z 的某些属性，来把 z 插入到树中的相应位置上。

插入 go 实现

func (t *BinarySearchTree) Insert(v int) {
	z := NewEmptyNode(v)
	x := t.Root
	var y *Node

	for ; x != nil; {
		y = x
		if z.Key < x.Key {
			x = x.Left
		} else {
			x = x.Right
		}
	}
	
	z.Parent = y
	if y == nil {
		t.Root = z
	} else if z.Key < y.Key {
		y.Left = z
	} else {
		y.Right = z
	}
}

定理

如果 x 是一棵有 n 个节点子树的根，那么调用中序遍历需要 O(n) 时间

证明：由于中序遍历需要访问这颗子树的全部 n 个节点，所以有中序遍历需要 O(n) 时间

在一棵高度为 h 的二叉搜索树上，动态集合上的操作 SEARCH,MINIMUM,MAXIMUM,SUCCESSOR 和 PREDECESSOR 可以在 O(h) 时间内完成

证明：因为以上过程或者遵从一条简单路径沿树向上或者遵从简单路径沿树向下，所以耗费的时间取决于树的高度，为 O(h)