Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct node {
- int data, size;
- node *left, *right;
- node(int x){
- data = x;
- size = 1;
- left = NULL;
- right = NULL;
- }
- };
- struct BSTree {
- node *root;
- BSTree(){
- root = NULL;
- }
- void insert(int x){
- root = insert(root, x);
- }
- int findMed(){
- if(root == NULL){
- return 0;
- }
- if(root -> size % 2 == 0){
- return (findIndex(root, root -> size / 2) + findIndex(root, root -> size / 2 + 1)) / 2;
- } else {
- return findIndex(root, (root -> size + 1) / 2);
- }
- }
- private:
- node *insert(node *root, int x){
- if(root == NULL){
- return new node(x);
- }
- ++(root -> size);
- if(x < root -> data){
- root -> left = insert(root -> left, x);
- } else {
- root -> right = insert(root -> right, x);
- }
- return root;
- }
- int findIndex(node *root, int i){
- if(root == NULL){
- return 0;
- }
- int leftSz = (root -> left == NULL) ? 0 : root -> left -> size;
- if(leftSz + 1 == i){
- return root -> data;
- }
- if(i <= leftSz){
- return findIndex(root -> left, i);
- } else {
- return findIndex(root -> right, i - leftSz - 1);
- }
- }
- };
- int main(){
- int nNumber;
- scanf("%d", &nNumber);
- BSTree bst = BSTree();
- for(int i = 1; i <= nNumber; ++i){
- int x;
- scanf("%d", &x);
- bst.insert(x);
- cout << bst.findMed() << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement