[C++] Treap.

/*
제    목 : 데이터구조 10주차 과제 Treap을 이용한 코로나 확진자 정보 구현
기    능 : 코로나 확진자 정보를 추가 또는 삭제
파일이름 : 201622821_김영진_데이터구조_10주차과제
수정날짜 : 2020-06-04
작 성 자 : 김영진
*/
#include <iostream>
#include <cstdlib>
using namespace std;

typedef double KeyType;

class TreapNode {
public:
    KeyType death_rate;
    string country;
    int dead;
    int infected;
    int priority;
    int size;
    TreapNode* left;
    TreapNode* right;

    TreapNode(const KeyType _death_rate, const string _country, int _dead, int _infected)
        :death_rate(_death_rate),
        country(_country), 
        dead(_dead), 
        infected(_infected), 
        priority(rand()), 
        size(1), 
        left(NULL), 
        right(NULL)
    {}
    void setLeft(TreapNode* newLeft) {
        left = newLeft;
        calcSize();
        return;
    }
    void setRight(TreapNode* newRight) {
        right = newRight;
        calcSize();
        return;
    }
    void calcSize(void) {
        size = 1;
        size = (left != NULL) ? size + left->size : size;
        size = (right != NULL) ? size + right->size : size;
        return;
    }
};

typedef pair<TreapNode*, TreapNode*> TreapNodePair;

TreapNodePair split(TreapNode* root, KeyType _death_rate) {
    if (root == NULL) {
        return TreapNodePair(NULL, NULL);
    }
    if (root->death_rate < _death_rate) {
        TreapNodePair rs = split(root->right, _death_rate);
        root->setRight(rs.first);
        return TreapNodePair(root, rs.second);
    }
    else {
        TreapNodePair ls = split(root->left, _death_rate);
        root->setLeft(ls.second);
        return TreapNodePair(ls.first, root);
    }
}

TreapNode* insert(TreapNode* root, TreapNode* new_node) {
    if (root == NULL) {
        return new_node;
    }
    if (root->priority > new_node->priority) {
        if (root->death_rate > new_node->death_rate) {
            root->setLeft(insert(root->left, new_node));
        }
        else {
            root->setRight(insert(root->right, new_node));
        }
        return root;
    }
    else {
        TreapNodePair splited = split(root, new_node->death_rate);
        new_node->setLeft(splited.first);
        new_node->setRight(splited.second);
        return new_node;
    }
}

TreapNode* merge(TreapNode* t1, TreapNode* t2) {
    if (t1 == NULL) {
        return t2;
    }
    if (t2 == NULL) {
        return t1;
    }
    if (t1->priority < t2->priority) {
        t2->setLeft(merge(t1, t2->left));
        return t2;
    }
    else {
        t1->setRight(merge(t1->right, t2));
        return t1;
    }
}

TreapNode* erase(TreapNode* root, KeyType _death_rate) {
    if (root == NULL) {
        return root;
    }
    if (root->death_rate == _death_rate) {
        TreapNode* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    else if (root->death_rate > _death_rate) {
        root->setLeft(erase(root->left, _death_rate));
        return root;
    }
    else {
        root->setRight(erase(root->right, _death_rate));
        return root;
    }
}

void inorder(TreapNode* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << fixed;
        cout.precision(1);
        cout << root->country << "\t" 
            << root->infected << "\t" 
            << root->dead << "\t" 
            << root->death_rate << " %" 
            << endl;
        inorder(root->right);
    }
    return;
}

int main(void) {
    TreapNode* root = NULL;
    int num = 0;
    int m_dead = 0, m_infected = 0;
    double m_death_rate = 0.0;
    string m_country;

    root = insert(root, new TreapNode(5.8, "America", 106120, 1830066));
    root = insert(root, new TreapNode(5.6, "Brazil", 31199, 555383));
    root = insert(root, new TreapNode(1.2, "Russia", 5037, 423741));
    root = insert(root, new TreapNode(14.2, "England", 39369, 277985));
    root = insert(root, new TreapNode(11.3, "Spain", 27127, 239932));
    root = insert(root, new TreapNode(14.4, "Italy", 33530, 233515));
    root = insert(root, new TreapNode(2.8, "India", 5598, 198706));
    root = insert(root, new TreapNode(4.7, "Germany", 8563, 183879));
    root = insert(root, new TreapNode(2.7, "Peru", 4634, 170039));
    root = insert(root, new TreapNode(2.8, "Turkey", 4585, 165555));


    while (1) {
        cout << "(0)Exit\t\t(1)Insert\t(2)Print\t(3)Erase" << endl
            << "입력:";
        cin >> num;
        switch (num) {
        case 0:
            return 0;
        case 1:
            cout << "국가명:";
            cin >> m_country;
            cout << "사망자:";
            cin >> m_dead;
            cout << "확진자:";
            cin >> m_infected;
            m_death_rate = ((double)m_dead / m_infected) * 100;
            root = insert(root, new TreapNode(m_death_rate, m_country, m_infected, m_dead));
            break;
        case 2:
            cout << "국가명\t확진자\t사망자\t사망률" << endl;
            inorder(root);
            cout << endl;
            break;
        case 3:
            cout << "제거할 국가의 사망률 입력:";
            cin >> m_death_rate;
            root = erase(root, m_death_rate);
            break;
        default:
            cout << "잘못된 접근입니다." << endl;
            break;
        }
    }
}