University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

Trees (cont)

Orders for visiting nodes in a tree

bulletPre Order - root first, then left, then right
bulletIn Order - left first, then root, then right
bulletPost Order - left first, then right, then root

Rotations

bulletRotating a tree around a given node x will change the balancing of the tree.
bulletYou 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?

bulletperfect balance may require too much work
bulletthere are strategies to keep trees reasonably balanced

Red-Black Trees

bulletNodes have an additional field = color ... red or black
bulletLeaves are actually nodes with a special NULL flag

Properties of Red-Black Trees

  1. Every node is either Red or Black
  2. Every leaf is black
  3. If a node is Red, then both its children are black.
  4. 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

bulletinsert
bulletremove
bulletsearch