코딩의 숲
2020. 9. 7. 22:57
HEAP+TREE를 합친 TREAP
트리가 한쪽으로 쏠리는것을 막기위해 우선순위를 부여함
이것을이용해 나라간 코로나 표를 만들어봄
" target="_blank" rel="noopener" data-mce-href="http://
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
#include<iostream>
#include<string>
using namespace std;
int counter = 0;
bool on = false;
class node//1.노드 만들기
{
public:
node(const string& country = "", const double& death_percent = 0)
{
this->country = country;
this->death_percent = death_percent;
left = NULL;
right = NULL;
}
node* left;
node* right;
string country;
double death_percent;
};
class manager//2.노드 관리
{
public:
node* leftrotation(node* x)
{
node* y = x->right, * T2 = y->left;
y->left = x;
x->right = T2;
return y;
}
node* rightrotation(node* y)
{
node* x = y->left, * T2 = x->right;
x->right = y;
y->left = T2;
return x;
}
node* search(node* root, const string& country)
{
if (root == NULL || root->country == country)
{
on = true;
return root;
}
if (root->country > country)
{
if (!on)
{
cout << root->country << "를 거쳤습니다." << endl;
counter++;
}
return search(root->left, country);
}
if (root->country <= country)
{
if (!on)
{
cout << root->country << "를 거쳤습니다." << endl;
counter++;
}
return search(root->right, country);
}
}
node* insert(node* root, const string& country, const double& death_percent)
{
if (root == NULL)
{
return new node(country, death_percent);
}
if (root->country <= country)
{
root->right = insert(root->right, country, death_percent);
if (root->death_percent < death_percent)
{
root = leftrotation(root);
}
}
else if (root->country > country)
{
root->left = insert(root->left, country, death_percent);
if (root->death_percent < death_percent)
{
root = rightrotation(root);
}
}
return root;
}
node* deletenode(node* root)
{
if (root == NULL)
{
return root;
}
if (root->left == NULL)
{
node* root_ = root->right;
delete root;
root = root_;
}
else if (root->right == NULL)
{
node* root_ = root->left;
delete root;
root = root_;
}
else if (root->left->death_percent >= root->right->death_percent)
{
root = rightrotation(root);
root->right = deletenode(root->right);
}
else
{
root = leftrotation(root);
root->left = deletenode(root->left);
}
return root;
}
};
int main()
{
manager manager;
node* root = NULL;
string name = "";
double percent = 0;
int input = 0;
root = manager.insert(root, "미국", 1.2);
root = manager.insert(root, "중국", 13.2);
root = manager.insert(root, "일본", 1.3);
root = manager.insert(root, "프랑스", 1.211);
root = manager.insert(root, "영국", 14.2);
root = manager.insert(root, "러시아", 16.3);
while (true)
{
counter = 0;
cout << "1번은 나라추가 2번은 나라 검색 3번은 가장사망률이높은 국가 삭제입니다 4번은 나가기 입니다" << endl;
cin >> input;
if (input == 1)
{
cout << "나라이름,사망률순으로 적어주세요" << endl;
cin >> name >> percent;
root = manager.insert(root, name, percent);
}
else if (input == 2)
{
on = false;
cout << "나라이름을 적어주세요" << endl;
cin >> name;
cout << endl;
cout << "\n\n" << manager.search(root, name)->country << " 의 사망률은 " << manager.search(root, name)->death_percent << endl;
cout << counter << "번거쳤습니다\n\n";
}
else if (input == 3)
{
root = manager.deletenode(root);
cout << "가장사망률이높은 국가가삭제되었습니다" << endl;
}
else
{
while (root != NULL)
{
root = manager.deletenode(root);
}
cout << "프로그램 종료" << endl;
break;
}
}
return 0;
}
|
cs |