Binary Search Trees

Binary Search Tree Property: Let $x$ be a node in a BST. If $y$ is a node in the left subtree of $x$, then $y.key\le x.key$. If $y$ is a node in the right subtree of $x$, then $y.key\ge x.key$

Preorder/inorderpostorder traversal

Querying a binary search tree:

Tree-Search procedure:

• To search for key $k$ in the entire BST

TREE-SEARCH(x,k)
if x == NIL or k == x.key
	return key
if k < x.key
	return TREE-SEARCH(x.left, k)
else return TREE-SEARCH(x.right, k)

ITERATIVE-TREE-SEARCH(x,k)
while x != NIL and k != x.key
	if k < x.key
		x = x.left
	else
		x = x.right
return x

TREE-Minimum(x)
while x.left != NIL
	x = x.left
return x

TREE-SUCCESSOR(x)
if x.right != NIL
	return TREE-MINIMUM(x.right)
else:
	y = x.p
	while y != NIL and x == y.right
		x = y
		y = y.p
	return y
	
	

The running time of TREE-SUCCESSOR on a tree of height $h$ is $O(h)$.

TREE-INSERT (T,z)
x = T.root // node being compared with z
y = NIL // y will be parent of z
while x != NIL // descend until reaching a leaf
	y = x
	if z.key  < x.key
		x = x.left
	 else 
		 x = x.right
 z.p = y // foud the location - insert z with parent y
 
 if y == NIL
	 T.root = z
 
 elseif z.key < y.key
	 y.left = z
 else y.right = z

Tree-TRANSPLANT(T, u, v)

TREE-DELETE(T,z)