---

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

int height(Node* n) { return n ? n->height : 0; }
int bfactor(Node* n) { return n ? height(n->left) - height(n->right) : 0; }
void fixHeight(Node* n) {
    if (n) n->height = 1 + max(height(n->left), height(n->right));
}

Node* rotateRight(Node* p) {
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* rotateLeft(Node* p) {
    Node* q = p->right;
    p->right = q->left;
    q->left = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* balance(Node* p) {
    fixHeight(p);
    if (bfactor(p) == 2) {
        if (bfactor(p->left) < 0) p->left = rotateLeft(p->left);
        return rotateRight(p);
    }
    if (bfactor(p) == -2) {
        if (bfactor(p->right) > 0) p->right = rotateRight(p->right);
        return rotateLeft(p);
    }
    return p;
}

Node* insert(Node* p, int key) {
    if (!p) return new Node(key);
    if (key < p->key) p->left = insert(p->left, key);
    else if (key > p->key) p->right = insert(p->right, key);
    else return p;
    return balance(p);
}

// Полное удаление поддерева с корнем p
void deleteSubtree(Node* p) {
    if (!p) return;
    deleteSubtree(p->left);
    deleteSubtree(p->right);
    delete p;
}

// Удаление ветви (вершина с ключом key и всё её поддерево)
Node* deleteBranch(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) {
        root->left = deleteBranch(root->left, key);
        return balance(root);
    } else if (key > root->key) {
        root->right = deleteBranch(root->right, key);
        return balance(root);
    } else {
        // Нашли узел для удаления
        deleteSubtree(root);
        return nullptr;
    }
}

void inorder(Node* p) {
    if (!p) return;
    inorder(p->left);
    cout << p->key << " ";
    inorder(p->right);
}

int main() {
    srand(time(0));
    Node* root = nullptr;

    // Создаём дерево ровно из 10 случайных чисел в диапазоне [-50, 50]
    cout << "Создание дерева из 10 случайных чисел:\n";
    for (int i = 0; i < 10; i++) {
        int val = rand() % 101 - 50;
        root = insert(root, val);
    }

    cout << "Дерево (возрастание): ";
    inorder(root);
    cout << endl;

    int key;
    cout << "Введите ключ вершины, ветвь с которой нужно удалить: ";
    cin >> key;

    root = deleteBranch(root, key);

    cout << "Дерево после удаления ветви с ключом " << key << " : ";
    if (root == nullptr)
        cout << "(дерево пусто)";
    else
        inorder(root);
    cout << endl;

    // Освобождение памяти (на случай, если root не пуст)
    if (root) deleteSubtree(root);
    return 0;
}