#include "pch.h"
#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

const unsigned char KEY_MAX_LENGTH = 5;

struct node                                                 //Представление узла дерева
{
    int key;                                                //Ключ узла
    unsigned char height;                                   //Высота поддерева с корнем в данном узле
    node* left;                                             //Указатель на левое поддерево
    node* right;                                            //Указатель на правое поддерево

    node(int k)                                             //Конструктор создаёт новый узел (высота 1) с заданным ключом "k"
    {
        key = k;                                            //Заданныйы ключ для конструктора
        left = right = nullptr;                             //Указатели на левое и правое поддерево не указывают не на что, потому что этих поддеревьев нет
        height = 1;                                         //Выосота
    }
};

unsigned char height(node* p)                               //Вычисляет высоту дерева (даже, если оно пустое)
{
    if (p)
    {
        return p->height;                                   //Если дерево не пустое, то выводим его высоту
    }
    else
    {
        return 0;                                           //Если дерево пустое, то выводим его высоту ("ноль")
    }
}

int bfactor(node* p)                                        //Вычисляет "Balance factor" заданного узла (работает только с ненулевыми указателями)
{
    return height(p->right) - height(p->left);              //"Balance factor" - это разница высот между правым и левым поддеревьями
}

void fixheight(node* p)                                     //Функция восстановления корректного значения поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются  корректными)
{
    unsigned char hl = height(p->left);                     //Вычисление высоты левого поддерева
    unsigned char hr = height(p->right);                    //Вычисление высоты правого поддерева

    if (hl > hr)
    {
        p->height = hl + 1;
    }
    else
    {
        p->height = hr + 1;
    }
}

node* rotateleft(node* q)                                   //Левый поворот
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;

    fixheight(q);
    fixheight(p);

    return p;
}

node* rotateright(node* p)                                  //Правый поворот
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;

    fixheight(p);
    fixheight(q);

    return q;
}

node* balance(node* p)                                      //Фкнкция балансировки
{                                                           //Балансоровка сводится к проверке услоовий и выполнению поворотов
    fixheight(p);                                           //Восстановим корректное значение высоты узла

    if (bfactor(p) == 2)                                    //Если разница между высотой правого и левого поддеревьв этого узла равна 2, то узнаем разницу между высотой правого и левого поддеревьев его правого поддерева
    {
        if (bfactor(p->right) < 0)                          //И если эта разница окажется меньше "0", то правое поддерево "стартового" узла совершит правый поворот
        {
            p->right = rotateright(p->right);
        }

        return rotateleft(p);                               //В конце совершим левый поворот для обрабатываемого узла
    }

    if (bfactor(p) == -2)                                   //Если разница между высотой правого и левого поддеревьв этого узла равна -2, то узнаем разницу между высотой правого и левого поддеревьев его левого поддерева
    {
        if (bfactor(p->left) > 0)                           //И если эта разница окажется больше "0", то левое поддерево "стартового" узла совершит левый поворот

        {
            p->left = rotateleft(p->left);
        }

        return rotateright(p);                              //В конце совершим правый поворот для обрабатываемого узла
    }
    return p;
}

node* insert(node* p, int k)                                //Функция вставки нового ключа в АВЛ-дерево выполняется с помощью спуска вниз по дереву, выбирая направление (правое или левое)
{
    if (!p)                                                 //Если этого узла ещё не существует, то сюда и вставляем
    {
        return new node(k);
    }

    if (k < p->key)                                         //Если вставляемый ключ меньше ключа проверяемого узла, то  идёт вставка в левое поддерево
    {
        p->left = insert(p->left, k);
    }

    else                                                    //Если вставляемый ключ больше ключа проверяемого узла, то  идёт вставка в правое поддерево
    {
        p->right = insert(p->right, k);
    }

    return balance(p);                                      //Баланисруем текущий узел
}

node* findmin(node* p)                                      //Функция поиска узла с минимальным ключом
{
    if (p->left)                                            //Спускаемся влево
    {
        return findmin(p->left);
    }
    else
    {
        return p;                                           //Самый левый узел будет содержать ключ с минимальным значением
    }
}

node* removemin(node* p)                                    //Функция даления узла с минимальным ключом
{
    if (p->left == 0)                                       //По определению АВЛ-дерева, у минимального элемента справа либо подвешен единственный узел, либо там пусто
    {
        return p->right;                                    //В обоих случаях надо вернуть указатель на правый узел
    }

    p->left = removemin(p->left);

    return balance(p);                                      //И по пути назад выполинть балансировку
}

node* remove(node* p, int k)                                //Функция удаления ключа из дерева
{
    if (!p)                                                 //Если дерево пустое, то нечего удалять
    {
        return 0;
    }

    if (k < p->key)                                         //Спускаемся вниз, пока не найдём наш ключ
    {
        p->left = remove(p->left, k);
    }

    else {
        if (k > p->key)
        {
            p->right = remove(p->right, k);
        }
        else                                                //Как только находим
        {
            node* q = p->left;                              //Запомним в "q" левое поддерево узла, который собираемся удалять
            node* r = p->right;                             //Запомним в "r" правое поддерево узла, который собираемся удалять

            delete p;                                       //Удаляем сам узел

            if (!r)                                         //Если правое поддерерво пустое, то возвращаем указатель на левое поддерево
            {
                return q;
            }

            node* min = findmin(r);                         //Если правое поддерерво не пустое, то находим там минимальный элемент "min"

            min->right = removemin(r);                      //Справа подвесим к "min" то, что получилось из "r"
            min->left = q;                                  //Слева подвесим к min "q"

            return balance(min);                            //Возвращаем "min" после его балансировки
        }
    }
    return balance(p);                                      //После выхода из рекурсии выполняем балансировку
}

bool search(node* p, int k)                                 //Функция поиска ключа
{
    bool res = false;

    if (p)                                                  //Если дерево пустое, то нет смысла искать
    {
        if (k == p->key)                                    //Если нашли, получаем истину
        {
            return true;
        }
        if (k < p->key)                                     //Если ключ, который мы ищем меньше того, на котором мы остановились, то спусакамся влево
        {
            res = search(p->left, k);
        }
        if (k > p->key)                                     //Если ключ, который мы ищем больше того, на котором мы остановились, то спусакамся вправо
        {
            res = search(p->right, k);
        }
    }
    return res;                                             //Если после всего дерева такого ключа нет, то получаем ложь
}

void printGL(node* p, int height)                           //Функция вывода АВЛ-дерева
{
    if (p)                                                  //Если дерево пустое, то нет смысла выводить
    {
        if (p->left)
        {
            height--;
            printGL(p->left, height);
            height++;
        }
        for (int i = 0; i < height; i++)
        {
            cout << "\t";
        }
        cout << p->key;
        cout << endl;

        if (p->right)
        {
            height--;
            printGL(p->right, height);
            height++;
        }
    }
}

int main()
{
    char choice = 0;
    node* p = nullptr;
    do {
        system("cls");
        cout << "Please, make a choice: " << endl;

        cout << "1 - add" << endl;
        cout << "2 - remove" << endl;
        cout << "3 - search" << endl;
        cout << "4 - print" << endl;

        choice = _getch();
        switch (choice) {
        case '1':
            int a;
            cout << "Enter a key: ";

            cin >> a;

            if (!p) {
                p = new node(a);
            }
            else {
                if (search(p, a)) {
                    cout << a << " already exist!" << endl;
                }
                else {
                    p = insert(p, a);
                    cout << "insertion of " << a << " has been made succesfully" << endl;
                }
            }
            system("pause");
            break;
        case '2':
            if (p) {
                cout << "Enter a key that you wanna remove: ";
                int a;
                cin >> a;
                if (search(p, a)) {
                    p = remove(p, a);
                    cout << "remove of " << a << " has been made succesfully" << endl;
                }
                else {
                    cout << a << " doesn't exist!" << endl;
                }
            }
            else {
                cout << "Your tree is empty" << endl;
            }
            system("pause");
            break;
        case '3':
            if (p) {
                cout << "Enter a key that you wanna search: ";
                int a;
                cin >> a;
                if (search(p, a))
                    cout << a << " has been found succesfully" << endl;
                else
                    cout << a << " has not been found" << endl;
            }
            else {
                cout << "Your tree is empty" << endl;
            }
            system("pause");
            break;
        case '4':
            if (p) {
                cout << "Your tree: " << endl;
                printGL(p, p->height - 1);
            }
            else {
                cout << "Your tree is empty" << endl;
            }
            system("pause");
            break;
        }
    } while (choice != 27);
    _getch();
}