《算法导论》笔记3-12

二叉搜索树

递归查找：

tree_search(root, k)
	if root == null or k == root.key
		return root
	if k < root.key
		return tree_search(root.left, k)
	else
		return tree_search(root.right, k)

迭代查找：

tree_search(root, k)
	while root != null or k != root.key
		if k < root.key
			root = root.left
		else
			root = root.right
	return root

最大关键字元素和最小关键字元素：

tree_min(root)
	while root.left != null
		root = root.left
	return root

tree_max(root)
	while root.right != null
		root = root.right
	return root

插入：

tree_insert(T, node)
	parent = null
	root = T.root
	while root != null
		parent = root
		if node.key < root.key
			root = root.left
		else
			root = root.right
	node.parent = parent
	# 空树
	if parent == null
		T.root = node
	elif node.key < parent.key
		parent.left = node
	else
		parent.right = node

删除：

transplant(T, root, child)
	if root.parent == null
		T.root = child
	elif root == root.parent.left
		root.parent.left = child
	else
		root.parent.right = child
	if child != null
		child.parent = root.parent

tree_delete(T, node)
	if node.left == null
		transplant(T, node, node.right)
	elif node.right == null
		transplant(T, node, node.left)
	else
		minChild = tree_min(node.right)
		if minChild != node
			transplant(T, minChild, minChild.right)
			minChild.right = node.right
			minChild.right.parent = minChild
		transplant(T, node, minChild)
		minChild.left = node.left
		minChild.left.parent = minChild