RedBlackBST Review

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

Complexity

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

<CLRS#3>

Not figure out yet…

<Algorithm#4>

RedBlackBST

class Node:
	size:1
	color:BLACK
	Node left,right
  key
  val
    
size(x):
	if x == NIL
    return 0
	return size(x.left) + size(x.right) + 1

isRed(x):
	if x == NIL
    return False
  return x.color == RED

rotateLeft(x):
	y = x.right
	x.right = y.left
	y.left = x
	y.color = y.left.color
	y.left.color = RED
	y.size = x.size
	x.size = 1 + size(x.left) + size(x.right)
	return y
	
rotateRight(x):
	y = x.left
	x.left = y.right
	y.right = x
	y.color = y.right.color
	y.right.color = RED
	y.size = x.size
	x.size = 1 + size(x.left) + size(x.right)
	return y
	
flipColors(x):
	if x != NIL and x.left != NIL and x.right != NIL
		x.color = !x.color
		x.left.color = !x.left.color
		x.right.color = !x.right.color
	return x

put(x,key,val):
	if x == NIL
		return new Node(k,val,1,RED)
	if key < x.key
		put(x.left,key,val)
	elif key > x.key
		put(x.right,key,val)
	else x.val = val
	x = balance(x)
	return x

balance(x):
	if !x.left.isRed() and x.right.isRed()
		x = rotateLeft(x)
	if x.left.isRed() and x.left.left.isRed()
		x = rotateRight(x)
	if x.left.isRed() and x.right.isRed()
		x = flipColor(x)
	x.size = size(x.left) + size(x.right) + 1
	return x

// assume that x is red, x.left and x.left.left is black
// make x.left or sub-node of x.left color to red
moveRedLeft(x):
	flipColor(x)
	if x.right.left.isRed()
		x.right = rotateRight(x.right)
    x = rotateLeft(x)
  return x

deleteMin(x):
	if x.left == NIL
		return NIL
	if !x.left.isRed() and !x.left.left.isRed()
		x = moveRedLeft(x)
	x.left = deleteMin(x.left)
	x = balance(x)
	return x

// assume that x is red, x.right and x.right.left is black
// make x.right or sub-node of x.right color to red
moveRedRight(x):
	flipColor(x)
	if !x.left.left.isRed
		x = rotateRight(x)
	return x

deleteMax(x):
	if x.left.isRed()
		x = rotateRight(x)
	if x == NIL
		return NIL
	if !x.right.isRed() and !x.right.left.isRed()
		x = moveRedRight(x)
	x.right = deleteMax(x.right)
	x = balance(x)
	return x

// turn to delete deleteMin or deleteMax
delete(x, key):
	if key < x.key
    if !x.left.isRed() and !x.left.left.isRed()
      x = moveLeftRed(x)
     x.left = delete(x.left,key)
  else
    if x.left.isRed()
      x = rotateRight(x)
    if key == x.key and x.right == NIL
      return NIL
    if !x.right.isRed() and !x.right.left.isRed()
      x = moveRedRight(x)
    if key == x.key
      minKey = min(x.right)
      minVal = minKey.val
      x.val = get(x.right, minVal)
      x.key = minKey
      x.right = deleteMin(x.right)
    else
      x.right = delete(x.right,key)
  x = balance(x)
  return x