#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <set>
#include <vector>

using namespace std;

struct Node {
  int key;
  Node *left, *right;
  int height;
};

int height(Node *n) {
  // απλός getter, αν το πεδίο height είναι ενημερωμένο σωστά
  if (n == nullptr) return 0;
  return n->height;
}

// Δημιουργεί έναν νέο κόμβο, χωρίς να τον τοποθετήσει στο δέντρο
Node *newNode(int newkey) {
  Node *newNode = new Node;
  newNode->key = newkey;
  newNode->left = newNode->right = nullptr;
  newNode->height = 1;
  return (newNode);
}

Node *rightRotate(Node *y) { // Δεξιά περιστροφή
  Node *x = y->left;
  Node *tmpNode = x->right;
  x->right = y; // περιστροφή: x είναι η νέα ρίζα
  y->left = tmpNode;
  y->height = max(height(y->left), height(y->right)) + 1; // ενημέρωση υψών
  x->height = max(height(x->left), height(x->right)) + 1;
  return x;
}

Node *leftRotate(Node *x) { // Αριστερή περιστροφή
  Node *y = x->right;
  Node *tmpNode = y->left;
  y->left = x;
  x->right = tmpNode;
  x->height = max(height(x->left), height(x->right)) + 1; // ενημέρωση υψών
  y->height = max(height(y->left), height(y->right)) + 1;
  return y;
}

int getBalance(Node *n) {
  if (n == nullptr) return 0;
  return height(n->left) - height(n->right);
}

Node *rebalanceNode(Node *n) {
  // 2. ενημέρωση υψών
  n->height = 1 + max(height(n->left), height(n->right));

  // 3. έλεγχος ισορροπίας
  int balance = getBalance(n);
  if (balance > 1) {
    if (getBalance(n->left) >= 0)
      return rightRotate(n);
    n->left = leftRotate(n->left);
    return rightRotate(n);
  } else if (balance < -1) {
    if (getBalance(n->right) <= 0)
      return leftRotate(n);
    n->right = rightRotate(n->right);
    return leftRotate(n);
  }
  return n;
}

Node *insertNode(Node *n, int key) {
  // 1. εισαγωγή στο BST χωρίς ζύγισμα
  if (n == nullptr)
    return newNode(key);
  if (key < n->key)
    n->left = insertNode(n->left, key);
  else if (key > n->key)
    n->right = insertNode(n->right, key);
  else // Δεν επιτρέπονται διπλά κλειδιά
    return n;

  return rebalanceNode(n);
}

Node *minValueNode(Node *n) {
  while (n->left != nullptr)
    n = n->left;
  return n;
}

Node *deleteNode(Node *n, int key) {
  // 1. διαγραφή από το BST χωρίς ζύγισμα
  if (n == nullptr)
    return n;
  if (key < n->key)
    n->left = deleteNode(n->left, key);
  else if (key > n->key)
    n->right = deleteNode(n->right, key);
  else {
    // this is the node to delete
    Node *temp = n;
    if (n->left == nullptr && n->right == nullptr) {
      n = nullptr; // it's a leaf, just delete it!
      delete temp;
    } else if (n->left == nullptr) {
      n = n->right; // it has one right child, replace it with that!
      delete temp;
    } else if (n->right == nullptr) {
      n = n->left; // it has one left child, replace it with that!
      delete temp;
    } else {
      // the node has two children, find its inorder successor
      temp = minValueNode(n->right);
      // copy the inorder successor's content to this node
      n->key = temp->key;
      // delete the inorder successor
      n->right = deleteNode(n->right, temp->key);
    }
  }

  // Αν το δένδρο άδειασε, τελειώσαμε.
  if (n == nullptr)
    return n;

  return rebalanceNode(n);
}

void printPreorder(Node *node) {
  if (node == nullptr) return;
  cout << node->key << "(" << node->height << ") ";
  printPreorder(node->left);
  printPreorder(node->right);
}

void verify(bool p, const char *msg = "assertion failure") {
  if (!p) throw msg;
}

int checkAVL(Node *n, int lower = numeric_limits<int>::min(),
             int upper = numeric_limits<int>::max()) {
  if (n == nullptr) return 0;
  verify(lower <= n->key, "key lower than expected");
  verify(n->key <= upper, "key higher than expected");
  verify(abs(getBalance(n)) <= 1, "wrong balance");
  int l = checkAVL(n->left, lower, n->key - 1);
  int r = checkAVL(n->right, n->key + 1, upper);
  return 1 + l + r;
}

bool grow(int size, int target_size) {
  int k = rand() % (2 * target_size);
  return size < k;
}

int test() {
  Node *t = nullptr;
  int size = 0;
  constexpr int iterations = 1000000;
  constexpr int target_size = 100000;
  set<int> s;
  vector<pair<char, int>> commands;
  for (int i = 0; i < iterations; ++i) {
    cerr << "\r" << i;
    if (t == nullptr || grow(size, target_size)) {
      int k = rand() % iterations;
      commands.emplace_back('a', k);
      t = insertNode(t, k);
      if (s.find(k) == s.end()) {
        s.insert(k);
        ++size;
      }
    } else {
      int k = rand() % iterations;
      commands.emplace_back('d', k);
      t = deleteNode(t, k);
      if (s.find(k) != s.end()) {
        s.erase(k);
        --size;
      }
    }
    try {
      verify(checkAVL(t) == size, "wrong size");
    } catch (const char *msg) {
      cerr << " iteration failed, " << msg << endl;
      cout << "Result: ";
      printPreorder(t);
      cout << endl;
      return 1;
    }
  }
  cerr << " iterations were successful." << endl;
  return 0;
}

int main() {
  Node *t = nullptr;
  cout << "Start with empty tree" << endl;
  vector<pair<char, int>> commands = {{'a', 5}, {'a', 6}, {'a', 7}, {'a', 8},
                                      {'d', 5}, {'a', 3}, {'a', 4}, {'d', 8}};
  try {
    // The following syntax of "for" requires C++17 (-std=c++17) or later.
    for (auto [cmd, k] : commands) {
      switch (cmd) {
      case 'a':
        cout << endl << "Insert " << k << endl;
        t = insertNode(t, k);
        cout << "Result: ";
        printPreorder(t);
        cout << endl;
        checkAVL(t);
        break;
      case 'd':
        cout << endl << "Delete " << k << endl;
        t = deleteNode(t, k);
        cout << "Result: ";
        printPreorder(t);
        cout << endl;
        checkAVL(t);
        break;
      }
    }
  } catch (const char *msg) {
    cout << "Fail: " << msg << endl;
    return 1;
  }

  return test();
}