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
|
#include"../Seminar08/tree-utils.h"
#include<optional>
#include<vector>
#include<assert.h>
#include<algorithm>
template<class T>
std::optional<T> getMax(const Tree<T>* t) {
if (t == nullptr)
return {}; // Няма стойност
T res = t->data;
std::optional<T> left = getMax(t->left);
std::optional<T> right = getMax(t->right);
if (left.has_value())
res = std::max(res, left.value());
if (right.has_value())
res = std::max(res, right.value());
return res;
}
bool isBSTRec(const Tree<int>* t, int min, int max) {
if (t == nullptr)
return true;
if (t->data < min || t->data > max)
return false;
return isBSTRec(t->left, min, t->data) && isBSTRec(t->right, t->data, max);
}
bool isBST(const Tree<int>* t) {
return isBSTRec(t, INT_MIN, INT_MAX);
}
template<class T>
Tree<T>* buildFromRec(const std::vector<T>& v, int start, int end) {
if (end < start)
return nullptr;
int mid = (end - start) / 2 + start;
return new Tree<T>(v[mid], buildFromRec(v, start, mid - 1), buildFromRec(v, mid + 1, end));
}
template<class T>
Tree<T>* buildFrom(const std::vector<T>& v) {
return buildFromRec(v, 0, v.size() - 1);
}
template<class T>
bool isSameTree(const Tree<T>* fst, const Tree<T>* snd) {
if (!fst && !snd)
return true;
if ((fst && !snd) || (!fst && snd) || fst->data != snd->data)
return false;
return isSameTree(fst->left, snd->left) && isSameTree(fst->right, snd->right);
}
template<class T>
Tree<T>* clone(const Tree<T>* t) {
if (!t)
return nullptr;
return new Tree<T>(t->data, clone(t->left), clone(t->right));
}
template<class T>
void rotateLeft(Tree<T>*& root) {
assert(root->right != nullptr);
Tree<T>* originalRight = root->right;
root->right = originalRight->left;
originalRight->left = root;
root = originalRight;
}
template<class T>
void rotateRight(Tree<T>*& root) {
assert(root->left != nullptr);
Tree<T>* originalLeft = root->left;
root->left = originalLeft->right;
originalLeft->right = root;
root = originalLeft;
}
void rotationsTests() {
std::vector<int> v;
for (size_t i = 0; i < 100; i++)
v.push_back(rand() % 100);
std::sort(v.begin(), v.end());
Tree<int>* example = buildFrom(v);
Tree<int>* exampleClone = clone(example);
// Тестваме лява ротация:
// Тука не правя проверки за nullptr понеже не е това целта на този пример
Tree<int>* alpha = clone(example->left);
Tree<int>* beta = clone(example->right->left);
Tree<int>* gamma = clone(example->right->right);
rotateLeft(example);
assert(isSameTree(alpha, example->left->left));
assert(isSameTree(beta, example->left->right));
assert(isSameTree(gamma, example->right));
freeTree(alpha); freeTree(beta); freeTree(gamma);
// Тествам дясна ротация
alpha = clone(example->left->left);
beta = clone(example->left->right);
gamma = clone(example->right);
rotateRight(example);
assert(isSameTree(alpha, example->left));
assert(isSameTree(beta, example->right->left));
assert(isSameTree(gamma, example->right->right));
freeTree(alpha); freeTree(beta); freeTree(gamma);
// Лявата ротация е симетрична на дясната следователно като направим лява + дясна трябва да остане същото дърво
assert(isSameTree(example, exampleClone));
freeTree(example);
freeTree(exampleClone);
}
int main() {
rotationsTests();
}
|
