AVL merge

#include "bits/stdc++.h"
//speed coding handle

#define mp make_pair
#define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " ";  }cout << "\n";} ;
#define f first
#define s second
#define loop(i, x, n) for (int i = x; i < n; i++)
#define joop(x, n) for (ll j = x; j < n; j++)
#define lp(n) for (ll i = 0; i < n; i++)
#define err cout << "ERROR" << endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) x.size()
#define rndm rng()

// types
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
typedef long long ll;
typedef long double ld;

// types of data
#define inf 1000000000
#define infll 1000000000000000000
#define INF ll(1e18)

#define md 998244353
#define mod 1000000009
//#define K 239017

#define DEBUG 1
using namespace std;
mt19937_64 rng(113113);
uniform_int_distribution<ll> drist;

struct node // структура для представления узлов дерева
{
    int info;//значение
    node *left;//ссылка на левое поддерево
    node *right;//ссылка на правое поддерево
    int balance; // поле баланса= высота правого поддерева - высота левого поддерева
};


int Height(node *root)// вычисляет высоту дерева
{
    if (root == nullptr) return 0;//если дерево пусто возвращаем 0
    //иначе
    int hLeft = Height(root->left),//считаем высоту левого поддерева
    hRight = Height(root->right); //считаем высоту правого поддерева
    return max(hLeft, hRight) + 1;

}

void SetBalance(node *(&root))//нахождение значение баланса для текущего узла
{
    if (root != nullptr)
        root->balance = Height(root->right) - Height(root->left);
}

void TurnLeft(node *(&root))//левый поворот АВЛ-дерева
{
    node *rightSubtree, *rightSubtreeLeftSubtree;
    rightSubtree = root->right;
    rightSubtreeLeftSubtree = rightSubtree->left;

    rightSubtree->left = root;
    root->right = rightSubtreeLeftSubtree;
    root = rightSubtree;
    SetBalance(root->left);
    SetBalance(root);
}

void TurnRight(node *(&root))//правый поворот
{
    node *leftSubtree, *leftSubtreeRightSubtree;
    leftSubtree = root->left;
    leftSubtreeRightSubtree = leftSubtree->right;

    leftSubtree->right = root;
    root->left = leftSubtreeRightSubtree;
    root = leftSubtree;
    SetBalance(root->right);
    SetBalance(root);
}


void insert(node *(&root), int d) // добавление узла в дерево поиска
{
    if (root == nullptr)//нашли пустой указатель – пустое место
    { //создаём новый узел дерева на найденном месте
        root = new node;
        root->info = d;
        root->balance = 0;
        root->left = nullptr;
        root->right = nullptr;
    }
    else//текущий узел не пуст
    {
        if (d > root->info)//идём в правое поддерево

        {
            insert(root->right, d);//добавляем узел в правое поддерево
            if (Height(root->right) - Height(root->left) > 1)//если баланс АВЛ-дерева нарушен
            {//выполняем вращения
                if (Height(root->right->right) < Height(root->right->left))//а если были еще проблемы в поддеревьях у правого поддерева
                    TurnRight(root->right);//то предварительно поворачиваем правое поддерево
                TurnLeft(root);//поворот дерева влево
            }
        }
        else if (d < root->info)//идём в левое поддерево

        {

            insert(root->left, d);//добавляем узел в левое поддерево
            if (Height(root->left) - Height(root->right) > 1)//если баланс АВЛ-дерева нарушен
            {
                if (Height(root->left->left) < Height(root->left->right))//а если были еще проблемы в поддеревьях у левого поддерева
                    TurnLeft(root->left);//то предварительно поворачиваем левое поддерево
                TurnRight(root);//поворот дерева вправо
            }
        }

        SetBalance(root);//пересчитываем значение баланса
    }
}

void copytree(node *(&T1), node * (&root)){
//    node *root = new node;


}
void print(node *p);
void balance(node *(&root)) // балансировка
{
    if (root != nullptr)//нашли пустой указатель – пустое место//текущий узел не пуст
    {
        // сортим правое
        balance(root->right);//добавляем узел в правое поддерево
        if (Height(root->right) - Height(root->left) > 1)//если баланс АВЛ-дерева нарушен
        {//выполняем вращения
            if (Height(root->right->right) < Height(root->right->left))//а если были еще проблемы в поддеревьях у правого поддерева
                TurnRight(root->right);//то предварительно поворачиваем правое поддерево
            TurnLeft(root);//поворот дерева влево
        }

        //идём в левое поддерево


        balance(root->left);//идём
        if (Height(root->left) - Height(root->right) > 1)//если баланс АВЛ-дерева нарушен
        {
            if (Height(root->left->left) < Height(root->left->right))//а если были еще проблемы в поддеревьях у левого поддерева
                TurnLeft(root->left);//то предварительно поворачиваем левое поддерево
            TurnRight(root);//поворот дерева вправо
            cout << "PPPPP" << endl;

        }


        SetBalance(root);//пересчитываем значение баланса
    }
}
node* merge(node *(&T1), node *(T2)){
    // выбрать левый в T2, удалить, добавить root(t1), добавить удалённое

    // удалить самую правую,
    // идем по 2му, когда высота
    node *v1 = T1, *pv1 = new node;
    while(v1->right){
        pv1 = v1;
        v1 = v1->right;

//        v->left = nullptr;
    }
    pv1->right = nullptr;
    // нашёл отчистил
    node *v2 = T2, *pv2 = new node;
    while(v2 != nullptr and Height(v2) != Height(T1)){
        cout << "ERR " << v2->info << endl;
        pv2 = v2;
        v2 = v2->left;
    }
    node *S = new node;
    S->info = v1->info;
    S->left = T1;
    S->right = v2;

    cout << "\n S: \n";
    print(S);
    cout << "\nv2\n" << v2->info;
    pv2->left = S;
//    balance(T2);
    cout << "Start:\n";
    print(T2);
    balance(T2);
    print(T2);
    cout << "End\n";
//    cout << "LEFT:" << v->info << " " << pv->info << "\n";
//    pv->left = T1;
    return T2;

//    insert(T2, v->info);




}

void output(node *p)// распечатка дерева в симметричном порядке
{
    if (p != nullptr)
    {
        output(p->left);
        cout << p->info << " ";
        output(p->right);
    }
}

void print_n(const node *p, int n, int level, int prob)//печать n-ого уровня дерева, level - это номер уровня
{
    if (p)
    {
        if (level == n)
        {
            for (int i = 1; i <= prob; i++) cout << " ";
            cout << p->info;
        }
        else
        {
            print_n(p->left, n, level + 1, prob);
            print_n(p->right, n, level + 1, prob);
        }
    }
}

void print(node *p) //распечатка дерева по уровням
{
    int h = Height(p);
    int prob = 3;
    if (p)
    {
        for (int i = 0; i <= h; i++)//вот здесь задаются номера уровней
        {
            print_n(p, i, 0, prob*(h - i));//вызывается функция печати n-ого уровня дерева
            cout << endl;
        }
    }
    cout << "H " << h << endl;
}


void clear(node **p) // очистка
{
    if ((*p) != nullptr) {
        cout << "ERRr " << (*p)->info << endl;

        clear(&(*p)->left);
        clear(&(*p)->right);

        delete *p;
        *p = nullptr;
    }
}

void solve()
{
    int  d;
    char ch;
    node *root;
    root = nullptr;
    do {
        cout << "enter num" << endl;
        cin >> d;
        insert(root, d);
        cout << "eshe? (y/n)" << endl;
        cin >> ch;

    } while (ch != 'n');

    node *root2;
    root2 = nullptr;
    do {
        cout << "enter num" << endl;
        cin >> d;
        insert(root2, d);
        cout << "eshe? (y/n)" << endl;
        cin >> ch;

    } while (ch != 'n');

    cout << endl;
    cout << "print1" << endl;
    print(root);

    cout << "print2" << endl;
    print(root2);
    node *t = merge(root, root2);
    cout << "print:\n";

    print(t);

    cout << "simm:\n";
    output(t);
//    cout << "\n EDGE: " << t->info << endl;
//    clear(&root);
//    clear(&root2);
    clear(&t);
    if (!root and !root2 and !t) { cout << "cleared!" << endl; }
    else { cout << "err!" << endl; }
    system("pause");
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("text.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    solve();
    return 1;
}