Guidelines for labs
Take quiz & check grades
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|
|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|
|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
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.
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
usual operations are performed in O(lg n)
How do we implement the operations