#include <iostream>
#include <ctime>
#include <iomanip>

using namespace std;

int maximum(int a, int b)
{
    if (a > b) return a;
    else return b;
}

int minimum(int a, int b)
{
    if (a > b) return b;
    else return a;
}

struct Node
{
    int key;
    struct Node* left;
    struct Node* right;
};

typedef struct Node N;

N* treeInit(int _key)
{
    N* newNode = new N;
    newNode->key = _key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

N* searchInsert(N* Root, int _key)
{
    N* tmp = Root;
    N* prev = NULL;
    bool found = false;

    while ((tmp != NULL) && (found == false))
    {
        prev = tmp;
        if (_key == tmp->key)
            found = true;
        else
        {
            if (_key < tmp->key) tmp = tmp->left;
            else  tmp = tmp->right;
        }
    }
    if (found)
        return tmp;

    N* newNode = new N;
    newNode->key = _key;
    newNode->left = NULL;
    newNode->right = NULL;
    if (_key < prev->key)
        prev->left = newNode;
    else
        prev->right = newNode;
    return newNode;
}

int MaxTreeH(N* Root) {
    if (Root == NULL)
        return 0;
    return 1 + maximum(MaxTreeH(Root->left), MaxTreeH(Root->right));
}

int MinTreeH(N* Root) {
    if (Root == NULL)
        return 0;
    return 1 + minimum(MinTreeH(Root->left), MinTreeH(Root->right));
}

void printTree(N* Root, int level)
{
    if (Root != NULL)
    {
        printTree(Root->right, level + 1);
        for (int i = 0; i < level; i++) cout << "   ";
        cout << Root->key << endl;
        printTree(Root->left, level + 1);
    }
}

void deleteTree(N* Root)
{
    if (Root == NULL) return;

    deleteTree(Root->left);
    deleteTree(Root->right);
    delete Root;
}

struct RNode
{
    int key;
    int size;
    RNode* left;
    RNode* right;
};

typedef RNode* RN;

RN RTreeInit(int _key)
{
    RN newNode = new RNode;
    newNode->key = _key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void printRTree(RN Root, int level)
{
    if (Root != NULL)
    {
        printRTree(Root->right, level + 1);
        for (int i = 0; i < level; i++) cout << "   ";
        cout << Root->key << endl;
        printRTree(Root->left, level + 1);
    }
}

int SizeRTree(RN _node)
{
    if (_node == NULL) return 0;
    return _node->size;
}

void fixRTreeSize(RN _node)
{
    _node->size = SizeRTree(_node->left) + SizeRTree(_node->right) + 1;
}

RN rotateRight(RN _node)
{
    RN tmp = _node->left;
    if (!tmp) return _node;
    _node->left = tmp->right;
    tmp->right = _node;
    tmp->size = _node->size;
    fixRTreeSize(_node);
    return tmp;
}

RN rotateLeft(RN _node)
{
    RN tmp = _node->right;
    if (!tmp) return _node;
    _node->right = tmp->left;
    tmp->left = _node;
    tmp->size = _node->size;
    fixRTreeSize(_node);
    return tmp;
}

RN insertToRTreeRoot(RN* _node, int _key)
{
    if (!(*_node))
    {
        RN newNode = new RNode;
        newNode->size = 1;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->key = _key;
        return newNode;
    }

    if (_key < (*_node)->key)
    {
        (*_node)->left = insertToRTreeRoot(&((*_node)->left), _key);
        return rotateRight((*_node));
    }
    else
    {
        (*_node)->right = insertToRTreeRoot(&((*_node)->right), _key);
        return rotateLeft((*_node));
    }
}

RN insertRand(RN* _node, int _key)
{
    if (!(*_node))
    {
        RN newNode = new RNode;
        newNode->size = 1;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->key = _key;
        return newNode;
    }
    if (rand() % ((*_node)->size + 1) == 0) return (*_node) = insertToRTreeRoot(_node, _key);
    if ((*_node)->key > _key)   (*_node)->left = insertRand(&((*_node)->left), _key);
    else (*_node)->right = insertRand(&((*_node)->right), _key);
    fixRTreeSize((*_node));
    return (*_node);
}

int getMaxRTreeHeight(RN Root) {
    if (Root == NULL)
        return 0;
    return 1 + maximum(getMaxRTreeHeight(Root->left), getMaxRTreeHeight(Root->right));
}

int getMinRTreeHeight(RN Root) {
    if (Root == NULL)
        return 0;
    return 1 + minimum(getMinRTreeHeight(Root->left), getMinRTreeHeight(Root->right));
}

void deleteRTree(RN Root)
{
    if (Root == NULL) return;

    deleteRTree(Root->left);
    deleteRTree(Root->right);
    delete Root;
}

struct DATA
{
    int* mas;
    int min;
    int max;
    int size;
};

typedef struct DATA Data;


int random(int N)
{
    int result = rand() % N;
    return result;
}


int formRArray(Data* data)
{
    int tmp;
    bool inArray;
    int i = 0;
    if ((data->max - data->min) < data->size) return -1;
    while (i < data->size)
    {
        inArray = false;
        tmp = data->min + random(data->max - data->min);
        for (int j = 0; j < i; j++)
        {
            if (data->mas[j] == tmp)
            {
                inArray = true;
                break;
            }
        }
        if (inArray == false)
        {
            data->mas[i] = tmp;
            i++;
        }
    }
    return 0;
}

int copyArray(Data dataFrom, Data* dataTo)
{
    for (int i = 0; i < dataFrom.size; i++)
    {
        dataTo->mas[i] = dataFrom.mas[i];
    }
    return 0;
}


void printMas(Data& data)
{
    for (int i = 0; i < data.size; i++)
        cout << data.mas[i] << ' ';
    cout << '\n';
}

void ShellSort(Data& data)
{
    int h = 0;

    while (h < data.size / 3)
    {
        h = 3 * h + 1;
    }

    for (h; h > 0; h = (h - 1) / 3)
    {
        for (int i = h; i < data.size; i++)
        {
            int j = i;
            int tmp = data.mas[i];

            for (j = i; j >= h && data.mas[j - h] > tmp; j -= h)
            {
                data.mas[j] = data.mas[j - h];

            }
            data.mas[j] = tmp;
        }
    }

    return;
}

int main()
{
    system("color F0");
    setlocale(LC_ALL, "RUS");

    srand(time(NULL));

    N* Tree1 = NULL;
    N* Tree2 = NULL;

    RN RandTree1 = NULL;
    RN RandTree2 = NULL;

    Data unsortedArray{ NULL, 0, 1000, 10 };
    Data sortedArray{ NULL, 0, 1000, 10 };

    unsortedArray.mas = new int[unsortedArray.size];

    formRArray(&unsortedArray);

    sortedArray.mas = new int[sortedArray.size];

    copyArray(unsortedArray, &sortedArray);

    ShellSort(sortedArray);

    cout << "Несортированная последовательность: "; printMas(unsortedArray);
    cout << "\nСортированная последовательность: "; printMas(sortedArray);

    Tree1 = treeInit(unsortedArray.mas[0]);
    Tree2 = treeInit(sortedArray.mas[0]);

    for (int i = 1; i < unsortedArray.size; i++)
    {
        searchInsert(Tree1, unsortedArray.mas[i]);
    }

    for (int i = 0; i < unsortedArray.size; i++)
    {
        RandTree1 = insertRand(&RandTree1, unsortedArray.mas[i]);
    }

    for (int i = 1; i < sortedArray.size; i++)
    {
        searchInsert(Tree2, sortedArray.mas[i]);
    }

    for (int i = 0; i < sortedArray.size; i++)
    {
        RandTree2 = insertRand(&RandTree2, sortedArray.mas[i]);
    }


    cout << "\nДеревья для несортированной последовательности: \n\n";

    cout << "\nОбычное дерево:\n";
    printTree(Tree1, 0);
    cout << "\nМаксимальная высота: " << MaxTreeH(Tree1) << endl;
    cout << "Минимальная высота: " << MinTreeH(Tree1) << endl;
    cout << "\nРандомизированное дерево:\n";
    printRTree(RandTree1, 0);
    cout << "\nМаксимальная высота: " << getMaxRTreeHeight(RandTree1) << endl;
    cout << "Минимальная высота: " << getMinRTreeHeight(RandTree1) << endl;

    cout << "\n\nДеревья для сортированной последовательности: \n\n";

    cout << "\nОбычное дерево:\n";
    printTree(Tree2, 0);
    cout << "\nМаксимальная высота: " << MaxTreeH(Tree2) << endl;
    cout << "Минимальная высота: " << MinTreeH(Tree2) << endl;;
    cout << "\nРандомизированное дерево:\n";
    printRTree(RandTree2, 0);
    cout << "\nМаксимальная высота: " << getMaxRTreeHeight(RandTree2) << endl;
    cout << "Минимальная высота: " << getMinRTreeHeight(RandTree2) << endl;



    deleteTree(Tree1);
    deleteTree(Tree2);
    deleteRTree(RandTree1);
    deleteRTree(RandTree2);

    delete[] unsortedArray.mas;
    delete[] sortedArray.mas;

    cout << endl;

    for (int keyCount = 25; keyCount <= 300; keyCount = keyCount + 25)
    {
        Tree1 = NULL;
        Tree2 = NULL;

        RandTree1 = NULL;
        RandTree2 = NULL;

        unsortedArray.size = keyCount;
        sortedArray.size = keyCount;

        unsortedArray.mas = new int[keyCount];
        formRArray(&unsortedArray);
        sortedArray.mas = new int[keyCount];
        copyArray(unsortedArray, &sortedArray);
        ShellSort(sortedArray);

        Tree1 = treeInit(unsortedArray.mas[0]);
        Tree2 = treeInit(sortedArray.mas[0]);
        RandTree1 = insertRand(&RandTree1, unsortedArray.mas[0]);
        RandTree2 = insertRand(&RandTree2, unsortedArray.mas[0]);

        for (int i = 1; i < keyCount; i++)
        {
            searchInsert(Tree1, unsortedArray.mas[i]);
            RandTree1 = insertRand(&RandTree1, unsortedArray.mas[i]);
            searchInsert(Tree2, sortedArray.mas[i]);
            RandTree2 = insertRand(&RandTree2, sortedArray.mas[i]);
        }

        cout << " n = " << keyCount << endl;
        cout << " Случайная последовательность максимум:" << endl;
        cout << "   Обычное дерево: высота " << MaxTreeH(Tree1) << endl;
        cout << "   Рандом. дерево: высота " << MaxTreeH(Tree2) << endl;
        cout << "\n Упорядоченная последовательность максимум:" << endl;
        cout << "   Обычное дерево: высота " << getMaxRTreeHeight(RandTree1) << endl;
        cout << "   Рандом. дерево: высота " << getMaxRTreeHeight(RandTree2) << endl;
        cout << "\n Случайная последовательность минимум:" << endl;
        cout << "   Обычное дерево: высота " << MinTreeH(Tree1) << endl;
        cout << "   Рандом. дерево: высота " << MinTreeH(Tree2) << endl;
        cout << "\n Упорядоченная последовательность минимум:" << endl;
        cout << "   Обычное дерево: высота " << getMinRTreeHeight(RandTree1) << endl;
        cout << "   Рандом. дерево: высота " << getMinRTreeHeight(RandTree2) << "\n\n\n";

        deleteTree(Tree1);
        deleteTree(Tree2);
        deleteRTree(RandTree1);
        deleteRTree(RandTree2);

        delete unsortedArray.mas;
        delete sortedArray.mas;
    }
}