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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
| #include <iostream>
#include <locale>
#include <fstream>
#include <string>
using namespace std;
const int n = 2;
const int nn = 4;
struct item;
struct page // страница дерева
{
short m; // кол-во элементов
page* p0; // адрес левого потомка
item* e[nn]; // указатели на элементы страницы
};
struct item // элемент страницы
{
long key; // данные
page* p; // указатель к потомку
long count; // количество одинаковых данных
};
void sort(page*& a, int m) // сортировка элементов по возрастанию данных
{
int c_swap;
do
{
c_swap = 0;
for (int i = 0; i < (m - 1); i++)
{
if ((*a).e[i]->key > (*a).e[i + 1]->key)
{
swap((*a).e[i], (*a).e[i + 1]); // перемещение данных
c_swap++; // произведено перемещение
}// проходим по всем элементам и выстраиваем данные по возрастанию (m-1 т.к сравниваем данные текущего элемента со следующим)
}
} while (c_swap > 0); // сортировка пузырьком, пока выполняются перемещения выполнять сортировку
}
void print_tree(page* a) // вывод дерева
{
if (a != NULL)
{
for (int i = 0; i < (*a).m; i++)
{
cout << (*a).e[i]->key << " ";
}
cout << endl;
print_tree((*a).p0);
for (int i = 0; i < ((*a).m); i++)
{
print_tree((*a).e[i]->p);
}
}
}
void Split(page*& a, page*& branch) // a - лист, в который будет перенесён медианный элемент, brnch - лист который требует расщепление
{
int mean = (*branch).m / 2 + 1; // середина
item* mid = (*branch).e[mean - 1]; // серединный элемент
(*a).e[(*a).m] = mid; // перемещаем элемент (m+1 сделаем в конце)
page* new_right = new(page); // создаём правую ветку для перемещённого элемента
(*new_right).p0 = (*mid).p;
int j = 0;
(*new_right).m = 0;
for (int i = mean; i < (*branch).m; i++) // идём от медианного элемента + 1 (относительно массива где счёт идёт от 0) до конца страницы
{
(*new_right).e[j] = (*branch).e[i]; // переносим указатели из переполненного листа в новый (элементы которые больше медианного)
(*new_right).m += 1; // добавили элемент
j++;
}
(*a).e[(*a).m]->p = new_right; // перемещаем указатель на новое правое поддерево
for (int i = mean - 1; i < nn + 1; i++)
{
(*branch).e[i] = NULL;
(*branch).m -= 1;
}
(*a).m += 1; // добавлен элемент после расщепления
}
void Split_root(page*& a) // расщепление корня
{
int mean = ((*a).m / 2) + 1;
item* mid = (*a).e[mean - 1]; // для начала находим медианный элемент
page* new_root = new(page); // создаём новый корень
(*new_root).p0 = a; // делаем адресацию на изначальный корень (левая ветвь)
(*new_root).e[0] = mid; // определяем нулевой элемент в новом корне
(*new_root).m = 1; // кол-во элементов в корне = 1
page* new_right = new(page); // создаём новую правую ветку для нулевого элемента корня
(*new_right).p0 = (*new_root).e[0]->p; // переопределяем указатель по условию расщепления
(*new_right).m = 0;
int j = 0;
for (int i = mean; i < (*a).m; i++) // идём от медианного элемента + 1 (относительно массива где счёт идёт от 0) до конца страницы
{
(*new_right).e[j] = (*a).e[i]; // переносим указатели и данные элементов из корня в правое поддерево, справа, относительно медианного элемента
(*new_right).m += 1; // добавили элемент
j++;
}
(*new_root).e[0]->p = new_right; // перемещаем указатель на новое правое поддерево
for (int i = mean - 1; i < nn + 1; i++) // очищаем старый корень от перемещённых элементов
{
(*a).e[i] = NULL; // обнуляем элементы
(*a).m -= 1; // убрали элемент
}
a = new_root;
}
void read_list(page*& a, int D, bool root = false) // загрузка новых данных, root - определение, является ли данная страница корнем, запуск происходит с true, далее в рекурсии присваивается false
{
if (a == NULL) // если нет корня, создаём
{
a = new(page); // создание новой страницы
(*a).p0 = NULL; // зануляем адреса к следующим страницам
(*a).e[0] = new(item); // создание нового элемента
(*a).e[0]->key = D; // добавляем информацию
(*a).e[0]->count = 1; // кол-во данной информации равно 1
(*a).e[0]->p = NULL;
for (int i = 1; i <= 3; i++)
{
(*a).e[i] = NULL; // заполнение остальных точек для элеметнов нулями
}
(*a).m = 1; // добавили 1 элемент в страницу
}
else // если же страница существует нужно провести работу по проверке на нужную страницу, если страница та, тогда, на идентичность данных, заполнению, сортировке и проверке на переполнение и при необходимости расщепление
{
short flag_next = 0;
/*
если флаг:
= 0 - дошли до конца, но адреса на потомка нет, вставить на эту страницу
= 1 - нашли элемент с данными больше чем D, но адреса на новую страницу нет, вставить нужно в эту страницу, остановить цикл
= 2 - Нашли потомка, к которому нужно перейти и он не самый правый
= 3 - Нашли потомка - самый правый
*/
int i = 0; // для определения номера элемента, к потомку которого нужно перейти в случае 4
while (i < (*a).m && flag_next == 0) // пока не дошли до конца и не изменился флаг
{
if ((*a).e[i]->key > D) // если нашли элемент с данными больше чем D проверяем, есть ли ссылку на следующую страницу у ПРЕДЫДУЩЕГО элемента(или, если это нулевой элемент, проверяем p0)
{
if (i == 0 && (*a).p0 == NULL) flag_next = 1; // если D меньше данных нулевого элемента, тогда проверяем есть ли самый левый потомок
else if (i == 0 && (*a).p0 != NULL) flag_next = 2;
else if ((*a).e[i - 1]->p == NULL) flag_next = 1; // если же D меньше данных не нулевого элемента, тогда проверяем есть ли потомок у ПРЕДЫДУЩЕГО элемента
else flag_next = 2;
}
i++; // переход к следующему элементу
}
i--; // уменьшаем i на 1 т.к оно на 1 больше чем надо, если не доходим до конца
// Выполнение флагов
if (flag_next == 2) // описано в флаге flag_next
{
if (i != 0) read_list((*a).e[i - 1]->p, D); // если мы остановились не на 0 элементе то переходим по указателю у предыдущего элемента
else read_list((*a).p0, D); // если остановились на нулевом, тогда переходим по указателю из страницы (p0)
}
if (flag_next == 0) // если дошли до конца, нужно проверить есть ли указателю на правого потомка
{// i а не i - 1 т.к мы дошли до конца и i не прибавилось
if ((*a).e[i]->p != NULL) // нужно двойное if т.к если мы остановимся на нулевом элементе с флагом 1, тогда уйдём за границы массива в данном условии
{
flag_next = 3; // всё-таки идём в глубь, значит изменяем флаг
read_list((*a).e[i]->p, D);
}
}
if (flag_next > 1) // если флаг 2 или 3,значит данные находятся ниже, нужно произвести проверку на переполнение (проверка только i-1 элемента т.к именно туда он отправился)
{
if (flag_next == 2 ) i -= 1; // если мы нашли не последнего потомка, значит при работе с i мы использовали i - 1, уменьшаем на 1, чтобы работать с i
// ЕСЛИ мы были на 0 элементе, то flag_next = -1, значит данные были отправлены в левого потомка
if (i == -1)
{
if ((*a).p0->m <= nn) return; // если переполнения не случилось значит заканчиваем действия на данной итерации
else
{
Split(a, (*a).p0);
sort(a, (*a).m);
if (root && (*a).m > nn) Split_root(a);
return;
}
}
else // если же fn != -1 значит данные пошли к потомку по указателю элемента с индексом i
{
if ((*a).e[i]->p->m <= nn) return; // если переполнения не случилось значит заканчиваем действия на данной итерации
else
{
Split(a, (*a).e[i]->p);
sort(a, (*a).m);
if (root && (*a).m > nn) Split_root(a);// если элемент был перемещён в корень нужно выполнить ещё расщепление корня
return;
}
}
}
// далее, если нашли нужную страницу выполняем действия:
// Поиск одинаковых данных
bool flag = false; // флаг нахождения одинаковых данных
for (int i = 0; (i < (*a).m) && (flag == false); i++) // поиск одинаковых данных
{
if (D == (*a).e[i]->key)
{
(*a).e[i]->count += 1; // если нашли идентичные данные, тогда увеличиваем количество данных на 1
flag = true; // если нашли одинаковые данные дальнейшая проверка не нужна
}
}
// Вставка
if (flag == false) // если не нашли одинаковые данные выполняем вставку
{
(*a).e[(*a).m] = new(item);
(*a).e[(*a).m]->key = D;
(*a).e[(*a).m]->count = 1;
(*a).e[(*a).m]->p = NULL;
(*a).m += 1;
sort(a, (*a).m); // нужно переместить новые данные с учётом возрастания
}
// Проверка корня на переполнение
if (root && (*a).m > nn) // если мы в корне, то должны выполнить проверку на переполнение
{// если переполнение в корне нужно выполнить его расщепление
Split_root(a);
}
}
}
void Delete_el(page*& a, item*& el) // a - лист в котором находится элемент с ключом который нужно удалить, el - элемент в котором находится ключ, который нужно удалить
{
if ((*el).p == NULL) // если страница - лист
{
}
else // если страница не является листом
{
}
}
int main()
{
setlocale(0, "");
page* a = NULL;
int D;
cout << "Введите данные для заполнения Б-дерева, 0 - конец ввода:\n";
cin >> D; // данные загружаемые в дерево
while (D != 0)
{
read_list(a, D, true);
print_tree(a);
cout << endl;
cin >> D;
}
} |
(
