Introduction
Syllabus
Guidelines for labs
Lab sections
Take quiz & check grades
 
Trees (cont)
Orders for visiting nodes in a tree
 Pre Order  root first, then left, then right 
 In Order  left first, then root, then right 
 Post Order  left first, then right, then root 
Rotations
 Rotating a tree around a given node x will change the balancing of the tree. 
 You may rotate to the right or to the left. 
Trees are great when they are balanced, but tragic if they go out of balance.
How do you keep a tree balanced?
 perfect balance may require too much work 
 there are strategies to keep trees reasonably balanced 
RedBlack Trees
 Nodes have an additional field = color ... red or black 
 Leaves are actually nodes with a special NULL flag 
Properties of RedBlack Trees
 Every node is either Red or Black
 Every leaf is black
 If a node is Red, then both its children are black.
 Every simple path from a node to a descendant leaf contains the same number of black
nodes.
Definition:
Black height bh(x) of a node x, is the number of black nodes on any path from,
but not including node x, to a leaf.
Lemma:
A redblack tree with n internal nodes hs height at most 2 lg(n+1)
which means... the heigh h of the tree h <= 2 bh
Consequences:
usual operations are performed in O(lg n)
How do we implement the operations
