---

#include <iostream>
#include <ctime>
#include <random>
using namespace std;

struct ttree {
    int inf;
    ttree *left;
    ttree *right;
};

ttree *addtree(ttree *proot, int inf) {
    ttree *nl, *pr, *ps;
    bool b;
    nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->right = NULL;
    if (proot == NULL) return nl;
    ps = proot;
    while (ps != NULL) {
        pr = ps;
        b = (inf < ps->inf);
        if (b) ps = ps->left;
        else ps = ps->right;
    }
    if (b) pr->left = nl;
    else pr->right = nl;
    return proot;
}

void wrtree(ttree *p) {
    if (p == NULL) return;
    wrtree(p->left);
    cout << p->inf << " ";
    wrtree(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 << " ";
}

void poisktree(ttree *p, int key, bool &b, int &inf) {
    if ((p != NULL) && (b != true)) {
        if (p->inf != key) {
            poisktree(p->left, key, b, inf);
            poisktree(p->right, key, b, inf);
        } else {
            b = true;
            inf = p->inf;
        }
    }
}

int poiskmaxtree(ttree *p) {
    while (p->right != NULL) p = p->right;
    return p->inf;
}

ttree *poiskmaxtreeNode(ttree *p) {
    if (p == NULL) return NULL;
    while (p->right != NULL) p = p->right;
    return p;
}

ttree *poiskmintreeNode(ttree *p) {
    if (p == NULL) return NULL;
    while (p->left != NULL) p = p->left;
    return p;
}

ttree *deltree(ttree *p) {
    if (p == NULL) return NULL;
    deltree(p->left);
    deltree(p->right);
    delete p;
    return NULL;
}

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;
    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;
    }
    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;
    }
    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;
    }
    w = ps->left;
    if (w->right == NULL) {
        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 *build_balanced(int arr[], int start, int end) {
    if (start > end) return NULL;
    int mid = start + (end - start) / 2;
    ttree *root = new ttree;
    root->inf = arr[mid];
    root->left = build_balanced(arr, start, mid - 1);
    root->right = build_balanced(arr, mid + 1, end);
    return root;
}

int main() {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(-50, 50);

    const int N = 10;
    int vals[N];
    bool used[101] = {false};

    for (int i = 0; i < N; ++i) {
        int num;
        do {
            num = dis(gen);
        } while (used[num + 50]);
        used[num + 50] = true;
        vals[i] = num;
    }

    for (int i = 0; i < N - 1; ++i)
        for (int j = i + 1; j < N; ++j)
            if (vals[i] > vals[j]) {
                int t = vals[i];
                vals[i] = vals[j];
                vals[j] = t;
            }

    ttree *root = build_balanced(vals, 0, N - 1);

    cout << "Исходное сбалансированное дерево:\n";
    cout << "Прямой обход: "; preorder(root); cout << "\n";
    cout << "По возрастанию: "; wrtree(root); cout << "\n";
    cout << "Обратный обход: "; postorder(root); cout << "\n";

    cout << "\nДобавляем элемент 55\n";
    root = addtree(root, 55);
    cout << "По возрастанию: "; wrtree(root); cout << "\n";

    cout << "\nУдаляем элемент " << vals[N/2] << "\n";
    root = dellist(root, vals[N/2]);
    cout << "По возрастанию: "; wrtree(root); cout << "\n";

    cout << "\nИщем элемент " << vals[0] << ":\n";
    bool found = false;
    int res;
    poisktree(root, vals[0], found, res);
    if (found) cout << "Найден: " << res << "\n";
    else cout << "Не найден\n";

    cout << "\nМеняем местами максимальный и минимальный ключи...\n";
    ttree *minNode = poiskmintreeNode(root);
    ttree *maxNode = poiskmaxtreeNode(root);
    if (minNode && maxNode) {
        int tmp = minNode->inf;
        minNode->inf = maxNode->inf;
        maxNode->inf = tmp;
    }

    cout << "Дерево после обмена:\n";
    cout << "Прямой обход: "; preorder(root); cout << "\n";
    cout << "По возрастанию: "; wrtree(root); cout << "\n";
    cout << "Обратный обход: "; postorder(root); cout << "\n";

    root = deltree(root);
    return 0;
}