// 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 <iostream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

// die einzelnen Baumknoten: Wert + 3 Pointer
class Node
{
  // alles privat, Zugriff nur für die Friend Class möglich!
  friend class BinTree;
  
  private:
    // Konstruktor (Söhne leer)
    Node(int val, Node *father)
      : key(val), left(nullptr), right(nullptr), up(father) {}
    ~Node();  // Code siehe unten!

    // Copy Constructor und Assignment operator sollen nicht verwendet werden
    // (es ist sinnlos, einen einzelnen Knoten zu kopieren)
    // ==> als "privat" deklarieren und *nicht* definieren!
    Node(const Node &node);  
    Node &operator=(const Node &node);  

    int key;
    Node *left, *right, *up;
};

// Destruktor: Rekursiv die Unterbäume löschen, damit sie nicht überbleiben!
// Aber erkennen, wenn jemand vergessen hat,
// bei einem einzelnen ausgehängten Knoten die Unterbäume auf nullptr zu setzen!
Node::~Node()
{
  if (left) {
    assert(left->up == this);
    delete left;
  }
  if (right) {
    assert(right->up == this);
    delete right;
  }
}

// unser Baum
class BinTree
{
  public:
    // Konstruktor: Erzeugt einen leeren Bauim
    BinTree() : root(nullptr) {}
    // expliziter Copy Construktor: Ganzen Baum rekursiv kopieren!
    BinTree(const BinTree &tree)
      : root(recCopy(tree.root, nullptr)) {}
    // im Destruktor: Auch alle Knoten des Baumes freigeben
    // (rekursiv über ~Node() beim Löschen der Wurzel)
    ~BinTree() { if (root) delete root; }

    // expliziter Assignment operator: Ganzen Baum rekursiv kopieren!
    BinTree &operator=(const BinTree &tree);

    // füge "val" ein
    // Returnwert: true wenn ok, false wenn schon vorhanden
    bool Insert(int val);
    // lösche "val"
    // Returnwert: true wenn ok, false wenn nicht vorhanden
    bool Delete(int val);
    // suche "val"
    // Returnwert: true wenn gefunden, false wenn nicht vorhanden
    bool Exists(int val) const;

    // liefert das kleinste Element im Baum oder -1 bei leerem Baum
    int getFirst() const;
    // 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
    int getNext(int val) const;

    // Anzahl der Elemente im Baum
    int getSize() const { return recSize(root); }
    // Ist der Baum leer?
    bool isEmpty() const { return (root == nullptr); }
    // Ausgabe von Elementzahl, durchschnittlicher Höhe, maximaler Höhe
    void printStats() const;
    // 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(int n) const;
    
  private:

    // Hilfsfunktionen:
    // 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 nullptr sein ==> Ergebnis auch nullptr
    Node *recCopy(const Node *p, Node *up) const;
    // Baum links absteigen: Liefert den linkesten (kleinsten) Knoten des Teilbaumes p
    // p darf nicht nullptr sein, und es kommt auch nie nullptr zurück
    Node *leftMost(const Node *p) const;
    // Rekursives Knotenzählen: Liefert die Knotenanzahl des Teilbaumes p
    // p darf nullptr sein
    int recSize(const Node *p) const;
    // 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 nullptr sein
    void recStats(const Node *p, int h, int &elemCnt, int &sumH, int &maxH) const;
    // Rekursive Prüf-Funktion: Prüft den Teilbaum p auf Korrektheit
    // (links < Wurzel < rechts und korrektes up)
    // p darf *nicht* nullptr sein
    void recCheck(const Node *p) const;

#ifdef REC_GETNEXT
    // Hilfsfunktion für rekursives getNext:
    // liefert den kleinsten Knoten größer val im Teilbaum p oder -1
    int recGetNext(int val, const Node *p) const;
#endif
    
    Node *root;  // Wurzel des Baumes
};

Node *BinTree::recCopy(const Node *p, Node *up) const
{
  Node *newP;
  
  if (p == nullptr) return nullptr;
  
  newP = new Node(p->key, up);
  newP->left = recCopy(p->left, newP);
  newP->right = recCopy(p->right, newP);
  return newP;
}

Node *BinTree::leftMost(const Node *p) const
{
  assert(p);  // sollte nie mit p==nullptr aufgerufen werden
  while (p->left) p = p->left;
  return const_cast<Node *>(p); // const weg-casten
}

int BinTree::recSize(const Node *p) const
{
  if (p == nullptr) return 0;
  return 1 + recSize(p->left) + recSize(p->right);
}

void BinTree::recStats(const Node *p, int h,
                       int &elemCnt, int &sumH, int &maxH) const
{
  if (p == nullptr) 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);
}

void BinTree::recCheck(const Node *p) const
{
  const Node *q;
  
  assert(p);  // sollte nie mit p==nullptr 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);
  }
}

BinTree &BinTree::operator=(const BinTree &tree)
{
  if (this == &tree) return *this; // Schutz vor Selbstzuweisung
  
  if (root) delete root;  // zuerst alten Baum sauber löschen!
  root = recCopy(tree.root, nullptr);
  return *this;
}

bool BinTree::Insert(int val)
{
  // **-Trick:
  // ptr zeigt auf den Pointer, an dem der aktuelle Knoten hängt
  // bzw. am Ende auf den nullptr-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 = nullptr;    

  assert(val >= 0);

  for (;;) {
    p = *ptr;
    if (p == nullptr) {
      // nicht gefunden: Neuen Knoten an *ptr anhängen
      *ptr = new Node(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;
  }
}

bool BinTree::Delete(int val)
{
  // **-Trick:
  // ptr zeigt auf den Pointer, an dem der aktuelle Knoten hängt
  // bzw. am Ende auf den nullptr-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 = nullptr;
  // Wenn p gelöscht wird: Sohn bzw. Nachfolger von p
  Node *q;  

  assert(val >= 0);

  for (;;) {
    p = *ptr;
    if (p == nullptr) {
      // 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 nullptr setzen,
  // sonst löscht der Destruktor den ganzen Teilbaum, wenn er p freigibt!
  if (p->left) {
    q = p->left;
    q->up = father;
    p->left = nullptr;
  } else if (p->right) {
    q = p->right;
    q->up = father;
    p->right = nullptr;
  } else {
    q = nullptr;
  }

  // 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;
  
  delete p;  
  return true;
}

bool BinTree::Exists(int val) const
{
  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;
}

int BinTree::getFirst() const
{
  if (root == nullptr) return -1;
  return leftMost(root)->key;    // der erste ist der ganz links
}

#ifdef REC_GETNEXT
int BinTree::recGetNext(int val, const Node *p) const {
  if (p == nullptr) {
    // Teilbaum leer
    // ==> kein nächster
    return -1;
  } else if (val < p->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(val, p->left);
    return (res == -1) ? p->key : res;
  } else {
    // Wert ist gleich dem Knoten oder rechts davon
    // ==> rechts Nachfolger suchen
    return recGetNext(val, p->right);
  }
}
int BinTree::getNext(int val) const
{
  return recGetNext(val, root); 
}
#else
int BinTree::getNext(int val) const
{
  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

void BinTree::printStats() const
{
  int elemCnt = 0, sumH = 0, maxH = 0;
  double avgH;

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

  avgH = (elemCnt == 0) ? 0.0 : double(sumH) / elemCnt;
  cout << "Number of elements: " << elemCnt << endl;
  cout << "Average height: " << avgH << endl;
  cout << "Maximum height: " << maxH << endl;
}

void BinTree::checkTree(int n) const
{
  int cnt;
  int oldval, val;

  if (root != nullptr) {
    assert(root->up == nullptr);
    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();
       val >= 0;
       ++cnt, oldval = val, val = getNext(val)) {
    assert(oldval < val); // aufsteigend?
  }
  assert(cnt == getSize());
  assert(n == getSize());
}

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

  srand(static_cast<unsigned int>(time(nullptr)));

  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 (t.Exists(n)) {
        assert(t.Delete(n));
        --anz;
      } else {
        assert(t.Insert(n));
        ++anz;
      }
    }
    // gib den Baum aus
    if (PRINT_TREE) {
      for (n = t.getFirst(); n != -1; n = t.getNext(n)) {
        cout << n << ' ';
      }
      cout << endl;
    }
    // Statistiken und Baumprüfung
    t.printStats();
    t.checkTree(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!
  cout << "***" << endl;
  t1 = t;
  t1.printStats();
  t1.checkTree(anz);
  for (n = t.getFirst(); n != -1; n = t.getNext(n)) {
    assert(t.Delete(n));
  }
  t.printStats();
  t.checkTree(0);
  t1.printStats();  // muss unverändert sein!
  t1.checkTree(anz);

  exit(EXIT_SUCCESS);
}