Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement