#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <locale.h>
#include <ctime>
#include <iostream>

using namespace std;

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


vertex* root;
vertex* root2;
int ymen;
int rost;
int raz, sum, vismax;

int VR = 1;
int HR = 1;

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

int summa(vertex* p)
{
    if (p == NULL)
        sum = 0;
    else
        sum = p->data + summa(p->left) + summa(p->right);
}

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

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

int tree_len_sum(vertex* p, int level = 0)
{
    int len_sum = 0;
    if (p == 0)
        return len_sum;
    else
        len_sum = level + tree_len_sum(p->left, level + 1) + tree_len_sum(p->right, level + 1);
    return len_sum;
}

double medium_tree_height(vertex* root)
{
    return (double)tree_len_sum(root, 1) / tree_size(root);
}

void random(int A[], int N)
{
    srand(time(NULL));
    int i;
    for (i = 0; i < N; i++)
        A[i] = i;

    for (i = N - 1; i >= 1; i--) {
        int j = rand() % (i + 1);

        int tmp = A[j];
        A[j] = A[i];
        A[i] = tmp;
    }
}

void vivod(int A[], int N)
{
    for (int i = 0; i < N; i++)
        printf("%d ", A[i]);
}

void obhod(vertex* p)
{
    if (p != NULL) {
        obhod(p->left);
        cout << p -> data << " ";
        obhod(p->right);
    }
}
void LL(vertex*& p)
{
    vertex* q;
    q = p->left;
    q->balance = 0;
    p->balance = 0;
    p->left = q->right;
    q->right = p;
    p = q;
}

void LR(vertex*& p)
{
    vertex *q, *r;
    q = p->left;
    r = q->right;
    if (r->balance < 0)
        p->balance = 1;
    else
        p->balance = 0;
    if (r->balance > 0)
        q->balance = -1;
    else
        q->balance = 0;
    r->balance = 0;
    q->right = r->left;
    p->left = r->right;
    r->left = q;
    r->right = p;
    p = r;
}
void RR(vertex*& p)
{
    vertex* q;
    q = p->right;
    q->balance = 0;
    p->balance = 0;
    p->right = q->left;
    q->left = p;
    p = q;
}

void RL(vertex*& p)
{
    vertex *r, *q;
    q = p->right;
    r = q->left;
    if (r->balance > 0)
        p->balance = -1;
    else
        p->balance = 0;
    if (r->balance < 0)
        q->balance = 1;
    else
        q->balance = 0;
    r->balance = 0;
    q->left = r->right;
    p->right = r->left;
    r->right = q;
    r->left = p;
    p = r;
}

void AVL(int D, vertex*& p)
{

    if (p == NULL) {
        p = new vertex;
        p->data = D;
        p->left = NULL;
        p->right = NULL;
        p->balance = 0;
        rost = 1;
    }
    else if (p->data > D) {
        AVL(D, p->left);
        if (rost == 1) {
            if (p->balance > 0) {
                p->balance = 0;
                rost = 0;
            }
            else if (p->balance == 0) {
                p->balance = -1;
            }
            else if (p->left->balance < 0) {
                LL(p);
                rost = 0;
            }
            else {
                LR(p);
                rost = 0;
            }
        }
    }
    else if (p->data < D) {
        AVL(D, p->right);
        if (rost == 1) {
            if (p->balance < 0) {
                p->balance = 0;
                rost = 0;
            }
            else if (p->balance == 0) {
                p->balance = 1;
            }
            else if (p->right->balance > 0) {
                RR(p);
                rost = 0;
            }
            else {
                RL(p);
                rost = 0;
            }
        }
    }
}

void LL1(vertex*& p)
{
    vertex* q;
    q = p->left;
    if (q->balance == 0) {
        q->balance = 1;
        p->balance = -1;
        ymen = 0;
    }
    else {
        q->balance = 0;
        p->balance = 0;
    }
    p->left = q->right;
    q->right = p;
    p = q;
}

void RR1(vertex*& p)
{
    vertex* q;
    q = p->right;
    if (q->balance == 0) {
        q->balance = -1;
        p->balance = 1;
        ymen = 0;
    }
    else {
        q->balance = 0;
        p->balance = 0;
    }
    p->right = q->left;
    q->left = p;
    p = q;
}
void BL(vertex*& p)
{
    if (p->balance == -1)
        p->balance = 0;
    else if (p->balance == 0) {
        p->balance = 1;
        ymen = 0;
    }
    else if (p->right->balance >= 0)
        RR1(p);
    else
        RL(p);
}

void BR(vertex*& p)
{
    if (p->balance == 1)
        p->balance = 0;
    else if (p->balance == 0) {
        p->balance = -1;
        ymen = 0;
    }
    else if (p->left->balance <= 0)
        LL1(p);
    else
        LR(p);
}

void del(vertex*& r, vertex*& q)
{
    if (r->right != NULL) {
        del(r->right, q);
        if (ymen)
            BR(r);
    }
    else {
        q->data = r->data;
        q = r;
        r = r->left;
        // delete (q);
        ymen = 1;
    }
}

void del_AVL(int D, vertex*& p)
{
    vertex* q;
    if (p == NULL) {
        ymen = 0;
    }
    else {
        if (D < p->data) {
            del_AVL(D, p->left);
            if (ymen)
                BL(p);
        }
        else {
            if (D > p->data) {
                del_AVL(D, p->right);
                if (ymen)
                    BR(p);
            }
            else {
                q = p;
                if (q->left == NULL) {
                    p = q->right;
                    ymen = 1;
                }
                else if (q->right == NULL) {
                    p = q->left;
                    ymen = 1;
                }
                else {
                    del(q->left, q);
                    if (ymen)
                        BL(p);
                }
                delete (q);
            }
        }
    }
}

void b2insert(int D, vertex *&p)
{
    vertex *q;
    if (p == NULL){
        p = new vertex;
        p -> data = D;
        p -> left = p -> right = NULL;
        p -> balance = 0;
        VR = 1;
    } else if (p -> data > D) {
        b2insert(D, p -> left);
        if (VR == 1){
            if (p -> balance == 0){
                q = p -> left;
                p -> left = q -> right;
                q -> right = p;
                p = q;
                q -> balance = 1;
                VR = 0;
                HR = 1;
            } else {
                p -> balance = 0;
                VR = 1;
                HR = 0;
            }
        } else {
            HR = 0;
        }
    } else if(p -> data < D){
        b2insert(D, p -> right);
        if (VR == 1){
            p -> balance = 1;
            HR = 1;
            VR = 0;
        } else if (HR == 1){
            if (p -> balance == 1){
                q = p -> right;
                p -> balance = 0;
                q -> balance = 0;
                p -> right = q -> left;
                q -> left = p;
                q = p;
                VR = 1;
                HR = 0;
            } else {
                HR = 0;
            }
        }
    }
}

int main()
{
    int *A, N = 100, w;
    A = new int[N];
    random(A, N);
    root = NULL;
    root2 = NULL;
    for (int i = 0; i < N; i++) {
        // AVL(A[i], root);
        cout << A[i] << " ";
        b2insert(A[i], root2);
    }
    cout << "---" << endl;
    obhod(root2);
    system("pause");
}