mickypinata

SMMR-T246: Median

Jun 13th, 2021
611
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node {
  5.     int data, size;
  6.     node *left, *right;
  7.     node(int x){
  8.         data = x;
  9.         size = 1;
  10.         left = NULL;
  11.         right = NULL;
  12.     }
  13. };
  14.  
  15. struct BSTree {
  16.     node *root;
  17.     BSTree(){
  18.         root = NULL;
  19.     }
  20.     void insert(int x){
  21.         root = insert(root, x);
  22.     }
  23.     int findMed(){
  24.         if(root == NULL){
  25.             return 0;
  26.         }
  27.         if(root -> size % 2 == 0){
  28.             return (findIndex(root, root -> size / 2) + findIndex(root, root -> size / 2 + 1)) / 2;
  29.         } else {
  30.             return findIndex(root, (root -> size + 1) / 2);
  31.         }
  32.     }
  33. private:
  34.     node *insert(node *root, int x){
  35.         if(root == NULL){
  36.             return new node(x);
  37.         }
  38.         ++(root -> size);
  39.         if(x < root -> data){
  40.             root -> left = insert(root -> left, x);
  41.         } else {
  42.             root -> right = insert(root -> right, x);
  43.         }
  44.         return root;
  45.     }
  46.     int findIndex(node *root, int i){
  47.         if(root == NULL){
  48.             return 0;
  49.         }
  50.         int leftSz = (root -> left == NULL) ? 0 : root -> left -> size;
  51.         if(leftSz + 1 == i){
  52.             return root -> data;
  53.         }
  54.         if(i <= leftSz){
  55.             return findIndex(root -> left, i);
  56.         } else {
  57.             return findIndex(root -> right, i - leftSz - 1);
  58.         }
  59.     }
  60. };
  61.  
  62. int main(){
  63.  
  64.     int nNumber;
  65.     scanf("%d", &nNumber);
  66.     BSTree bst = BSTree();
  67.     for(int i = 1; i <= nNumber; ++i){
  68.         int x;
  69.         scanf("%d", &x);
  70.         bst.insert(x);
  71.         cout << bst.findMed() << ' ';
  72.     }
  73.  
  74.     return 0;
  75. }
  76.  
RAW Paste Data