/
1066_Root of AVL Tree (25).cpp
235 lines (207 loc) · 4.6 KB
/
1066_Root of AVL Tree (25).cpp
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#define _CRT_SECURE_NO_DEPRECATE
#define _SECURE_SCL 0
#pragma comment(linker, "/STACK:66777216")
#include <algorithm>
#include <string>
#include <complex>
#include <cassert>
#include <memory>
#include <set>
#include <stack>
#include <map>
#include <list>
#include <deque>
#include <numeric>
#include <cctype>
#include <cstddef>
#include <vector>
#include <queue>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#include <cstring>
#include <functional>
#include <bitset>
using namespace std;
#if defined(_MSC_VER) || defined(__BORLANDC__)
typedef unsigned __int64 uint64;
typedef signed __int64 int64;
#else
typedef unsigned long long uint64;
typedef signed long long int64;
#endif
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef pair<int64,int64> PLL;
typedef vector<int64> VL;
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define REP(i,n) FOR(i,1,(n))
#define REPT(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).size())
#define C(a) memset((a),0,sizeof(a))
#define IOS ios::sync_with_stdio(false)
const double pi = 3.1415926535897932384626433832795028841971;
const double EPS = 1E-9;
const int64 INF64 = (int64)1E18;
const int INF = 1000000000;
static inline bool get(int &v)
{
int s = 1, c;
while(!isdigit(c = getchar())&&c != '-')
{
if(c == EOF)
break ;
}
if(c == EOF) return 0;
if(c == '-') s = 0 , v = 0;
else v = c^48;
for(;isdigit(c = getchar());v = (v << 1) + (v << 3) + (c ^ 48));
v = (s ? v : -v);
return 1 ;
}
/*
AVLTree
四种操作
*/
class TreeNode
{
public:
TreeNode():lson(NULL),rson(NULL),height(0){}
int val;
int height;
TreeNode *lson, *rson;
};
class AVLTree
{
private:
TreeNode *root;
TreeNode* SingRotateLeft(TreeNode *&k2);//LL情况下旋转
TreeNode* SingRotateRight(TreeNode *&k2);//RR情况下旋转
TreeNode* DoubleRotateLR(TreeNode *&k3);//LR
TreeNode* DoubleRotateRL(TreeNode *&k3);//RL
void InsertNode(TreeNode *&node, int val);
int Height(TreeNode *node);
public:
AVLTree():root(NULL){}
void insert(int val);
int GetRootVal();
};
int AVLTree::Height(TreeNode *node)
{
if (node != NULL) return node->height;
return -1;
}
int AVLTree::GetRootVal()
{
return root->val;
}
void AVLTree::insert(int val)
{
InsertNode(root, val);
}
TreeNode* AVLTree::SingRotateLeft(TreeNode *&k2)
{
TreeNode *k1;
k1 = k2->lson;
k2->lson = k1->rson;
k1->rson = k2;
k2->height = max(Height(k2->lson), Height(k2->rson))+1;
k1->height = max(Height(k1->lson), Height(k1->rson))+1;
if (root == k2)
root = k1;
return k1;
}
TreeNode* AVLTree::SingRotateRight(TreeNode *&k2)
{
TreeNode *k1;
k1 = k2->rson;
k2->rson = k1->lson;
k1->lson = k2;
k2->height = max(Height(k2->lson), Height(k2->rson))+1;
k1->height = max(Height(k1->lson), Height(k1->rson))+1;
if (root == k2)
root = k1;
return k1;
}
TreeNode* AVLTree::DoubleRotateLR(TreeNode *&k3)
{
k3->lson = SingRotateRight(k3->lson);
return SingRotateLeft(k3);
}
TreeNode* AVLTree::DoubleRotateRL(TreeNode *&k3)
{
k3->rson = SingRotateLeft(k3->rson);
return SingRotateRight(k3);
}
void AVLTree::InsertNode(TreeNode *&node, int val)
{
if (node == NULL)
{
node = new TreeNode();
node->val = val;
if (NULL == root) root = node;
return ;
}
if (node->val > val)//插入到左子树
{
InsertNode(node->lson, val);
if (2 == Height(node->lson) - Height(node->rson))
{
if (val < node->lson->val) node = SingRotateLeft(node);
else node = DoubleRotateLR(node);
}
}
else if (node->val < val)//插入到右子树
{
InsertNode(node->rson, val);
if (2 == Height(node->rson) - Height(node->lson))
{
if (val > node->rson->val) node = SingRotateRight(node);
else node = DoubleRotateRL(node);
}
}
node->height = max(Height(node->lson), Height(node->rson))+1;
}
void run()
{
int n,e;
get(n);
AVLTree *tree = new AVLTree();
FOR(i, 1, n)
{
get(e);
tree->insert(e);
}
printf("%d\n", tree->GetRootVal());
}
int main()
{
#ifdef __DEBUG__
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
time_t st = clock();
#endif
run();
#ifdef __DEBUG__
printf( "\n=============\n");
printf("Time: %.2lf sec\n",(clock()-st)/double(CLOCKS_PER_SEC));
#endif
return 0;
}