#include <iostream>

struct Node {
  int data;
  int height;
  Node* left;
  Node* right;
  Node* parent;
};

struct BinTree {
  Node* top = nullptr;

int height(Node* N) {
    if (N == nullptr)
      return 0;
    return N->height;
  }

  Node* newNode(int value) {
    Node* node = new Node();
    node->data = value;
    node->left = nullptr;
    node->right = nullptr;
    node->parent = nullptr;
    node->height = 1;
    return(node);
  }

  Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = std::max(height(y->left), height(y->right)) + 1;
    x->height = std::max(height(x->left), height(x->right)) + 1;
    return x;
  }

  Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = std::max(height(x->left), height(x->right)) + 1;
    y->height = std::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* MinValueNode(Node* node) {
   Node* current = node;
   
   while (current && current->left != NULL) {
       current = current->left;
   }
   return current;
}

 Node* Delete(Node* root, int value) {
    if (root == nullptr)
      return root;

    if (value < root->data)
      root->left = Delete(root->left, value);
    else if(value > root->data)
      root->right = Delete(root->right, value);
    else {
      if((root->left == nullptr) || (root->right == nullptr)) {
        Node* temp = root->left ? root->left : root->right;

        if(temp == nullptr) {
          temp = root;
          root = nullptr;
        } else
          *root = *temp;
        free(temp);
      } else {
        Node* temp = MinValueNode(root->right);
        root->data = temp->data;
        root->right = Delete(root->right, temp->data);
      }
    }

    if (root == nullptr)
      return root;

    root->height = 1 + std::max(height(root->left), height(root->right));
    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0)
      return rightRotate(root);

    if (balance > 1 && getBalance(root->left) < 0) {
      root->left = leftRotate(root->left);
      return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0)
      return leftRotate(root);

    if (balance < -1 && getBalance(root->right) > 0) {
      root->right = rightRotate(root->right);
      return leftRotate(root);
    }

    return root;
  }

  Node* Insert(Node* node, int value) {
    if (node == nullptr)
      return(newNode(value));

    if (value < node->data)
      node->left = Insert(node->left, value);
    else if (value > node->data)
      node->right = Insert(node->right, value);
    else
      return node;

    node->height = 1 + std::max(height(node->left), height(node->right));
    int balance = getBalance(node);

    if (balance > 1 && value < node->left->data)
      return rightRotate(node);

    if (balance < -1 && value > node->right->data)
      return leftRotate(node);

    if (balance > 1 && value > node->left->data) {
      node->left = leftRotate(node->left);
      return rightRotate(node);
    }

    if (balance < -1 && value < node->right->data) {
      node->right = rightRotate(node->right);
      return leftRotate(node);
    }

    return node;
  }

  void Exists(int value) {
    Node* current = top;

    while (current != nullptr) {
      if (value < current->data) {
        current = current->left;
      } else if (value > current->data) {
        current = current->right;
      } else {
        std::cout << "true" << '\n';
        return;
      }
    }
    std::cout << "false" << '\n';
  }

void prev(Node* current, int value) {
  Node* ans_root = nullptr;
  
  while (current != nullptr) {
    if (value > current->data) {
      ans_root = current;
      current = current->right;
    } else {
      current = current->left;
    }
  }

 if (ans_root != nullptr) {
  std::cout << ans_root->data << '\n';
 } else {
  std::cout << "none" << '\n';
 }
}

void next(Node* current, int value) {
  Node* ans_root = nullptr;
  
  while (current != nullptr) {
    if (value < current->data) {
      ans_root = current;
      current = current->left;
    } else {
      current = current->right;
    }
  }
  if (ans_root != nullptr) {
  std::cout << ans_root->data << '\n';
 } else {
  std::cout << "none" << '\n';
 }
}
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  std::string cmd;
  BinTree tree;
  while (std::cin >> cmd) {
    if (cmd == "insert") {
      int x;
      std::cin >> x;
      tree.top = tree.Insert(tree.top, x);
    } else if (cmd == "delete") {
      int x;
      std::cin >> x;
      tree.top = tree.Delete(tree.top, x);
    } else if (cmd == "exists") {
      int x;
      std::cin >> x;
      tree.Exists(x);
    } else if (cmd == "next") {
      int x;
      std::cin >> x;
      tree.next(tree.top, x);
    } else if (cmd == "prev") {
      int x;
      std::cin >> x;
      tree.prev(tree.top, x);
    }
  }

}



используй этот код для решения задачи ниже

Для балансировки АВЛ-дерева при операциях вставки и удаления производятся левые и правые повороты. Левый поворот в вершине производится, когда баланс этой вершины больше 1, аналогично, правый поворот производится при балансе, меньшем 1.

Существует два разных левых (как, разумеется, и правых) поворота: большой и малый левый поворот.

Малый левый поворот осуществляется следующим образом:

{скоро тут будет иллюстрация}

Заметим, что если до выполнения малого левого поворота был нарушен баланс только корня дерева, то после его выполнения все вершины становятся сбалансированными, за исключением случая, когда у правого ребенка корня баланс до поворота равен 1. В этом случае вместо малого левого поворота выполняется большой левый поворот, который осуществляется так:

{скоро тут будет иллюстрация}

Дано дерево, в котором баланс дерева равен 2. Сделайте левый поворот.

Входные данные

Входные данные содержат описание двоичного дерева.

В первой строке файла находится число 
�
n (
1
≤
�
≤
2
⋅
1
0
5
1≤n≤2⋅10 
5
 ) - число вершин в дереве. В последующих 
�
n строках файла находятся описания вершин дерева. В (
�
+
1
i+1)-ой строке айла (
1
≤
�
≤
�
1≤i≤n) находится описание 
�
i-ой вершины, состоящее из трех чисел 
�
�
K 
i
​
 , 
�
�
L 
i
​
 , 
�
�
R 
i
​
 , разделенных пробелами ключа в 
�
i-ой вершине (
∣
�
�
∣
<
=
1
0
9
∣Ki∣<=10 
9
 ), номера левого ребенка 
�
i-ой вершины (
�
<
�
�
≤
�
i<L 
i
​
 ≤n или 
�
�
=
0
L 
i
​
 =0, если левого ребенка нет) и номера правого ребенка 
�
i-ой вершины (
�
<
�
�
≤
�
i<R 
i
​
 ≤n или 
�
�
=
0
R 
i
​
 =0, если правого ребенка нет).

Все ключи различны. Гарантируется, что данное дерево является деревом поиска. Все ключи различны. Баланс корня дерева (вершины с номером 1) равен 2, баланс всех остальных вершин находится в пределах от -1 до 1.