Systemnahe Programmierung in C: Rot-Schwarz-Bäume

Rot-Schwarz-Bäume	sind Binärbäume, die beim Einfügen "on the fly" ausbalanciert werden.
	Zusätzlich zu Binärbäumen wird in jedem Knoten eine Farbe gespeichert, und zwar gibt es rote und schwarze Knoten. Diese Zusatzinformation wird nur beim Einfügen und Löschen von Elementen berücksichtigt. Das Suchen läuft wie bei einfachen binären Bäumen.
	Ein Rot-Schwarz-Baum muss folgende Balance-Invarianten erfüllen: Kein roter Knoten besitzt einen roten Kindknoten. Jeder Pfad von der Wurzel zu einem leeren Baum enthält die gleiche Anzahl von schwarzen Knoten. Leere Bäume werden immer als schwarz eingefärbt betrachtet.
	Diese beiden Invarianten garantieren, dass der längste mögliche Pfad in einem Rot-Schwarz-Baum, einer mit abwechselnd schwarzen und roten Knoten, höchstens doppelt so lang sein kann, wie der kürzeste, der nur schwarze Knoten enthält.
	Daraus folgt, dass die maximale Tiefe eines Baumes mit n Elementen höchstens `2 * log2 (n + 1)` sein kann.
	Beim Einfügen wird der Baum auf dem Weg von der Einfügestelle zurück zur Wurzel an den Stellen ausbalanciert, an denen zwei rote Knoten entstanden sind. Neu eingefügte Knoten werden immer als rot markiert.
	Das Löschen läuft prinzipiell genauso ab wie das Einfügen, nur können dabei doppelt schwarze Knoten entstehen, d.h. schwarze Knoten, die beim Zählen das Gewicht 2 haben. Diese werden durch lokale Umstrukturierung auf dem Rückweg zur Wurzel wieder eliminiert. Die Löschroutinen werden in diesem Beispiel nicht behandelt.
	Die Typdefinition ist eine Erweiterung der für binäre Bäume: Pro Knoten wird zusätzlich eine Farbe gespeichert.
	Diese Beispiel-Implementierung lässt noch Speilraum für lokale Optimierungen. Einmal können die einfachen Funktionen, insbesondere die Hilfsfunktionen, zum Teil durch Makros einkopiert werden. Weiter kann das Ausbalancieren vebessert werden: Wenn in den linken Teilbaum eingefügt wird, muss auch nur der linke Baum auf Ausgewogenheit getestet werden. Analoges gilt für den rechten Teilbaum. Die kritischen Funktionen erkennt man mit einem Profiling-Lauf.

#include "Set.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
/*--------------------*/
/* special empty node, marked as black */
static struct Node finalNode = { BLACK }; 
Set
mkEmptySet(void)
{
  return &finalNode;
}
/* local optimization */
#define mkEmptySet() (&finalNode)
/*--------------------*/
int
isEmptySet(Set s)
{
  return s == &finalNode;
}
/* local optimization */
#define isEmptySet(s) ((s) == &finalNode)
/*--------------------*/
/* auxiliary function: file scope */
static Set
mkNewRedNode(Element e)
{
  Set res = malloc(sizeof(*res));
  if (!res)
    {
      perror
        ("mkNewNode: malloc failed");
      exit(1);
    }
  res->color = RED;             /* every new node is red */
  res->info = e;
  res->l = mkEmptySet();
  res->r = mkEmptySet();
  return res;
}
/*--------------------*/
Set
mkOneElemSet(Element e)
{
  return insertElem(e, mkEmptySet());
}
/*--------------------*/
int
isInSet(Element e, Set s)
{
  if (isEmptySet(s))
    return 0;
  switch (compare(e, s->info))
    {
    case -1:
      return isInSet(e, s->l);
    case 0:
      return 1;
    case +1:
      return isInSet(e, s->r);
    }
  assert(0);
  return 0;
}
/*--------------------*/
/* color predicates */
#define isBlackNode(s) ((s)->color == BLACK)
#define isRedNode(s) (! isBlackNode(s))
static int
hasRedChild(Set s)
{
  return
    ! isEmptySet(s)
    && (isRedNode(s->l)
        ||
        isRedNode(s->r));
}
/*--------------------*/
/* reorganize tree */
static Set
balanceTrees(Set x, Set y, Set z,
             Set b, Set c)
{
  x->r = b;
  z->l = c;
  y->l = x;
  y->r = z;
  x->color = BLACK;
  z->color = BLACK;
  y->color = RED;
  return y;
}
/* check invariant */
/* check balance in left subtree */
static Set
checkBalanceLeft(Set s)
{
  assert(!isEmptySet(s));
  /* no balancing of trees with red root */
  if (isRedNode(s))
    return s;
  if (isRedNode(s->l)
      && isRedNode(s->l->l))
    return balanceTrees(s->l->l,
                        s->l,
                        s,
                        s->l->l->r,
                        s->l->r);
  if (isRedNode(s->l)
      && isRedNode(s->l->r))
    return balanceTrees(s->l,
                        s->l->r,
                        s,
                        s->l->r->l,
                        s->l->r->r);
  return s;
}
/* check balance in right subtree */
static Set
checkBalanceRight(Set s)
{
  assert(!isEmptySet(s));
  /* no balancing of trees with red root */
  if (isRedNode(s))
    return s;
  if (isRedNode(s->r)
      && isRedNode(s->r->l))
    return balanceTrees(s,
                        s->r->l,
                        s->r,
                        s->r->l->l,
                        s->r->l->r);
  if (isRedNode(s->r)
      && isRedNode(s->r->r))
    return balanceTrees(s,
                        s->r,
                        s->r->r,
                        s->r->l,
                        s->r->r->l);
  return s;
}
/*--------------------*/
static Set
insertElem1(Element e, Set s)
{
  if (isEmptySet(s))
    return mkNewRedNode(e);
  switch (compare(e, s->info))
    {
    case -1:
      s->l = insertElem1(e, s->l);
      /* invariant is checked with left subtree */
      return checkBalanceLeft(s);
    case 0:
      break;
    case +1:
      s->r = insertElem1(e, s->r);
      /* invariant is checked with right subtree */
      return checkBalanceRight(s);
    }
  return s;
}
/*--------------------*/
Set
insertElem(Element e, Set s)
{
  Set res = insertElem1(e, s);
  /* the root is always black */
  res->color = BLACK;
  assert(invSetAsRedBlackTree(res));
  return res;
}
/*--------------------*/
static int
lessThan(Set s, Element e)
{
  return
    isEmptySet(s)
    || (compare(s->info, e) == -1
        && lessThan(s->r, e));
}
/*--------------------*/
static int
greaterThan(Set s, Element e)
{
  return
    isEmptySet(s)
    || (
        compare(s->info, e) == +1
        &&
        greaterThan(s->l, e));
}
/*--------------------*/
static int
invSetAsBinTree(Set s)
{
  return
    isEmptySet(s)
    || (
        lessThan(s->l, s->info)
        &&
        greaterThan(s->r, s->info)
        &&
        invSetAsBinTree(s->l)
        &&
        invSetAsBinTree(s->r));
}
/*--------------------*/
static int
invNoRedNodeHasRedChild(Set s)
{
  if (isEmptySet(s))
    return 1;
  return
    (isBlackNode(s)
     ||
     ! hasRedChild(s)
    )
    &&
    invNoRedNodeHasRedChild(s->l)
    &&
    invNoRedNodeHasRedChild(s->r);
}
/*--------------------*/
static int
noOfBlackNodes(Set s)
{
  if (isEmptySet(s))
    return 1;
  {
    int nl = noOfBlackNodes(s->l);
    int nr = noOfBlackNodes(s->r);
    if (nl == nr && nl != -1)
      return nl + isBlackNode(s);
    /* invariant does not hold */
    return -1;
  }
}
/*--------------------*/
int
invSetAsRedBlackTree(Set s)
{
  return
    invSetAsBinTree(s)
    &&
    invNoRedNodeHasRedChild(s)
    &&
    noOfBlackNodes(s) != -1;
}
/*--------------------*/
unsigned int
card(Set s)
{
  if (isEmptySet(s))
    return 0;
  return card(s->l) + 1 + card(s->r);
}
/*--------------------*/
static unsigned int
max(unsigned int i, unsigned int j)
{
  return i > j ? i : j;
}
/*--------------------*/
static unsigned int
min(unsigned int i, unsigned int j)
{
  return i < j ? i : j;
}
/*--------------------*/
unsigned int
maxPathLength(Set s)
{
  if (isEmptySet(s))
    return 0;
  return
    1 + max(maxPathLength(s->l),
            maxPathLength(s->r));
}
/*--------------------*/
unsigned int
minPathLength(Set s)
{
  if (isEmptySet(s))
    return 0;
  return
    1 + min(minPathLength(s->l),
            minPathLength(s->r));
}
/*--------------------*/

Rot-Schwarz-Bäume

Implementierung von Rot-Schwarz-Bäumen

Die Schnittstelle: Element.h

Die Implementierung: Element.c

Die Schnittstelle: Set.h

Die Implementierung: Set.c

Ein einfacher Test: Test.c

Übersetzen:

worst case Test: Sortiertes Einfügen mit 7 Elementen

worst case Test: Sortiertes Einfügen mit 100.000 Elementen

worst case Test: Sortiertes Einfügen mit 1.000.000 Elementen

worst case Test: Sortiertes Einfügen mit 2.000.000 Elementen

worst case Test: Sortiertes Einfügen mit 4.000.000 Elementen

worst case Test: Sortiertes Einfügen mit 8.000.000 Elementen

Testreihe: 1, 2, 4 und 8M Elemente

Test mit Profiling: Sortiertes Einfügen mit 1.000.000 Elementen

Download