Для балансировки АВЛ-дерева при операциях вставки и удаления производятся левые и правые повороты. Левый поворот в вершине производится, когда баланс этой вершины больше 1, аналогично, правый поворот производится при балансе, меньшем 1.

Существует два разных левых (как, разумеется, и правых) поворота: большой и малый левый поворот.

Малый левый поворот осуществляется следующим образом:

{скоро тут будет иллюстрация}

Заметим, что если до выполнения малого левого поворота был нарушен баланс только корня дерева, то после его выполнения все вершины становятся сбалансированными, за исключением случая, когда у правого ребенка корня баланс до поворота равен 1. В этом случае вместо малого левого поворота выполняется большой левый поворот, который осуществляется так:

{скоро тут будет иллюстрация}

Дано дерево, в котором баланс дерева равен 2. Сделайте левый поворот.

Входные данные

Входные данные содержат описание двоичного дерева.

В первой строке файла находится число 
n
n (
1
≤
n
≤
2
⋅
1
0
5
1≤n≤2⋅10 
5
 ) - число вершин в дереве. В последующих 
n
n строках файла находятся описания вершин дерева. В (
i
+
1
i+1)-ой строке айла (
1
≤
i
≤
n
1≤i≤n) находится описание 
i
i-ой вершины, состоящее из трех чисел 
K
i
K 
i
​	
 , 
L
i
L 
i
​	
 , 
R
i
R 
i
​	
 , разделенных пробелами ключа в 
i
i-ой вершине (
∣
K
i
∣
<
=
1
0
9
∣Ki∣<=10 
9
 ), номера левого ребенка 
i
i-ой вершины (
i
<
L
i
≤
n
i<L 
i
​	
 ≤n или 
L
i
=
0
L 
i
​	
 =0, если левого ребенка нет) и номера правого ребенка 
i
i-ой вершины (
i
<
R
i
≤
n
i<R 
i
​	
 ≤n или 
R
i
=
0
R 
i
​	
 =0, если правого ребенка нет).

Все ключи различны. Гарантируется, что данное дерево является деревом поиска. Все ключи различны. Баланс корня дерева (вершины с номером 1) равен 2, баланс всех остальных вершин находится в пределах от -1 до 1.

Выходные данные

Выведите в том же формате дерево после осуществления левого поворота. Нумерация вершин может быть произвольной при условии соблюдения формата. Так, номер вершины должен быть меньше номера ее детей. #include <iostream>

struct Node{
    int ind;
    int key;
    int height = 0;
    Node* left = nullptr;
    Node* right = nullptr;
};

struct All{
    int key;
    int left_kid;
    int right_kid;
    bool added = false;
};

int GetHeight(Node* temp) {
    if (temp == nullptr) {
        return 0;
    }

    return temp->height;
}

void AddHeight(Node*& tree) {
    if (tree != nullptr) {
        AddHeight(tree->left);
        AddHeight(tree->right);
        int left_subtree_height = GetHeight(tree->left);
        int right_subtree_height = GetHeight(tree->right);
        if (left_subtree_height > right_subtree_height) {
            tree->height = left_subtree_height + 1;
        } else {
            tree->height = right_subtree_height + 1;
        }
    }
}

Node* LeftRotate(Node* temp) {
    Node* new_root = temp->right;
    Node* new_child = new_root->left;
    new_root->left = temp;
    temp->right = new_child;
    if (GetHeight(temp->left) > GetHeight(temp->right)) {
        temp->height = GetHeight(temp->left) + 1;
    } else {
        temp->height = GetHeight(temp->right) + 1;
    }
    if (GetHeight(new_root->left) > GetHeight(new_root->right)) {
        new_root->height = GetHeight(new_root->left) + 1;
    } else {
        new_root->height = GetHeight(new_root->right) + 1;
    }

    return new_root;
}

Node* RightRotate(Node* temp) {
    Node* new_root = temp->left;
    Node* new_child = new_root->right;
    new_root->right = temp;
    temp->left = new_child;
    if (GetHeight(temp->left) > GetHeight(temp->right)) {
        temp->height = GetHeight(temp->left) + 1;
    } else {
        temp->height = GetHeight(temp->right) + 1;
    }
    if (GetHeight(new_root->left) > GetHeight(new_root->right)) {
        new_root->height = GetHeight(new_root->left) + 1;
    } else {
        new_root->height = GetHeight(new_root->right) + 1;
    }

    return new_root;
}

Node* Insert(Node* temp, All* arr, int ind) {
    if (temp == nullptr && !arr[ind].added) {
        temp = new Node();
        temp->key = arr[ind].key;
        arr[ind].added = true;
    }
    if (arr[ind].left_kid != 0) {
        temp->left = Insert(temp->left, arr, arr[ind].left_kid);
    }
    if (arr[ind].right_kid != 0) {
        temp->right = Insert(temp->right, arr, arr[ind].right_kid);
    }

    return temp;
}

void Level(Node* temp, int i, int& ind) {
    if (temp == nullptr) {
        return;
    }
    if (i == 0) {
        std::cout << temp->key << " ";
        if (temp->left != nullptr) {
            std::cout << ind << " ";
            ++ind;
        } else {
            std::cout << "0 ";
        }
        if (temp->right != nullptr) {
            std::cout << ind << '\n';
            ++ind;
        } else {
            std::cout << "0" << '\n';
        }
    } else if (i > 0) {
        Level(temp->left, i - 1, ind);
        Level(temp->right, i - 1, ind);
    }
}

void LevelOrder(Node* root, int& ind) {
    int i;
    for (i = 0; i <= root->height; ++i) {
        Level(root, i, ind);
    }
}

int main() {
    int n;
    std::cin >> n;
    Node* root = nullptr;
    All* arr = new All[n + 1];
    for (int i = 1; i < n + 1; ++i) {
        std::cin >> arr[i].key >> arr[i].left_kid >> arr[i].right_kid;
    }
    for (int i = 1; i < n + 1; ++i) {
        root = Insert(root, arr, i);
    }
    delete[] arr;
    AddHeight(root);
    if (GetHeight(root->right->left) > GetHeight(root->right->right)) {
        root->right = RightRotate(root->right);
    }
    root = LeftRotate(root);
    int ind = 2;
    std::cout << n << '\n';
    LevelOrder(root, ind);

    return 0;
} my implementation gives the wrong answers