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 |
Red-Black Trees
| Nodes have an additional field = color ... red or black |
| Leaves are actually nodes with a special NULL flag |
Properties of Red-Black 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 red-black 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
| insert |
| remove |
| search |