SHARE
TWEET

First Project

a guest May 26th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct Node
  6. {
  7.     int data ;
  8.     Node * l ;
  9.     Node * r ;
  10.     int counter;
  11.  
  12.     Node (int data = 0, Node * l = NULL, Node * r = NULL,int counter=1)
  13.     {
  14.         this -> data =data ;
  15.         this -> l = l ;
  16.         this -> r = r ;
  17.         this -> counter = counter ;
  18.     }
  19.  
  20.     bool is_leaf()
  21.     {
  22.         if(l== NULL && r==NULL)
  23.         {
  24.             return true ;
  25.         }
  26.  
  27.         return false ;
  28.     }
  29. };
  30.  
  31. class Tree
  32. {
  33.     Node * root ;
  34.  
  35.     int h (Node * curr)
  36.     {
  37.         if (curr == NULL)
  38.             return -1  ;
  39.  
  40.  
  41.         int l = h(curr->l) ;
  42.         int r = h(curr->r) ;
  43.  
  44.         return Max(l,r)+1;
  45.     }
  46.  
  47.     int Max(int a, int b)
  48.     {
  49.         if (a>b)
  50.         {
  51.             return a ;
  52.         }
  53.         else
  54.         {
  55.             return b;
  56.         }
  57.     }
  58.  
  59.     int calc_balance (Node *curr)
  60.     {
  61.         if (curr == NULL)
  62.             return 0 ;
  63.  
  64.         int l =  h(curr->l) ;
  65.         int r =  h(curr->r) ;
  66.  
  67.         return l-r ;
  68.     }
  69.  
  70.  
  71.     void correct_balance (Node *& curr, int t)
  72.     {
  73.         if (t==2)
  74.         {
  75.             int t2 = calc_balance(curr->l);
  76.  
  77.             if(t2 < 0)
  78.             {
  79.                 //2_doran `
  80.                 rot_l_r(curr) ;
  81.             }
  82.             else
  83.             {
  84.                 rot_r(curr);
  85.             }
  86.         }
  87.  
  88.         else
  89.         {
  90.             int t3 = calc_balance(curr->r);
  91.  
  92.             if (t3 > 0)
  93.             {
  94.                 //2_doran
  95.                 rot_r_l(curr);
  96.             }
  97.             else
  98.             {
  99.                 rot_l(curr);
  100.             }
  101.         }
  102.     }
  103.  
  104.     void check_if_balanced (Node *& curr)
  105.     {
  106.         if (curr == NULL)
  107.             return ;
  108.  
  109.         check_if_balanced (curr->l) ;
  110.         check_if_balanced (curr->r) ;
  111.  
  112.         int t = calc_balance (curr);
  113.  
  114.         if (t == 0 || t== 1 || t==-1)
  115.         {
  116.             return ;
  117.         }
  118.  
  119.         else
  120.         {
  121.             correct_balance(curr,t);
  122.         }
  123.     }
  124.  
  125.  
  126.     void rot_l (Node* & curr)
  127.     {
  128.         Node * a = curr ;
  129.         Node * b = a->r ;
  130.         Node * temp = b->l ;
  131.  
  132.         b->l = a ;
  133.         curr = b ;
  134.         a->r = temp ;
  135.     }
  136.  
  137.     void rot_r (Node* & curr)
  138.     {
  139.         Node * a = curr ;
  140.         Node * b = a-> l;
  141.         Node * temp = b->r ;
  142.         b->r = a;
  143.         curr = b ;
  144.         a->l = temp ;
  145.     }
  146.  
  147.     void rot_l_r (Node *&curr)
  148.     {
  149.         Node * & x = curr;
  150.         Node * & y = x->l;
  151.         Node * & z = y->r ;
  152.  
  153.         rot_l (y) ;
  154.         rot_r (x) ;
  155.     }
  156.  
  157.     void rot_r_l (Node *&curr)
  158.     {
  159.         Node * & x = curr;
  160.         Node * & y = x->r;
  161.         Node * & z = y->l ;
  162.  
  163.         rot_r (y) ;
  164.         rot_l (x) ;
  165.     }
  166.  
  167.     void insert (int value, Node* curr)
  168.     {
  169.  
  170.         if (curr->data == value)
  171.             curr->counter++;
  172.  
  173.         else if (curr->data < value)
  174.         {
  175.             /// نضيف لليمين
  176.             if(curr->r==NULL)
  177.             {
  178.  
  179.                 Node * nn = new Node(value) ;
  180.                 curr->r = nn ;
  181.             }
  182.             else
  183.                 insert(value, curr->r);
  184.         }
  185.  
  186.         else if (curr->data > value)
  187.         {
  188.  
  189.             if(curr->l == NULL)
  190.             {
  191.                 Node * nn = new Node(value) ;
  192.                 curr->l = nn ;
  193.             }
  194.             else
  195.                 insert(value, curr->l);
  196.         }
  197.     }
  198.  
  199.     void display(Node * node)
  200.     {
  201.  
  202.         if(node==NULL)
  203.             return ;
  204.  
  205.         display(node->l);
  206.         cout << node->data << endl ;
  207.         display(node->r);
  208.  
  209.     }
  210.  
  211.     int getcounter(Node * curr)
  212.     {
  213.         return curr->counter ;
  214.     }
  215.  
  216.     int count_high_salary (Node * curr, int value)
  217.     {
  218.         if (curr == NULL)
  219.         {
  220.             return 0 ;
  221.         }
  222.         if (value == curr->data)
  223.         {
  224.             return count_high_salary(curr->r, value);
  225.         }
  226.  
  227.         else if (value > curr->data)
  228.         {
  229.             return count_high_salary(curr->r, value) ;
  230.         }
  231.         else
  232.         {
  233.             int temp = count_high_salary(curr->r, value) + getcounter(curr);
  234.             return count_high_salary(curr->l, value) + temp ;
  235.         }
  236.     }
  237.  
  238. public :
  239.  
  240.     Tree()
  241.     {
  242.         root = NULL ;
  243.     }
  244.  
  245.  
  246.     void insert(int value)
  247.     {
  248.         if (root == NULL)
  249.         {
  250.             Node * nn = new Node;
  251.             nn->data = value ;
  252.             root = nn ;
  253.         }
  254.         else
  255.         {
  256.             insert(value, root) ;
  257.         }
  258.         check_if_balanced(root) ;
  259.     }
  260.  
  261.     int count_high_salary (int value)
  262.     {
  263.         return count_high_salary(root,value) ;
  264.     }
  265. };
  266.  
  267. int main ()
  268. {
  269.     Tree ob ;
  270.  
  271.     int n, x, Q ;
  272.  
  273.  
  274.     cin >> n ;
  275.  
  276.     for (int i = 0 ; i < n ; i++)
  277.     {
  278.         cin >> x ;
  279.         ob.insert(x);
  280.     }
  281.  
  282.     cin >> Q ;
  283.     int a[Q][2];
  284.  
  285.     cout<< "------------" << endl ;
  286.  
  287.  
  288.     for (int i = 0 ; i < Q ; i++)
  289.     {
  290.         cin >> a[i][0];
  291.         cin >> a[i][1];
  292.     }
  293.  
  294.     for (int i = 0 ; i < Q ; i++)
  295.     {
  296.         if (a[i][0] == 1)
  297.         {
  298.             ob.insert(a[i][1]);
  299.         }
  300.         else
  301.         {
  302.             cout << ob.count_high_salary(a[i][1]) << endl ;
  303.         }
  304.  
  305.     }
  306. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top