randomized_select(A, low, high, index)
	if low == high
		return A[low]
	mid = randomized_partition(A, low, high)
	leftRange = mid - low + 1
	if index == leftRange
		return A[mid]
	elif index < leftRange
		return randomized_select(A, low, mid - 1, index)
	else
		return randomized_select(A, mid + 1, high, index - leftRange)

stack_empty(S)
	return S.top == 0

push(S, x)
	S.top++
	S[S.top] = x

pop(S)
	if stack_empty(S)
		error "underflow"
	else
		S.top--
		return S[S.top + 1]

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)

left_rotate(T, root)
	rChild = root.right
	root.right = rChild.left
	if rChild.left != T.null
		rChild.left.parent = root
	rChild.parent = root.parent
	if root.parent == T.null
		T.root = rChild
	elif root == root.parent.left
		root.parent.left = rChild
	else
		root.parent.right = rChild
	rChild.left = root
	root.parent = rChild