Algorithmen und Datenstrukturen in Chome Algorithmen und Datenstrukturen 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/* $Id: Element.h,v 1.4 2011/12/19 19:11:03 uwe Exp $ */
   5
   6#if NUMELEM
   7
   8typedef int Element;
   9
  10#else
  11
  12typedef char * Element;
  13
  14#endif
  15
  16extern int compare(Element e1,
  17                   Element e2);
  18
  19#endif
weiter
weiter

Die Implementierung: Element.c

   1static char version[]
   2  ="$Id: Element.c,v 1.5 2011/12/19 19:11:03 uwe Exp $";
   3
   4#include "Element.h"
   5
   6#if NUMELEM
   7
   8int
   9compare(Element e1, Element e2)
  10{
  11  return (e1 >= e2) - (e2 >= e1);
  12}
  13
  14#else
  15#include <string.h>
  16
  17int
  18compare(Element e1, Element e2)
  19{
  20  int rel = strcmp(e1, e2);
  21
  22  return rel == 0
  23    ? 0
  24    : rel > 0
  25      ? 1
  26      : -1;
  27}
  28#endif
weiter
weiter

Die Schnittstelle: Set.h

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

Die Implementierung: Set.c

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

Download

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