First Project

#include <iostream>

using namespace std;

struct Node
{
    int data ;
    Node * l ;
    Node * r ;
    int counter;

    Node (int data = 0, Node * l = NULL, Node * r = NULL,int counter=1)
    {
        this -> data =data ;
        this -> l = l ;
        this -> r = r ;
        this -> counter = counter ;
    }

    bool is_leaf()
    {
        if(l== NULL && r==NULL)
        {
            return true ;
        }

        return false ;
    }
};

class Tree
{
    Node * root ;

    int h (Node * curr)
    {
        if (curr == NULL)
            return -1  ;


        int l = h(curr->l) ;
        int r = h(curr->r) ;

        return Max(l,r)+1;
    }

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

    int calc_balance (Node *curr)
    {
        if (curr == NULL)
            return 0 ;

        int l =  h(curr->l) ;
        int r =  h(curr->r) ;

        return l-r ;
    }


    void correct_balance (Node *& curr, int t)
    {
        if (t==2)
        {
            int t2 = calc_balance(curr->l);

            if(t2 < 0)
            {
                //2_doran `
                rot_l_r(curr) ;
            }
            else
            {
                rot_r(curr);
            }
        }

        else
        {
            int t3 = calc_balance(curr->r);

            if (t3 > 0)
            {
                //2_doran
                rot_r_l(curr);
            }
            else
            {
                rot_l(curr);
            }
        }
    }

    void check_if_balanced (Node *& curr)
    {
        if (curr == NULL)
            return ;

        check_if_balanced (curr->l) ;
        check_if_balanced (curr->r) ;

        int t = calc_balance (curr);

        if (t == 0 || t== 1 || t==-1)
        {
            return ;
        }

        else
        {
            correct_balance(curr,t);
        }
    }


    void rot_l (Node* & curr)
    {
        Node * a = curr ;
        Node * b = a->r ;
        Node * temp = b->l ;

        b->l = a ;
        curr = b ;
        a->r = temp ;
    }

    void rot_r (Node* & curr)
    {
        Node * a = curr ;
        Node * b = a-> l;
        Node * temp = b->r ;
        b->r = a;
        curr = b ;
        a->l = temp ;
    }

    void rot_l_r (Node *&curr)
    {
        Node * & x = curr;
        Node * & y = x->l;
        Node * & z = y->r ;

        rot_l (y) ;
        rot_r (x) ;
    }

    void rot_r_l (Node *&curr)
    {
        Node * & x = curr;
        Node * & y = x->r;
        Node * & z = y->l ;

        rot_r (y) ;
        rot_l (x) ;
    }

    void insert (int value, Node* curr)
    {

        if (curr->data == value)
            curr->counter++;

        else if (curr->data < value)
        {
            /// نضيف لليمين
            if(curr->r==NULL)
            {

                Node * nn = new Node(value) ;
                curr->r = nn ;
            }
            else
                insert(value, curr->r);
        }

        else if (curr->data > value)
        {

            if(curr->l == NULL)
            {
                Node * nn = new Node(value) ;
                curr->l = nn ;
            }
            else
                insert(value, curr->l);
        }
    }

    void display(Node * node)
    {

        if(node==NULL)
            return ;

        display(node->l);
        cout << node->data << endl ;
        display(node->r);

    }

    int getcounter(Node * curr)
    {
        return curr->counter ;
    }

    int count_high_salary (Node * curr, int value)
    {
        if (curr == NULL)
        {
            return 0 ;
        }
        if (value == curr->data)
        {
            return count_high_salary(curr->r, value);
        }

        else if (value > curr->data)
        {
            return count_high_salary(curr->r, value) ;
        }
        else
        {
            int temp = count_high_salary(curr->r, value) + getcounter(curr);
            return count_high_salary(curr->l, value) + temp ;
        }
    }

public :

    Tree()
    {
        root = NULL ;
    }


    void insert(int value)
    {
        if (root == NULL)
        {
            Node * nn = new Node;
            nn->data = value ;
            root = nn ;
        }
        else
        {
            insert(value, root) ;
        }
        check_if_balanced(root) ;
    }

    int count_high_salary (int value)
    {
        return count_high_salary(root,value) ;
    }
};

int main ()
{
    Tree ob ;

    int n, x, Q ;


    cin >> n ;

    for (int i = 0 ; i < n ; i++)
    {
        cin >> x ;
        ob.insert(x);
    }

    cin >> Q ;
    int a[Q][2];

    cout<< "------------" << endl ;


    for (int i = 0 ; i < Q ; i++)
    {
        cin >> a[i][0];
        cin >> a[i][1];
    }

    for (int i = 0 ; i < Q ; i++)
    {
        if (a[i][0] == 1)
        {
            ob.insert(a[i][1]);
        }
        else
        {
            cout << ob.count_high_salary(a[i][1]) << endl ;
        }

    }
}