AVL

#include <iostream>
#include <fstream>
using namespace std;
struct wezel{
    wezel *up;
    wezel *left;
    wezel *right;
    int val;
    int bf;
};

void RR(wezel *&root, wezel *A)
{
    wezel *B = A->right, *p = A->up;
    A->right = B->left;
    if(A->right)
        A->right->up = A;
    B->left = A;
    B->up = p;
    A->up = B;
    if(p)
    {
        if(p->left == A)
            p->left = B;
        else
            p->right = B;
    }
    if(B->bf == -1)
        A->bf = B->bf = 0;
    else
    {
        A->bf = -1;
        B->bf = 1;
    }
}

void LL(wezel *&root, wezel *A){
    wezel *B = A->left, *p = A->up;
    A->left = B->right;
    if(A->left)
        A->left->up = A;
    B->right = A;
    B->up = p;
    A->up = B;
    if(p){
        if(p->left == A)
            p->left = B;
        else
            p->right = B;
    }
    if(B->bf == 1)
        A->bf = B->bf = 0;
    else{
        A->bf = 1;
        B->bf = -1;
    }
}
void RL(wezel *&root, wezel *A){
    wezel *B = A->right, *C = B->left, *p = A->up;
    B->left = C->right;
    if(B->left)
        B->left->up = C;
    A->right = C->left;
    if(A->right)
        A->right->up = C;
    C->left = A;
    C->right = B;
    A->up = B->up = C;
    C->up = p;
    if(p){
        if(p->left == A)
            p->left = C;
        else
            p->right = C;
    }
    if(C->bf == -1)
        A->bf = 1;
    else
        A->bf = 0;
    if(C->bf == 1)
        B->bf = -1;
    else
        B->bf = 0;
    C->bf = 0;

}
void LR(wezel *&root, wezel *A){
    wezel *B = A->left, *C = B->right, *p = A->up;
    B->right = C->left;
    if(B->right)
        B->right->up = C;
    A->left = C->right;
    if(A->left)
        A->left->up = C;
    C->right = A;
    C->left = B;
    A->up = B->up = C;
    C->up = p;
    if(p){
        if(p->left == A)
            p->left = C;
        else
            p->right = C;
    }
    if(C->bf == 1)
        A->bf = -1;
    else
        A->bf = 0;
    if(C->bf == -1)
        B->bf = 1;
    else
        B->bf = 0;
    C->bf = 0;

}
void dodaj(wezel *&root, int k){
    wezel * y,* p,* x;
    bool t;
    y = new wezel;
    y->left = y->right = y->up = NULL;
    y->val  = k;
    y->bf  = 0;
    p = root;
    if(!p)
        root = y;
    else{
    while(true)
      if(k < p->val){
        if(!p->left){
          p->left = y;
          break;
        }
        p = p->left;
      }
      else{
        if(!p->right){
          p->right = y;
          break;
        }
        p = p->right;
      }
    y->up = p;

/////////////
         if(p->bf)
            p->bf = 0;
         else{
            if(p->left == y)
                p->bf = 1;
            else
                p->bf = -1;
////////////
         x = p->up;
         t = false;
         while(x){
            if(x->bf){
                t = true;
                break;
            };
            if(x->left == p)
                x->bf =  1;
            else
                x->bf = -1;
            p = x;
            x = x->up;
         }

      if(t){
        if(x->bf == 1){
          if(x->right == p)
             x->bf = 0;
          else
            if(p->bf == -1)
                    LR(root,x);
          else
            LL(root,x);
        }
        else{
          if(x->left == p)
            x->bf = 0;
          else if(p->bf == 1)
            RL(root,x);
          else
            RR(root,x);
        }
      }
    }
  }
}
void post(wezel *p){
    if(p){
        cout << p->val << " ";
        post(p->left);
        post(p->right);
    }
}
int main(){
    wezel *root = NULL;
    dodaj(root, 6);
    dodaj(root, 10);
    dodaj(root, 5);
    dodaj(root, 3);
    dodaj(root, 7);
    dodaj(root, 2);
    dodaj(root, 8);
    dodaj(root, 9);
    post(root);

}