Introduction to Algorithms/Balanced Search Tree

set Video Link

Search tree data structure maintaining dynamic set of $n$ elems using tree og height $O(\lg n)$.

Examples:

• AVL trees
• 2-3 trees
• 2-3-4 trees
• B-trees
• Red-black trees
• Skip lists
• Treaps

Red-black trees

BST data structure with extra color field for each node, satisfying: red-black properties:

1. Every node is either red or black.
2. The root and leaves (nil’s) are black.
3. Every red node has black parent.
4. All simple paths from node $x$ to a descendant leaf of $x$ have same # block nodes = black-height(x). (black height does not count $x$ itself).

Height of red-black tree

Red-black tree with $n$ keys has height $h\leqslant 2\lg (n+1)$.

Proof of sketch:

• merge each red node with its black parent $\to$ 2-3-4 tree. Height of new tree is $h’$
  • every internal node has 2-4 children.
  • every leaf has same depth, namely black-height of root.

How many leaves? $n+1$. And in 2-3-4 trees,$2^{h’}\leqslant$ # leaves $\leqslant 4^{h’}$ $\implies h’\leqslant \lg (n+1)$.

Using property 3, $h\leqslant 2h’=2\lg (n+1)$.

Corollary

Queries (search,min,max,successor,predecessor) run in $O(\lg n)$ in a red-black tree.

Updates: (insert or delete) modify the tree

• BST operation
• color changes
• restructuring of links via rotations

Rotation

preserves BST property.($O(1)$)

RB-Insert

Idea:

• Tree-Insert(x)
• Pick color red.
• Problem: parent is red.
• Fix: move the violation of 3 up the tree via recolorintg until we can fix the violation by rotation and recoloring.

RB-Insert(T,x):
	Tree-Insert(T,x)
	color[x]<-RED
	while x is not root[T] and color[x] is RED:
		if p[x] is left[p[p[x]]]:
			y <- right[p[p[x]]] # uncle
			if color[y] is RED:
				# case 1
				Recolor(p[x])
				Recolor(p[p[x]])
				Recolor(y)
				x = p[p[x]]
				continue
			else:
				if x is right[p[x]]:
					# case 2
					Left-Rotate(p[x])
					x = p[x]
				# case 3
				Right-Rotate(p[p[x]])
				Recolor(x)
				Recolor(p[x])
				Recolor(right(p[x]))
		else:
			# reversing notions of left and right
	color[root[T]] = BLACK

Time: $O(\lg n)$. # Rotation $=O(1)$.