Systemnahe Programmierung in Chome Systemnahe Programmierung in C: Binäre Suchbäume Prof. Dr. Uwe Schmidt FH Wedel
Dynamische Datenstrukturen
Einfach verkettete RingeInhaltsverzeichnisRot-Schwarz-Bäume

Binäre Suchbäume

weiter
weiter

Implementierung von binären Suchbäumen

Binäre Suchbäume
werden zu effizienten Implementierung von Mengen und Tabellen verwendet. Voraussetzung ist eine totale Ordnung auf dem Element- oder Schlüssel-Datentyp.
 
Die Typdefinition ist eine Erweiterung der für verkettete Listen: Pro Knoten werden anstatt einem zwei Nachfolger gespeichert, einen für alle kleineren und einen für alle größeren Elemente.
weiter
weiter

Die Schnittstelle: Element.h

   1#ifndef ELEMENT_H__
   2#define ELEMENT_H__ 1
   3
   4#if NUMELEM
   5
   6typedef int Element;
   7
   8#else
   9
  10typedef char * Element;
  11
  12#endif
  13
  14extern int compare(Element e1,
  15                   Element e2);
  16
  17#endif
weiter
weiter

Die Implementierung: Element.c

   1#include "Element.h"
   2
   3#if NUMELEM
   4
   5int
   6compare(Element e1, Element e2)
   7{
   8  return (e1 >= e2) - (e2 >= e1);
   9}
  10
  11#else
  12#include <string.h>
  13
  14int
  15compare(Element e1, Element e2)
  16{
  17  int rel = strcmp(e1, e2);
  18
  19  return rel == 0
  20    ? 0
  21    : rel > 0
  22      ? 1
  23      : -1;
  24}
  25#endif
weiter
weiter

Die Schnittstelle: Set.h

   1#ifndef SET_H__
   2#define SET_H__
   3
   4/*--------------------*/
   5
   6#include "Element.h"
   7
   8typedef unsigned int Nat0;
   9
  10typedef struct Node *Set;
  11
  12struct Node
  13{
  14  Element info;
  15  Set l;
  16  Set r;
  17};
  18
  19/*--------------------*/
  20
  21#if MACROS
  22
  23#define mkEmptySet() ((Set)0)
  24#define isEmptySet(s) ((s) == mkEmptySet())
  25
  26/*--------------------*/
  27
  28#else
  29
  30extern Set mkEmptySet(void);
  31extern int isEmptySet(Set s);
  32
  33#endif
  34
  35/*--------------------*/
  36
  37extern Set mkOneElemSet(Element e);
  38extern Set insertElem(Element e, Set s);
  39extern Set removeElem(Element e, Set s);
  40
  41extern int isInSet(Element e, Set s);
  42extern Nat0 card(Set s);
  43
  44extern Nat0 maxPathLength(Set s);
  45extern Nat0 minPathLength(Set s);
  46
  47extern int invSetAsBintree(Set s);
  48
  49extern int isBalancedBintree(Set s);
  50extern Set balanceBintree(Set s);
  51
  52/*--------------------*/
  53
  54#endif
weiter
weiter

Die Implementierung: Set.c

   1#include "Set.h"
   2
   3#include <stdlib.h>
   4#include <stdio.h>
   5#include <assert.h>
   6
   7/*--------------------*/
   8
   9#if ! MACROS
  10
  11Set
  12mkEmptySet(void)
  13{
  14  return (Set) 0;
  15}
  16
  17/*--------------------*/
  18
  19int
  20isEmptySet(Set s)
  21{
  22  return s == (Set) 0;
  23}
  24
  25#endif
  26
  27/*--------------------*/
  28
  29Set
  30mkOneElemSet(Element e)
  31{
  32  Set res = malloc(sizeof(*res));
  33
  34  if (!res)
  35    {
  36      perror("mkOneElemSet: malloc failed");
  37      exit(1);
  38    }
  39  res->info = e;
  40  res->l = mkEmptySet();
  41  res->r = mkEmptySet();
  42
  43  return res;
  44}
  45
  46/*--------------------*/
  47
  48int
  49isInSet(Element e, Set s)
  50{
  51  if (isEmptySet(s))
  52    return 0;
  53
  54  switch (compare(e, s->info))
  55    {
  56    case -1:
  57      return isInSet(e, s->l);
  58    case 0:
  59      return 1;
  60    case +1:
  61      return isInSet(e, s->r);
  62    }
  63
  64  assert(0);
  65  return 0;
  66}
  67
  68/*--------------------*/
  69
  70Set
  71insertElem(Element e, Set s)
  72{
  73  if (isEmptySet(s))
  74    return mkOneElemSet(e);
  75
  76  switch (compare(e, s->info))
  77    {
  78    case -1:
  79      s->l = insertElem(e, s->l);
  80      break;
  81    case 0:
  82      break;
  83    case +1:
  84      s->r = insertElem(e, s->r);
  85      break;
  86    }
  87
  88  return s;
  89}
  90
  91/*--------------------*/
  92
  93static int
  94lessThan(Set s, Element e)
  95{
  96  return
  97    (isEmptySet(s)
  98     || (compare(s->info, e) == -1
  99         &&
 100         lessThan(s->r, e)
 101         /*
 102         &&
 103         lessThan(s->l, e) is redundant */
 104         )
 105    );
 106
 107}
 108
 109/*--------------------*/
 110
 111static int
 112greaterThan(Set s, Element e)
 113{
 114  return
 115    (isEmptySet(s)
 116     || (compare(s->info, e) == +1
 117         &&
 118         greaterThan(s->l, e)
 119         /*
 120         &&
 121         greaterThan(s->r, e) is redundant */
 122        )
 123    );
 124}
 125
 126/*--------------------*/
 127
 128int
 129invSetAsBintree(Set s)
 130{
 131  return
 132    isEmptySet(s)
 133    || (lessThan(s->l, s->info)
 134        &&
 135        greaterThan(s->r, s->info)
 136        &&
 137        invSetAsBintree(s->l)
 138        &&
 139        invSetAsBintree(s->r));
 140}
 141
 142/*--------------------*/
 143
 144Nat0
 145card(Set s)
 146{
 147  if (isEmptySet(s))
 148    return 0;
 149
 150  return card(s->l) + 1 + card(s->r);
 151}
 152
 153/*--------------------*/
 154
 155static Nat0
 156max(Nat0 i, Nat0 j)
 157{
 158  return i > j ? i : j;
 159}
 160
 161/*--------------------*/
 162
 163static Nat0
 164min(Nat0 i, Nat0 j)
 165{
 166  return i < j ? i : j;
 167}
 168
 169/*--------------------*/
 170
 171Nat0
 172maxPathLength(Set s)
 173{
 174  if (isEmptySet(s))
 175    return 0;
 176
 177  return
 178    1 + max(maxPathLength(s->l),
 179            maxPathLength(s->r));
 180}
 181
 182/*--------------------*/
 183
 184Nat0
 185minPathLength(Set s)
 186{
 187  if (isEmptySet(s))
 188    return 0;
 189
 190  return
 191    1 + min(minPathLength(s->l),
 192            minPathLength(s->r));
 193}
 194
 195/*--------------------*/
 196
 197static Element
 198maxElem(Set s)
 199{
 200  assert(!isEmptySet(s));
 201
 202  if (isEmptySet(s->r))
 203    return s->info;
 204
 205  return maxElem(s->r);
 206}
 207
 208/*--------------------*/
 209
 210static Set
 211removeRoot(Set s)
 212{
 213  assert(!isEmptySet(s));
 214
 215  if (isEmptySet(s->l)
 216      || isEmptySet(s->r))
 217    {
 218      Set res =
 219        isEmptySet(s->l) ? s->r : s->l;
 220      free(s);
 221      return res;
 222    }
 223
 224  assert(!isEmptySet(s->l));
 225  assert(!isEmptySet(s->r));
 226
 227  s->info = maxElem(s->l);
 228  s->l = removeElem(s->info, s->l);
 229
 230  return s;
 231}
 232
 233/*--------------------*/
 234
 235Set
 236removeElem(Element e, Set s)
 237{
 238  if (isEmptySet(s))
 239    return s;
 240
 241  switch (compare(e, s->info))
 242    {
 243    case -1:
 244      s->l = removeElem(e, s->l);
 245      break;
 246    case 0:
 247      s = removeRoot(s);
 248      break;
 249    case +1:
 250      s->r = removeElem(e, s->r);
 251      break;
 252    }
 253
 254  return s;
 255}
 256
 257/*--------------------*/
 258
 259static Set
 260flat(Set s, Set res)
 261{
 262  if (isEmptySet(s))
 263    return res;
 264
 265  s->r = flat(s->r, res);
 266
 267  return flat(s->l, s);
 268}
 269
 270/*--------------------*/
 271
 272static Set
 273balance(Set s, Nat0 length)
 274{
 275  if (length == 0)
 276    return mkEmptySet();
 277
 278  {
 279    Nat0 rootPos = length / 2;
 280    Set root = s;
 281
 282    while (rootPos--)
 283      root = root->r;
 284
 285    root->l = balance(s, length / 2);
 286    root->r = balance(root->r,
 287                      length -
 288                      length / 2 - 1);
 289    return root;
 290  }
 291}
 292
 293/*--------------------*/
 294
 295int
 296isBalancedBintree(Set t) {
 297  return
 298    maxPathLength(t) -
 299    minPathLength(t) <= 1;
 300}
 301
 302Set
 303balanceBintree(Set t)
 304{
 305  Nat0 length = card(t);
 306
 307  Set res = balance(flat(t,
 308                         mkEmptySet()),
 309                    length);
 310
 311  assert(isBalancedBintree(res));
 312
 313  assert(card(res) == length);
 314
 315  assert(invSetAsBintree(res));
 316
 317  return res;
 318}
 319
 320/*--------------------*/
weiter
weiter

Ein einfacher Test: RandTest.c

   1#include <stdlib.h>
   2#include <stdio.h>
   3#include <assert.h>
   4
   5#include "Element.h"
   6#include "Set.h"
   7
   8int
   9main(int argc, char *argv[])
  10{
  11  unsigned int noOfElems = 1000;
  12
  13  if (argc == 2)
  14    sscanf(argv[1], "%u", &noOfElems);
  15
  16  fprintf(stdout,
  17          "%s %u %s",
  18          "run binary search trees with inserting",
  19          noOfElems,
  20          "elements in random order\n"
  21          );
  22
  23  {
  24    Set s = mkEmptySet();
  25    unsigned int i;
  26
  27    for (i = 0; i < noOfElems; ++i)
  28      {
  29        s = insertElem((Element)rand(), s);
  30      }
  31
  32    fprintf(stdout,
  33            "card(s)          = %u\n",
  34            card(s));
  35    fprintf(stdout,
  36            "minPathLength(s) = %u\n",
  37            minPathLength(s));
  38    fprintf(stdout,
  39            "maxPathLength(s) = %u\n",
  40            maxPathLength(s));
  41  }
  42
  43  return 0;
  44}
weiter
weiter

Die make Regeln: Makefile

# $Id: Makefile,v 1.2 2011/12/19 19:11:03 uwe Exp $
SRC = Set.c Element.c
HDR = $(SRC:.c=.h)
TESTS = $(TEST) $(PROF)
CARD = 1000
TEST = ./Test
PROF = ./ProfTest
RAND = ./RandTest
time = /usr/bin/time --format="runtime was %U sec"
include ../rules.mk
##all
## make all targets
## for normal version: all1
## without debug: ndebug
## and for iterative versions: iterative
all :
$(MAKE) clean all1 macros
all1 : $(OASS) $(TESTS)
##macros
## compile with macros and without assertions
macros :
$(MAKE) clean
$(MAKE) all1 CCFLAGS='$(CCFLAGS) -DMACROS=1 -DNDEBUG=1'
$(TEST) : Test.c $(OBJ)
$(CC) -o $@ Test.c $(OBJ) $(CCFLAGS)
$(RAND) : RandTest.c $(SRC) $(HDR)
$(CC) -o $@ RandTest.c $(OBJ) $(CCFLAGS) -DNUMELEM=1 -DNDEBUG=1
$(PROF) : ProfTest.c $(SRC) $(HDR)
$(CC) -o $@ -pg ProfTest.c $(CCFLAGS) -DNUMELEM=1 -DNDEBUG=1
prf : $(PROF)
rnd : $(RAND)
num :
rm -f *.o Test
$(MAKE) $(OBJ) $(TEST) CCFLAGS='$(CCFLAGS) -DNUMELEM=1 -DNDEBUG=1'
run :
@$(time) $(TEST) $(CARD)
1k :
$(MAKE) run CARD=1000
10k :
$(MAKE) run CARD=10000
20k :
$(MAKE) run CARD=20000
40k :
$(MAKE) run CARD=40000
rrun :
@$(time) $(RAND) $(CARD)
r1k :
$(MAKE) rrun CARD=1000
r10k :
$(MAKE) rrun CARD=10000
r20k :
$(MAKE) rrun CARD=20000
r40k :
$(MAKE) rrun CARD=40000
r1M :
$(MAKE) rrun CARD=1000000
prun : $(PROF)
rm -f gmon.out
$(PROF) $(CARD)
gprof --brief $(PROF) gmon.out
p10k :
$(MAKE) prun CARD=10000
weiter
weiter

Übersetzen: Test mit Zufallszahlen

make rnd
weiter
weiter

Test: Zufälliges Einfügen mit 10.000 Elementen

make rrun CARD=10000
weiter
weiter

Test: Zufälliges Einfügen mit 20.000 Elementen

make rrun CARD=20000
weiter
weiter

Test: Zufälliges Einfügen mit 40.000 Elementen

make rrun CARD=40000
weiter
weiter

Test: Zufälliges Einfügen mit 1.000.000 Elementen

make rrun CARD=1000000
weiter
weiter

Übersetzen: Worst-Case-Test

make num
weiter
weiter

Worst-Case-Test: Sortiertes Einfügen mit 10.000 Elementen

make run CARD=10000
weiter
weiter

Worst-Case-Test: Sortiertes Einfügen mit 20.000 Elementen

make run CARD=20000
weiter
weiter

Worst-Case-Test: Sortiertes Einfügen mit 40.000 Elementen

make run CARD=40000
weiter
weiter

Übersetzen: Worst-Case-Test mit Profiling

make prf
weiter
weiter

Worst-Case-Test: Sortiertes Einfügen mit 20.000 Elementen

make prun CARD=20000
weiter
weiter

Download

Quellen
Element.h
Element.c
Set.h
Set.c
Makefile
SeitenanfangDynamische Datenstrukturen
Einfach verkettete RingeInhaltsverzeichnisRot-Schwarz-Bäume
Letzte Änderung: 06.01.2014
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel