// Binärer Baum, ganz simpel: Als Daten dient eine nichtnegative ganze Zahl.
//
// Aufruf: baum
//
// Klaus Kusche, 2012

// Tuning-Parameter für das Hauptprogramm: 
// Umläufe der äußeren Schleife:
// Nach jedem Umlauf werden Statistiken ausgegeben
// und der Baum auf Konsistenz geprüft 
#define NUM_TESTRUNS 30
// Inserts / Deletes pro Umlauf 
#define OPS_PER_RUN 30000
// Anzahl der möglichen Schlüsselwerte
// (je weniger, umso kleiner der Baum und umso größer der Anteil der Deletes)
#define KEY_RANGE 100000 
// Soll der Baum nach jedem Umlauf ausgegeben werden?
#define PRINT_TREE 0

// assert() muss immer Code generieren ==> NDEBUG abschalten!
#undef NDEBUG

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <assert.h>

// die einzelnen Baumknoten: Wert + 3 Pointer
typedef struct Node
{
    int key;
    struct Node *left, *right, *up;
} Node;

Node *mkNode(int key, const Node *up);
void delNode(Node *p);
Node *recCopy(const Node *p, Node *up);
Node *copy(const Node *p);
Node *leftMost(const Node *p);
bool Insert(Node **root, int val);
bool Delete(Node **root, int val);
bool Exists(const Node *root, int val);
int getFirst(const Node *root);
int getNext(const Node *root, int val);
int recSize(const Node *p);
int getSize(const Node *root);
bool isEmpty(const Node *root);
void recStats(const Node *p, int h, int *elemCnt, int *sumH, int *maxH);
void printStats(const Node *root);
void recCheck(const Node *p);
void checkTree(const Node *root, int n);

// Legt einen neuen Knoten mit den angegebenen Werten dynamisch an
// Die Söhne werden auf NULL gesetzt
// Returnwert: Pointer auf den neuen Knoten
Node *mkNode(int key, const Node *up)
{
  Node *p;

  p = (Node *) (malloc(sizeof(Node)));
  if (p == NULL) {
    fprintf(stderr, "Out of memory!\n");
    exit(EXIT_FAILURE);
  }
  
  p->key = key;
  p->left = NULL;
  p->right = NULL;
  p->up = (Node *) up;        // const weg-casten
  return p;
}

// Löscht einen Knoten samt Unterbäumen (incl. free())
void delNode(Node *p)
{
  assert(p);
  
  if (p->left) {
    assert(p->left->up == p);
    delNode(p->left);
  }
  if (p->right) {
    assert(p->right->up == p);
    delNode(p->right);
  }
  
  free(p);
}

// Rekursives Kopieren:
// Liefert einen Pointer auf eine Kopie des Teilbaumes p,
// wobei up als up-Pointer in der Kopie von p eingetragen wird
// p darf NULL sein ==> Ergebnis auch NULL
Node *recCopy(const Node *p, Node *up)
{
  Node *newP;
  
  if (p == NULL) return NULL;
  
  newP = mkNode(p->key, up);
  newP->left = recCopy(p->left, newP);
  newP->right = recCopy(p->right, newP);
  return newP;
}

Node *copy(const Node *root)
{
  return recCopy(root, NULL);
}

// Baum links absteigen: Liefert den linkesten (kleinsten) Knoten des Teilbaumes p
// p darf nicht NULL sein, und es kommt auch nie NULL zurück
Node *leftMost(const Node *p)
{
  assert(p);  // sollte nie mit p==NULL aufgerufen werden
  while (p->left) p = p->left;
  return (Node *)p; // const weg-casten
}

// füge "val" ein
// Returnwert: true wenn ok, false wenn schon vorhanden
bool Insert(Node **root, int val)
{
  // **-Trick:
  // ptr zeigt auf den Pointer, an dem der aktuelle Knoten hängt
  // bzw. am Ende auf den NULL-Pointer, wo er angehängt gehört
  Node **ptr = root;
  // Aktueller Knoten: Inhalt des Pointers, auf den ptr zeigt
  Node *p;
  // Vater = voriger p
  Node *father = NULL;    

  assert(val >= 0);

  for (;;) {
    p = *ptr;
    if (p == NULL) {
      // nicht gefunden: Neuen Knoten an *ptr anhängen
      *ptr = mkNode(val, father);
      return true;
    } else if (val < p->key) {
      ptr = &(p->left);
    } else if (val > p->key) {
      ptr = &(p->right);
    } else {
      // val == p->key: Es gibt schon einen Knoten mit diesem val!
      return false;
    }
    father = p;
  }
}

// lösche "val"
// Returnwert: true wenn ok, false wenn nicht vorhanden
bool Delete(Node **root, int val)
{
  // **-Trick:
  // ptr zeigt auf den Pointer, an dem der aktuelle Knoten hängt
  // bzw. am Ende auf den NULL-Pointer, wo er angehängt gehört
  Node **ptr = root;
  // Aktueller Knoten: Inhalt des Pointers, auf den ptr zeigt
  Node *p;
  // Vater = voriger p
  Node *father = NULL;
  // Wenn p gelöscht wird: Sohn bzw. Nachfolger von p
  Node *q;  

  assert(val >= 0);

  for (;;) {
    p = *ptr;
    if (p == NULL) {
      // nicht gefunden
      return false;
    } else if (val < p->key) {
      ptr = &(p->left);
    } else if (val > p->key) {
      ptr = &(p->right);
    } else {
      // val == p->key: Gefunden, p zeigt auf zu löschenden Knoten!
      break;
    }
    father = p;
  }

  // der komplizierte Fall:
  // der Knoten hat 2 Söhne
  // ersetze ihn durch seinen Nachfolger und lösche den Nachfolger
  if (p->left && p->right) {
    q = leftMost(p->right);  // Nachfolger q = Kleinster Knoten des rechten Teilbaumes
    p->key = q->key;         // Wert von q nach p hinaufkopieren
    // welcher Pointer zeigt auf q?
    ptr = (q == p->right) ? &(p->right) : &(q->up->left); 
    p = q;                   // q wird unser zu löschender Knoten p
    father = p->up;          // ... und father sein Vater
  }

  // der einfache Fall: p hat keinen oder einen Sohn
  // wenn er einen Sohn hat, hänge den Sohn q statt p an Stelle ptr an,
  // sonst ersetze p in ptr durch den leeren Teilbaum
  // den Sohn-Link in p müssen wir vor dem Destruktor auf NULL setzen,
  // sonst löscht delNode den ganzen Teilbaum, wenn er p freigibt!
  if (p->left) {
    q = p->left;
    q->up = father;
    p->left = NULL;
  } else if (p->right) {
    q = p->right;
    q->up = father;
    p->right = NULL;
  } else {
    q = NULL;
  }

  // Hänge q dort an, wo p hing:
  // An root (wenn p der Wurzelknoten ist)
  // oder an das left oder right des Vaters
  *ptr = q;
  
  delNode(p);
  return true;
}

// suche "val"
// Returnwert: true wenn gefunden, false wenn nicht vorhanden
bool Exists(const Node *root, int val)
{
  const Node *p = root;
  while (p) {
    if (val < p->key) {
      p = p->left;
    } else if (val > p->key) {
      p = p->right;
    } else {
      return true;
    }
  }
  return false;
}

// liefert das kleinste Element im Baum oder -1 bei leerem Baum
int getFirst(const Node *root)
{
  if (root == NULL) return -1;
  return leftMost(root)->key;    // der erste ist der ganz links
}

// liefert das nächste Element
// (das kleinste Element größer "val", egal, ob es "val" gibt oder nicht)
// oder -1, wenn es kein Element größer "val" mehr gibt

#ifdef REC_GETNEXT
int getNext(const Node *root, int val)
{
  if (root == NULL) {
    // Teilbaum leer
    // ==> kein nächster
    return -1;
  } else if (val < root->key) {
    // Wert liegt links vom Knoten
    // ==> Versuche, links einen Nachfolger zu finden
    // wenn es einen gibt, ist das der Nachfolger
    // wenn es keinen gibt, ist der aktuelle Knoten der Nachfolger
    int res = recGetNext(root->left, val);
    return (res == -1) ? root->key : res;
  } else {
    // Wert ist gleich dem Knoten oder rechts davon
    // ==> rechts Nachfolger suchen
    return recGetNext(root->right, val);
  }
}
#else
int getNext(const Node *root, int val)
{
  int res = -1; // der kleinste bisher gefundene Nachfolger
  const Node *p;

  p = root;
  while (p) {
    if (val < p->key) {
      // aktueller Knoten ist größer, daher möglicher Nachfolger
      // ==> merken und links weiter
      res = p->key;
      p = p->left;
    } else {
      // aktueller Knoten gleich oder kleiner val ==> rechts weiter
      p = p->right;
    }
  }

  return res;
}
#endif

// Rekursives Knotenzählen: Liefert die Knotenanzahl des Teilbaumes p
// p darf NULL sein
int recSize(const Node *p)
{
  if (p == NULL) return 0;
  return 1 + recSize(p->left) + recSize(p->right);
}

// Anzahl der Elemente im Baum
int getSize(const Node *root)
{
  return recSize(root);
}

// Ist der Baum leer?
bool isEmpty(const Node *root)
{
  return (root == NULL);
}

// Rekursive Statistik-Funktion:
// Addiert den Teilbaum p, beginnend auf Höhe h, zu den Statistiken:
// Anzahl der Elemente, Summe der Höhen, größte Höhe
// p darf NULL sein
void recStats(const Node *p, int h, int *elemCnt, int *sumH, int *maxH)
{
  if (p == NULL) return;

  ++(*elemCnt);
  *sumH += h;
  if (h > *maxH) *maxH = h;

  recStats(p->left, h + 1, elemCnt, sumH, maxH);
  recStats(p->right, h + 1, elemCnt, sumH, maxH);
}

// Ausgabe von Elementzahl, durchschnittlicher Höhe, maximaler Höhe
void printStats(const Node *root)
{
  int elemCnt = 0, sumH = 0, maxH = 0;
  double avgH;

  recStats(root, 1, &elemCnt, &sumH, &maxH);
  assert(elemCnt == getSize(root));

  avgH = (elemCnt == 0) ? 0.0 : ((double) sumH) / elemCnt;
  printf("Number of elements: %d\n", elemCnt);
  printf("Average height: %f\n", avgH);
  printf("Maximum height: %d\n", maxH);
}

// Rekursive Prüf-Funktion: Prüft den Teilbaum p auf Korrektheit
// (links < Wurzel < rechts und korrektes up)
// p darf *nicht* NULL sein
void recCheck(const Node *p)
{
  const Node *q;
  
  assert(p);  // sollte nie mit p==NULL aufgerufen werden
  if (p->left) {
    q = p->left;
    assert(q->key < p->key);
    assert(q->up == p);
    recCheck(q);
  }
  if (p->right) {
    q = p->right;
    assert(q->key > p->key);
    assert(q->up == p);
    recCheck(q);
  }
}

// Konsistenzprüfung des gesamten Baumes:
// * Haben alle Knoten die richtige Ordnung
//   (linker Sohn < Knoten < rechter Sohn)?
// * Stimmen alle up-Pointer?
// * Hat der Baum insgesamt n Knoten?
void checkTree(const Node *root, int n)
{
  int cnt;
  int oldval, val;

  if (root != NULL) {
    assert(root->up == NULL);
    recCheck(root);
  }

  // Prüfe getFirst, getNext und getSize:
  // Stimmt die Durchlauf-Reihenfolge 
  // und kommen beim Durchlaufen gleichviele Elemente heraus?
  for (cnt = 0, oldval = -1, val = getFirst(root);
       val >= 0;
       ++cnt, oldval = val, val = getNext(root, val)) {
    assert(oldval < val); // aufsteigend?
  }
  assert(cnt == getSize(root));
  assert(n == getSize(root));
}

int main(void)
{
  int i, j, n;
  int anz = 0;
  Node *t = NULL, *t1 = NULL;

  srand((unsigned int)(time(NULL)));

  for (i = 1; i <= NUM_TESTRUNS; ++i) {
    // teste Exists, Insert und Delete
    for (j = 1; j <= OPS_PER_RUN; ++j) {
      n = rand() % KEY_RANGE;
      if (Exists(t, n)) {
        assert(Delete(&t, n));
        --anz;
      } else {
        assert(Insert(&t, n));
        ++anz;
      }
    }
    // gib den Baum aus
    if (PRINT_TREE) {
      for (n = getFirst(t); n != -1; n = getNext(t, n)) {
        printf("%d ", n);
      }
      printf("\n");
    }
    // Statistiken und Baumprüfung
    printStats(t);
    checkTree(t, anz);
  }

  // teste Assignment und Delete bis leer
  // wir kopieren den Baum zuerst (testet auch das Kopieren), 
  // denn das Löschen darf sich nicht auf die Kopie auswirken!
  printf("***\n");
  t1 = copy(t);
  printStats(t1);
  checkTree(t1, anz);
  for (n = getFirst(t); n != -1; n = getNext(t, n)) {
    assert(Delete(&t,n));
  }
  printStats(t);
  checkTree(t, 0);
  printStats(t1);  // muss unverändert sein!
  checkTree(t1, anz);

  exit(EXIT_SUCCESS);
}