《Introduction to Algorithm》notes:Binary search tree

什么是Binary search tree(BST,二叉检索树)?首先，它是一个二叉树，其次，它是按照一定规则组织的二叉树，即左结点值比根节点值小，右结点值大于或等于根节点值，根据这种规则组织的二叉树就是BST。

Inorder-tree-walk

BST的一个很常见的应用就是，如果中序(inorder)遍历这棵树，可以得到一个递增的一组序列。

//pseudocode: INORDER-TREE-WALK
if x!=null
	inorder-tree-walk(x.left)
	print x.key
	inorder-tree-walk(x.right)

proof about inorder travel

如何证明中序遍历整棵树花了 Θ(n)的时间？ 1.因为必须遍历所有结点，所以此算法一定是Ω(n)的，下面只需证明此算法是O(n)的即可。 2.根据伪代码，可以得出 T(n)<=T(k)+T(n-k-1)+d，使用前面的substitution method就可以证明此算法是O(n)的。

Exercise

12.1-1

EASY.

12.1-2

What is the difference between the binary-search-tree property and the min-heap property (see page 153)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Show how, or explain why not.

Solution： 1.BST规定了左子结点小于根结点并且右子节点大于或等于根结点，而min-heap只要求其子结点小于根结点即可，没有对左和右各做要求。 2.用min-heap结构不能做到在O(n)的时间内打印出排序序列，如果能做到的话，那么就能有一个新的排序算法，这个基于比较的排序算法时间复杂度是o(n)，而根据decision tree的知识可知，基于比较的排序算法是Ω(nlogn)的。

12.1-3

Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)

Solution：

//Stack solution
	//function:push_left(root)
	while root!=null//这个函数将该结点的所有左子树压栈
			stack.push(root)
			root=root.left
	//main function
	while x!=null
		push_left(x)//左
		print(stack.pop())//中
		push_left(x.right)//右

//Two-pointer solution
while root!=null
	while root->left!=null&&!root.visit //如果root的left没有被visit过
		root=root->left //左
	if(!root.visit) print(root) root.visit=true
	if root->right!=null&&!root->right.visit
		root=root.right
	else
		root=root.parent

12.1-4

Give recursive algorithms that perform preorder and postorder tree walks in Θ(n) time on a tree of n nodes.

//pseudocode: PREORDER-TREE-WALK
if x!=null
	print x.key
	inorder-tree-walk(x.left)		
	inorder-tree-walk(x.right)
	
//pseudocode: PREORDER-TREE-WALK
if x!=null		
	inorder-tree-walk(x.left)		
	inorder-tree-walk(x.right)
	print x.key

12.1-5

Argue that since sorting n elements takes Ω(nlogn) time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements takes Ω(nlogn) time in the worst case.

跟12.1-2类似，基于比较，一定是Ω(nlogn)。

Operations about BST

一些很简单的操作比如SEARCH,MAXIMUM等就不提了，这里提两个之前较少遇到的操作。

Successor and predecessor

//Tree-successor. time complexity:O(h)
if x.right!=null
	return Tree-minimum(x.right) //如果x有右子树,那么返回右子树中的最小值
y=x.parent
if y!=null&& y.right==x //如果x是y的右子结点，继续往上，直到x是y的左子结点时(或y是null)终止循环
	x=y
	y=y.parent
return y

Exercise

12.2-2

Write recursive versions of TREE-MINIMUM and TREE-MAXIMUM.

//Tree-minmum(recursive version)
if x.left==null
	return x
return Tree-maximum(x.left)

//Tree-maximum(recursive version)
if x.right==null
	return x
return Tree-maximum(x.right)

12.2-3

Write the TREE-PREDECESSOR procedure.

//Tree-predecessor
if x.left!=null
	return Tree-maximum(x.left)
y=x.parent
while y!=null&&x==y.left
	x=y
	y=y.parent
return y

12.2-5

Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

如果一个结点有俩孩子结点，那么其successor必定是右子树中最小的，也就是右子树中最“左”的结点，必定没有左孩子，同样的，其predecessor必定是左子树中最大的，也就是左子树中最“右”的结点，必定没有右孩子。

Insert

//Insert(T,z)
y=null
x=T.root
while x!=null //x就是z应该在的位置，y是x的父结点
	y=x
	if z.key<x.key
		x=x.left
	else 
		x=x.right
z.parent=y
if y=null
	T.root=z
else if z.key<y.key
	y.left=z
else y.right=z

Deletion

BST的删除操作可分为以下3种情况。

If z has no children, then we simply remove it by modifying its parent to replace z with NIL as its child.如果z没有孩子，直接将它的父结点的孩子节点设为NIL
If z has just one child, then we elevate that child to take z’s position in the tree by modifying z’s parent to replace z by z’s child.z有一个孩子，那么直接replace即可
If z has two children, then we find z’s successor y—which must be in z’s right subtree—and have y take z’s position in the tree. The rest of ’s original right subtree becomes y’s new right subtree, and z’s left subtree becomes y’s new left subtree. This case is the tricky one because, as we shall see, it matters whether y is z’s right child.找到z的successor替代z即可。

看了一下算法导论上的deletion相关的代码，比大二上的算法课上的代码要复杂，其原因在于这里的BST中的结点是有parent这个属性的，所以必不可少的加了很多步骤来保证这个parent属性能够传递，没有parent属性的话代码会简化很多。

Exercise

12.3-1

Give a recursive version of the TREE-INSERT procedure.

//TREE-INSERT(recursive version)