#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

struct vertex {
    int data;
    vertex *left;
    vertex *right;
    int Bal;
};

void ObhodLR(vertex *p) {
    if (p != NULL) {
        ObhodLR(p->left);
        cout << p->data << "  ";
        ObhodLR(p->right);
    }
}

int Size(vertex *p) {
    if (p == NULL) return 0;
    return 1 + Size(p->left) + Size(p->right);
}

int Sum(vertex *p) {
    if (p == NULL) return 0;
    return p->data + Sum(p->left) + Sum(p->right);
}

int Height(vertex *p) {
    if (p == NULL) return 0;
    return 1 + max(Height(p->left), Height(p->right));
}

float SumPaths(vertex *p, int L) {
    if (p == NULL) return 0;
    return L + SumPaths(p->left, L + 1) + SumPaths(p->right, L + 1);
}

float Averageheight(vertex *p){
    if(p == NULL) return 0;
    else return (float(SumPaths(p, 1)) / Size(p));
}

vertex* LL(vertex* &p) {
    vertex* q = p->left;
    p->Bal = 0;
    q->Bal = 0;
    p->left = q->right;
    q->right = p;

    return q;
}

vertex* RR(vertex* &p) {
    vertex* q = p->right;
    p->Bal = 0;
    q->Bal = 0;
    p->right = q->left;
    q->left = p;

    return q;
}

vertex* LR(vertex* &p) {
    vertex* q = p->left;
    vertex* r = q->right;

    if (r->Bal < 0)
        p->Bal = 1;
    else
        p->Bal = 0;

    if (r->Bal > 0)
        q->Bal = -1;
    else
        q->Bal = 0;

    r->Bal = 0;

    q->right = r->left;
    p->left = r->right;
    r->left = q;
    r->right = p;

    return r;
}

vertex* RL(vertex* &p) {
    vertex* q = p->right;
    vertex* r = q->left;

    if (r->Bal > 0)
        p->Bal = -1;
    else
        p->Bal = 0;

    if (r->Bal < 0)
        q->Bal = 1;
    else
        q->Bal = 0;

    r->Bal = 0;

    q->left = r->right;
    p->right = r->left;
    r->right = q;
    r->left = p;

    return r;
}

bool AVL(int D, vertex*& p, bool& Rost) {
    if (p == NULL) {
        p = new vertex;
        p->data = D;
        p->left = NULL;
        p->right = NULL;
        p->Bal = 0;
        Rost = true;
        return true;
    }

    if (D < p->data) {
        if (AVL(D, p->left, Rost)) {
            if (Rost) {
                if (p->Bal > 0) {
                    p->Bal = 0;
                    Rost = false;
                } else if (p->Bal == 0) {
                    p->Bal = -1;
                    Rost = true;
                } else {
                    if (p->left->Bal < 0) {
                        p = LL(p);
                    } else {
                        p = LR(p);
                    }
                    Rost = false;
                }
            }
        }
    } else if (D > p->data) {
        if (AVL(D, p->right, Rost)) {
            if (Rost) {
                if (p->Bal < 0) {
                    p->Bal = 0;
                    Rost = false;
                } else if (p->Bal == 0) {
                    p->Bal = 1;
                    Rost = true;
                } else {
                    if (p->right->Bal > 0) {
                        p = RR(p);
                    } else {
                        p = RL(p);
                    }
                    Rost = false;
                }
            }
        }
    } else {
        Rost = false;
    }

    return true;
}

vertex* ISDP(int* elements, int L, int R) {
    if (L > R) return NULL;

    int m = ceil((L + R) / 2.0);
    vertex* p = new vertex;
    p->data = elements[m];
    p->left = ISDP(elements, L, m - 1);
    p->right = ISDP(elements, m + 1, R);
    p->Bal = 0;
    return p;
}

void ShuffleArray(int* arr, int size) {
    for (int i = size - 1; i > 0; --i) {
        int j = rand() % (i + 1);
        swap(arr[i], arr[j]);
    }
}

int main() {
    srand(time(0));

    int N = 100;

    int* elements = new int[N];

    for (int i = 0; i < N; ++i) {
        elements[i] = i+1;
    }

    vertex* rootISDP = ISDP(elements, 0, N-1);

    ShuffleArray(elements, N);

    vertex* rootAVL = NULL;
    bool Rost = false;
    for (int i = 0; i < N; ++i) {
        AVL(elements[i], rootAVL, Rost);
    }

    cout << "Обход LR по АВЛ-дереву для проверки" << endl;
    ObhodLR(rootAVL);
    cout << endl << endl;

    printf("\n|-----------------|-------------|----------------|--------------|--------------|\n");
    cout << "|       " << "   |" << "Size  " << "   |" << "Checksum" << "    |" << "Height " << "   |" << "Average_height|" << endl;
    cout << "|ISDP   " << "   |" << Size(rootISDP) << "     |" << Sum(rootISDP) << "         |" << Height(rootISDP) << "        |"; printf("%.2f", Averageheight(rootISDP)); cout << "          |" << endl;
    cout << "|AVL    " << "   |" << Size(rootAVL) << "      |" << Sum(rootAVL) << "      |" << Height(rootAVL) << "     |"; printf("%.2f", Averageheight(rootAVL)); cout << "          |" << endl;
    printf("|-----------------|-------------|----------------|--------------|--------------|");
    delete[] elements;
    return 0;
}