Lecture Notes for CS 512, Algorithm Design

Red-Black Trees - 7 February 2000

1. what's the matter with binary search trees?

   1. average case vs. worst case

   2. average case behavior is O(log n)

   3. worst case behavior is O(n)

2. binary search trees can become unbalanced

   1. tree height

   2. unbalanced trees have a significant difference between subtree heights

   3. constraining subtree height differences provides balance

      1. AVL trees limit the height difference to -1, 0, or 1

      2. strict constraints require more work

      3. and don't forget the O(log n) limit on operations

3. red-black trees

   1. a binary search tree

      1. nodes are either red or black

      2. leaves are special; leaves are black

      3. red parents don't have black children

      4. every root-leaf path has the same number of black nodes

   2. a rb tree's black height

   3. search(), min(), max(), succ(), pred() run in O(log n)

   4. insertion

      1. insert new values as in bst

      2. new nodes are red

   5. deletion

      1. splice out the deleted node

      2. the replacement node inherits the extra 1 if the deleted node was black

This page last modified on 14 February 2000.