---

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>

using namespace std;

// Структура узла бинарного дерева поиска
struct ttree {
    int inf;            // ключ (информация)
    ttree *left;        // указатель на левое поддерево
    ttree *right;       // указатель на правое подерево
};

// Функция создания нового узла
ttree* createNode(int inf) {
    ttree *nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->right = NULL;
    return nl;
}

// Добавление элемента в бинарное дерево поиска (без балансировки)
ttree* addtree(ttree *proot, int inf) {
    ttree *nl = createNode(inf);
    if (proot == NULL) return nl;

    ttree *ps = proot;
    ttree *pr = NULL;
    bool b = false; // направление: true - влево, false - вправо

    while (ps != NULL) {
        pr = ps;
        if (inf < ps->inf) {
            b = true;
            ps = ps->left;
        } else {
            b = false;
            ps = ps->right;
        }
    }
    if (b)
        pr->left = nl;
    else
        pr->right = nl;
    return proot;
}

// Симметричный обход (в порядке возрастания ключей)
void inorder(ttree *p) {
    if (p == NULL) return;
    inorder(p->left);
    cout << p->inf << " ";
    inorder(p->right);
}

// Прямой обход (корень -> левое -> правое)
void preorder(ttree *p) {
    if (p == NULL) return;
    cout << p->inf << " ";
    preorder(p->left);
    preorder(p->right);
}

// Обратный обход (левое -> правое -> корень)
void postorder(ttree *p) {
    if (p == NULL) return;
    postorder(p->left);
    postorder(p->right);
    cout << p->inf << " ";
}

// Поиск элемента с заданным ключом (возвращает true и значение, если найден)
bool search(ttree *p, int key, int &found) {
    if (p == NULL) return false;
    if (p->inf == key) {
        found = p->inf;
        return true;
    }
    if (key < p->inf)
        return search(p->left, key, found);
    else
        return search(p->right, key, found);
}

// Удаление всего дерева (освобождение памяти)
ttree* deltree(ttree *p) {
    if (p == NULL) return NULL;
    deltree(p->left);
    deltree(p->right);
    delete p;
    return NULL;
}

// Поиск узла с минимальным ключом
ttree* findMin(ttree *p) {
    if (p == NULL) return NULL;
    while (p->left != NULL)
        p = p->left;
    return p;
}

// Поиск узла с максимальным ключом
ttree* findMax(ttree *p) {
    if (p == NULL) return NULL;
    while (p->right != NULL)
        p = p->right;
    return p;
}

// Удаление узла с заданным ключом (реализация из методички)
ttree* dellist(ttree *proot, int inf) {
    ttree *ps = proot, *pr = proot, *w, *v;

    // Поиск удаляемого узла
    while ((ps != NULL) && (ps->inf != inf)) {
        pr = ps;
        if (inf < ps->inf)
            ps = ps->left;
        else
            ps = ps->right;
    }

    if (ps == NULL) return proot;   // узел не найден

    // Случай 1: узел не имеет дочерних узлов (лист)
    if ((ps->left == NULL) && (ps->right == NULL)) {
        if (ps == pr) { // удаляется корень (и он единственный)
            delete ps;
            return NULL;
        }
        if (pr->left == ps)
            pr->left = NULL;
        else
            pr->right = NULL;
        delete ps;
        return proot;
    }

    // Случай 2: только правый потомок
    if (ps->left == NULL) {
        if (ps == pr) { // удаляется корень
            ps = ps->right;
            delete pr;
            return ps;
        }
        if (pr->left == ps)
            pr->left = ps->right;
        else
            pr->right = ps->right;
        delete ps;
        return proot;
    }

    // Случай 3: только левый потомок
    if (ps->right == NULL) {
        if (ps == pr) { // удаляется корень
            ps = ps->left;
            delete pr;
            return ps;
        }
        if (pr->left == ps)
            pr->left = ps->left;
        else
            pr->right = ps->left;
        delete ps;
        return proot;
    }

    // Случай 4: два потомка
    w = ps->left;
    if (w->right == NULL) {  // максимальный следует за ps
        w->right = ps->right;
    } else {
        while (w->right != NULL) {
            v = w;
            w = w->right;
        }
        v->right = w->left;
        w->left = ps->left;
        w->right = ps->right;
    }
    if (ps == pr) { // удаляется корень
        delete ps;
        return w;
    }
    if (pr->left == ps)
        pr->left = w;
    else
        pr->right = w;
    delete ps;
    return proot;
}

// Построение сбалансированного дерева из отсортированного вектора
ttree* buildBalanced(vector<int> &arr, int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    ttree *node = createNode(arr[mid]);
    node->left = buildBalanced(arr, start, mid - 1);
    node->right = buildBalanced(arr, mid + 1, end);
    return node;
}

// Функция для обмена максимального и минимального ключей в дереве
void swapMinMax(ttree *root) {
    if (root == NULL) return;
    ttree *minNode = findMin(root);
    ttree *maxNode = findMax(root);
    if (minNode != NULL && maxNode != NULL && minNode != maxNode) {
        int temp = minNode->inf;
        minNode->inf = maxNode->inf;
        maxNode->inf = temp;
    }
}

int main() {
    srand(time(0));

    // Генерация 15 случайных уникальных чисел в диапазоне [-50, 50]
    const int N = 15;
    vector<int> numbers;
    while (numbers.size() < N) {
        int r = rand() % 101 - 50;   // от -50 до 50
        // чтобы избежать повторов (для простоты)
        if (find(numbers.begin(), numbers.end(), r) == numbers.end())
            numbers.push_back(r);
    }

    // Сортируем числа для построения сбалансированного дерева
    sort(numbers.begin(), numbers.end());

    // Строим сбалансированное дерево
    ttree *root = buildBalanced(numbers, 0, numbers.size() - 1);

    cout << "=== Сбалансированное дерево поиска ===\n";
    cout << "Исходные числа (отсортированы): ";
    for (int x : numbers) cout << x << " ";
    cout << "\n\n";

    cout << "Обход в порядке возрастания (симметричный): ";
    inorder(root);
    cout << "\n";

    cout << "Прямой обход (корень-лево-право): ";
    preorder(root);
    cout << "\n";

    cout << "Обратный обход (лево-право-корень): ";
    postorder(root);
    cout << "\n";

    // Поиск значения (пример)
    int searchKey = numbers[N/2]; // выберем средний элемент
    int foundVal;
    if (search(root, searchKey, foundVal))
        cout << "\nПоиск: значение " << searchKey << " найдено.\n";
    else
        cout << "\nПоиск: значение " << searchKey << " не найдено.\n";

    // Выполняем индивидуальное задание: поменять местами минимальный и максимальный ключи
    cout << "\n=== Индивидуальное задание (вариант 1) ===\n";
    cout << "Меняем местами минимальный и максимальный ключи.\n";
    swapMinMax(root);

    cout << "Дерево после обмена (обход в порядке возрастания): ";
    inorder(root);
    cout << "\n";

    // Демонстрация удаления элемента (например, удалим число, которое было максимальным)
    // Но после обмена максимальным стало бывшее минимальное. Удалим его.
    // Найдём новый минимальный и максимальный для информации
    ttree *newMin = findMin(root);
    ttree *newMax = findMax(root);
    if (newMin && newMax) {
        cout << "Новый минимальный ключ: " << newMin->inf << endl;
        cout << "Новый максимальный ключ: " << newMax->inf << endl;
    }

    // Покажем работу удаления: удалим корень (для примера)
    int valToDelete = root->inf;
    cout << "\nУдаляем корень со значением " << valToDelete << " ...\n";
    root = dellist(root, valToDelete);
    cout << "Обход после удаления: ";
    inorder(root);
    cout << "\n";

    // Освобождение памяти
    root = deltree(root);
    cout << "\nПамять полностью освобождена.\n";

    return 0;
}