BinarySearchTrees

#include <cassert>
#include <iostream>
#include <limits.h>
#include <queue>

struct Node {
  int Key;
  Node* Left;
  Node* Right;
  Node* Parent;

  Node(int key, Node* parent) : Key(key), Left(nullptr), Right(nullptr), Parent(parent) {}
};

void Add(int key, Node* node) {
  assert(node);
  if (node->Key < key) {
    if (node->Right)
      Add(key, node->Right);
    else
      node->Right = new Node(key, node);
  } else {
    if (node->Left)
      Add(key, node->Left);
    else
      node->Left = new Node(key, node);
  }
}

// insert <-> delete
// add <-> remove

Node* Remove(int key, Node*& root) {

  delete root;
  return nullptr;
}

void DeleteTree(Node* root) {
  if (root != nullptr) {
    DeleteTree(root->Left);
    DeleteTree(root->Right);
    delete root;
  }
}

int main1() {
//  Node* root = new Node(5, nullptr);
//  Add(7, root);
  // Удаление. Вариант 1. Фиктивный корень.
  Node* unreal_root = new Node(INT_MAX, nullptr);
  // Node* root = new Node(5, unreal_root);
  Add(5, unreal_root);
  Remove(7, unreal_root);
  // Удаление. Вариант 2. Возвращать из Remove новый корень.

  std::cout << unreal_root->Key << " " << unreal_root->Right->Key << std::endl;
  DeleteTree(unreal_root);
  return 0;
}

int height(Node* root) {
  if (root == nullptr) return 0;
  int l = height(root->Left);
  int r = height(root->Right);
  return std::max(l, r) + 1;
}

int main2() {
  Node* fake_root = new Node(INT_MAX, nullptr);
  Add(5, fake_root);
  Add(7, fake_root);
  std::cout << height(fake_root->Left) << std::endl;
  return 0;
}

class Tree {
 public:
  Tree() : root(nullptr) { std::cout << "Constructor called" << std::endl; }
  ~Tree() { Destruct(root); std::cout << "Destructor called" << std::endl; }

  void Add(int key);
  void BFS();
  void Print() { if(root) DFS(root, 0); }

 private:
  Node* root;  // = nullptr, если дерево пустое

  void Destruct(Node* node) {
    if (node != nullptr) {
      Destruct(node->Left);
      Destruct(node->Right);
      delete node;
    }
  }
  void DFS(Node* node, int margin) {
    if (node->Right) DFS(node->Right, margin + 4);
    for (int i = 0; i < margin - 4; ++i) std::cout << " ";
    if (margin > 3) for (int i = 0; i < 4; ++i) std::cout << "-";
    std::cout << "(" << node->Key << ")" << std::endl;
    if (node->Left) DFS(node->Left, margin + 4);
  }
};

void Tree::Add(int key) {
  if (root == nullptr) {
    root = new Node(key, nullptr);
  } else {
    ::Add(key, root);
  }
}

void Tree::BFS() {
  std::queue<Node*> q;
  if (root) q.push(root);
  while (!q.empty()) {
    Node* current = q.front(); q.pop();
    std::cout << current->Key << " ";
    if (current->Left) q.push(current->Left);
    if (current->Right) q.push(current->Right);
  }
  std::cout << std::endl;
}

int main3() {
  {
    Tree tree;
    tree.Add(5);
    tree.Add(9);
    tree.Add(3);
    tree.Add(1);
    tree.Add(2);
    tree.Add(7);
    tree.Add(6);
    tree.Add(8);
    tree.Add(10);
    tree.BFS();
    tree.Print();
  }
  std::cout << "Before return" << std::endl;
  return 0;
}

struct TreapNode {
  int Key;
  int Priority;
  TreapNode* Left;
  TreapNode* Right;

  TreapNode(int key, int priority) : Key(key), Priority(priority), Left(nullptr), Right(nullptr) {}
};

std::pair<TreapNode*, TreapNode*> Split(TreapNode* node, int key) {
  if (node == nullptr) return {nullptr, nullptr};
  if (key < node->Key) {
    std::pair<TreapNode*, TreapNode*> p = Split(node->Left, key);
    node->Left = p.second;
    return {p.first, node};
  } else {
    auto [first, second] = Split(node->Right, key);
    node->Right = first;
    return {node, second};
  }
}

TreapNode* Merge(TreapNode* left, TreapNode* right) {
  if (left == nullptr || right == nullptr) {
    return left == nullptr ? right : left;
  }
  if (left->Priority > right->Priority) {
    left->Right = Merge(left->Right, right);
    return left;
  } else {
    right->Left = Merge(left, right->Left);
    return right;
  }
}

TreapNode* Add(TreapNode* root, int key) {
  TreapNode* new_node = new TreapNode(key, rand());
  auto [first, second] = Split(root, key);
  return Merge(Merge(first, new_node), second);
}

void DFS(TreapNode* node, int margin) {
  if (node->Right) DFS(node->Right, margin + 4);
  for (int i = 0; i < margin - 4; ++i) std::cout << " ";
  if (margin > 3) for (int i = 0; i < 4; ++i) std::cout << "-";
  std::cout << "(" << node->Key << ")" << std::endl;
  if (node->Left) DFS(node->Left, margin + 4);
}

int main() {
  srand(2021);

  TreapNode* root = nullptr;
  root = Add(root, 5);
  root = Add(root, 7);
  root = Add(root, 92);
  root = Add(root, 198);
  DFS(root, 0);
  return 0;
}