BinarySearchTree Review

This is a review about BinarySearchTree by CLRS#3 & Algorithm#4.

Complexity

• Average function
  $$
  T(n) = \Theta(\lg{n})
  $$

<CLRS#3>

BST

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

TREE-MINIMUN(x)
  while x != NIL
    x = x.left
  return x
    
TREE-MAXIMUN(x)
  while x != NIL
    x = x.right
  return x

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

TREE-INSERT(T,z)
  y = NIL
  x = T.root
  while x != NIL
    y = x
    if z.key < x.key
      x = x.left
    else x = x.right
  z.p = y
  if y == NIL
    T.root = z
  elif z.key < y.key
    y.left = z
  else y.right = z

TRANSPLANT(T,u,v)
  if u.p == NIL
    T.root = v
  elif u == u.p.left
    u.p.left = v
  else u.p.right = v
  if v != NIL
    v.p = u.p

TREE-DELETE(T,z)
  if z.left == NIL
    TRANSPLANT(T,z,z.right)
  elif z.right == NIL
    TRANSPLANT(T,z,z.left)
  else
    y = TREE-MINIMUM(z.right)
    if y.p != NIL
      TRANSPLANT(T,y,y.right)
      y.right = z.right
      y.right.p = y
    TRANSPLANT(T,z,y)
    y.left = z.left
    y.left.p = y

<Algorithm#4>

BST

class Node:
  Key key
  Value val
  Node left, right
  size //intger

size():
	return size(ROOT)
	
size(node):
	if node == NIL
		return 0
	return size(node.left) + size(node.right) + 1

get(Key):
	return get(ROOT,Key)
	
get(node,key):
	if key == NIL
    return NIL
  elif key < node.key
    return get(node.left,key)
  elif key > node.key
    return get(node.right,key)
  else return node.val

put(Key,VALUE):
	put(ROOT,KEY,VALUE)
	
put(node,key,val):
	if node == NIL
		return new Node(key,val,1)
  if key < node.key
    put(node.left,key,val)
  elif key > node.key
    put(node.right,key,val)
  else node.val = val
  node.size = size(node.left) + size(node.right) + 1

max():
	return max(ROOT)

max(node):
	if node.right == NIL
    return node
	return max(node.right)

min():
	return min(ROOT)

min(node):
	if min.left == NIL
    return node
	return min(node.right)

// round down
floor(KEY):
	return floor(ROOT,KEY)
    
floor(node,key):
	if node == NIL
    return NIL
  if key == node.key
    return node
  elif key < node.key
    return floor(node.left,key)
  t = floor(node.right,key)
  if t == NIL
    return node
  else return t

// round up
ceiling(KEY):
	return ceiling(ROOT,KEY)
    
ceiling(node,key):
	if node == NIL
    return NIL
  if key == node.key
    return node
  elif key > node.key
    return ceiling(node.right,key)
  t = ceiling(node.left,key)
  if t == NIL
    return node
  else return t

// find rank k node
select(k):
	select(ROOT,k)

select(node,k):
	if node == NIL
    return NIL
  t = node.left.size
  if k < t
    return select(node.left,k)
  elif k > t
    return select(node.right,k-t-1)
  else return node

// find size of smaller than KEY
rank(KEY):
	rank(ROOT,KEY)
    
rank(node,key):
	if node == NIL
    return 0
  if key < node.key
    return rank(node.left,key)
  elif k > node.key
    return 1 + size(node.left) + rank(node.right.key)
  else return node.left.size

// just delete min node
deleteMin():
	return deleteMin(ROOT)
    
deleteMin(node):
	if node.left == NIL
    return node.right
  node.left = deleteMin(node.left)
  node.size = size(node.left) + size(node.right) + 1
  return node
    
// just delete max node
deleteMax():
   return deleteMax(ROOT)
    
deleteMax(node):
	if node.right == NIL
    return node.left
  node.right = deleteMax(node.right)
  node.size = size(node.left) + size(node.right) + 1
  return node
    
// delete KEY
delete(KEY):
	delete(ROOT,KEY)
    
delete(node,key):
	if node == NIL
    return NIL
  if key < node.key
    node.left = delete(node.left,key)
  elif key > node.key
    node.right = delete(node.right,key)
  else
    if node.right == NIL
      return node.left
    if node.left == NIL
      return node.right
    successor = min(node.right)
    successor.right = deleteMin(node.right)
    successor.left = node.left
  successor.size = size(successor.left) + size(successor.right) + 1
  return successor