Б-дерево

Red);return; }add_tree(ref node, parent, val);if (node.keys.Count == 2*t - 1) {int median = node.keys[t - 1];begin_animation_stage(Root);anim_select(node, Color.Blue);TreeItemnew_node = newTreeItem(node.parent, t - 1);for (inti = 0; i < t - 1; i++)new_node.keys[i] = node.keys[t + i];for (inti = 0; i <= t - 1; i++) {new_node.list[i] = node.list[t + i];if (new_node.list[i] != null)new_node.list[i].parent = new_node; }node.keys.RemoveRange(t - 1, node.keys.Count - (t - 1));node.list.RemoveRange(t, node.list.Count - t);TreeItemold_root = node; node = newTreeItem(null, t - 1);node.keys[0] = median;node.list[0] = old_root;old_root.parent = node;node.list[1] = new_node;new_node.parent = node;begin_animation_stage(Root);anim_select(old_root, Color.Blue);anim_arrow(old_root, new_node, Color.Blue);anim_select(new_node, Color.Red);anim_arrow(old_root, node, Color.Blue);anim_select(node, Color.Red);} }3) Обработчик нажатия на кнопку загрузки ключей из файлаprivatevoidbtLoadKeys_Click(object sender, EventArgs e) {if (openFileDialog.ShowDialog() == DialogResult.OK) {tbKeys.Text = File.ReadAllText(openFileDialog.FileName);} }4) Обработчик нажатия на кнопку создания дерева из ключейprivatevoidbtCreateTree_Click(object sender, EventArgs e) { Root = null;pbTree.Invalidate();start_animation();foreach (string s intbKeys.Lines)if (s.Length > 0) {int n = 0;if (int.TryParse(s, out n)) {insert_b_tree(ref Root, null, n); }else {MessageBox.Show("Непонятноечисло '" + s + "'"); Root = null;break; } }play_animation();pbTree.Invalidate(); }5) Обработчик нажатия на кнопку добавления ключаprivatevoidbtAdd_Click(object sender, EventArgs e) {int n = 0;if (int.TryParse(tbKey.Text, out n)) {start_animation();insert_b_tree(ref Root, null, n);play_animation();pbTree.Invalidate(); }else {MessageBox.Show("Непонятныйключ '" + tbKey.Text + "'");} }6) ФункцииотрисовкиБ-дереваианимациидобавленияключейprivatevoidDrawTree(Graphics g, Brush b, Pen p, Font f, PointF[] parent_coords,float h, float l, float r, TreeItem node, boolDrawLinks) {SizeF[] sizes = newSizeF[node.keys.Count];PointF[] coords = newPointF[node.list.Count];floattotw = 0.0f;floattoth = 0.0f;for (inti = 0; i < node.keys.Count; i++) { sizes[i] = g.MeasureString(node.keys[i].ToString(), f);if (sizes[i].Height > toth)toth = sizes[i].Height + 1.0f;totw += sizes[i].Width + 1.0f; }float w = r - l;floatstart_x = l + 0.5f * (w - totw);coords[0] = newPointF(start_x, h + toth);for (inti = 0; i < node.keys.Count; i++) {start_x += sizes[i].Width + 1.0f;coords[i + 1] = newPointF(start_x, h + toth); }node.x = l + 0.5f * w;node.y = h + 0.5f * toth;if (DrawLinks) {if (parent_coords != null) {float x1 = 0.0f;float y1 = 0.0f;for (inti = 0; i < node.parent.list.Count; i++)if (node.parent.list[i] == node) { x1 = parent_coords[i].X; y1 = parent_coords[i].Y;break; }float x2 = l + 0.5f * w;float y2 = h;g.DrawLine(p, x1, y1, x2, y2); } }else {for (inti = 0; i < node.keys.Count; i++) {float y = coords[i].Y - 0.5f - sizes[i].Height;g.DrawRectangle(p, coords[i].X, y, 1.0f + sizes[i].Width, 1.0f + sizes[i].Height);if (AnimationCadre >= 0) {AnimationFrame F = Animation[AnimationCadre];TreeItemRealNode = F.SavedToKeyMap[node];intidx = F.Selected.IndexOf(RealNode);if (idx >= 0) { Pen SelPen = new Pen(F.SelectedColors[idx], 3.0f);g.DrawRectangle(SelPen, coords[i].X, y, 1.0f + sizes[i].Width, 1.0f + sizes[i].Height); } }g.DrawString(node.keys[i].ToString(), f, b, coords[i].X + 0.5f, y); }if (AnimationCadre >= 0) {AnimationFrame F = Animation[AnimationCadre];if (F.ColorArrows.Count > 0)for (inti = 0; i < F.ColorArrows.Count; i++) {TreeItemFirstNode = F.KeyToSavedMap[F.BegArrows[i]];TreeItemLastNode = F.KeyToSavedMap[F.EndArrows[i]]; Pen SelPen = new Pen(F.ColorArrows[i], 3.0f);float x1 = FirstNode.x;float y1 = FirstNode.y;float x2 = LastNode.x;float y2 = LastNode.y;g.DrawLine(SelPen, x1, y1, x2, y2);double L = Math.Sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));double dx = (x2 - x1) / L;doubledy = (y2 - y1) / L;floatxs = (float)(x2 - dx * 15.0);floatys = (float)(y2 - dy * 15.0);float xs1 = (float)(xs - dy * 5.0);float ys1 = (float)(ys + dx * 5.0);float xs2 = (float)(xs + dy * 5.0);float ys2 = (float)(ys - dx * 5.0);g.DrawLine(SelPen, x2, y2, xs1, ys1);g.DrawLine(SelPen, x2, y2, xs2, ys2); } } }floatw_next = w / node.list.Count;for (inti = 0; i < node.list.Count; i++) {floatl_next = l + i * w_next;floatr_next = l_next + w_next;if (node.list[i] != null)DrawTree(g, b, p, f, coords, h + 2.0f * toth, l_next, r_next, node.list[i], DrawLinks); } }privatevoidpbTree_Paint(object sender, PaintEventArgs e) { Graphics g = e.Graphics;g.Clear(Color.White); Pen BlackPen = newPen(Color.Black);SolidBrushBlackBrush = newSolidBrush(Color.Black); Font F = newFont(FontFamily.GenericSansSerif, 7.0f);if (Root != null) {float w = pbTree.Width;TreeItem r = AnimationCadre < 0 ?Root : Animation[AnimationCadre].SavedRoot;DrawTree(g, BlackBrush, BlackPen, F, null, 0.0f, 0.0f, w, r, true);DrawTree(g, BlackBrush, BlackPen, F, null, 0.0f, 0.0f, w, r, false);} }7) Обработчик нажатия на кнопку удаления ключаprivatevoidbtDel_Click(object sender, EventArgs e) {int n = 0;if (int.TryParse(tbKey.Text, out n)) {start_animation();delete_b_item(ref Root, n);play_animation();pbTree.Invalidate(); }else {MessageBox.Show("Непонятныйключ '" + tbKey.Text + "'");} }8) Обработчик нажатия на кнопку поиска значения в Б-деревеprivatevoidbtSearch_Click(object sender, EventArgs e) {int n = 0;if (int.TryParse(tbKey.Text, out n)) {int index = 0;if (search(Root, n, ref index) != null)MessageBox.Show("Найдено!");elseMessageBox.Show("Ненайдено!"); }else {MessageBox.Show("Непонятныйключ '" + tbKey.Text + "'");} }9) Обработчик нажатия на кнопку повтора анимацииprivatevoidbtRepeatAnimation_Click(object sender, EventArgs e){play_animation(); }10) Функцияповтораанимацииprivatevoidplay_animation() {if (Animation != null && Animation.Count > 0){AnimationCadre = 0;AnimationTimer.Enabled = true; } }11) Функция для медленного отображения анимации при построении Б-дереваprivatevoidAnimationTimer_Tick(object sender, EventArgs e) {if (AnimationCadre >= 0) {pbTree.Invalidate();Application.DoEvents();AnimationCadre++;if (AnimationCadre == Animation.Count) {AnimationTimer.Enabled = false;AnimationCadre = (-1);Thread.Sleep(500);pbTree.Invalidate(); } } }2.4.2Реализованный интерфейсРазработанный интерфейс программы полностью соответствует составленному ранее макету. В интерфейсе реализована возможность загрузки ключей из файла и их отображения в поле "Ключи". Панель управления программы содержит список операций "Добавить", "Удалить", "Искать" и поле для ввода ключа. Также в интерфейсе реализована функция "Создать дерево из ключей" для построения Б-дерева по введенным или загруженным ключам, а также кнопки "С анимацией" и "Повтор анимации" для включения и отключения графической анимации при построении Б-дерева. Все действия пользователя отображаются в графическом интерфейсе, включая отображение дерева на соответствующем поле.2.5 Пример работыПосле запуска программы открывается главное окно программы. Далее у пользователя есть возможность либо загрузить из файла ключи для построения Б-дерева, либо поочерёдно добавлять каждый элемент с помощью соответствующего поля «Ключ» и кнопки «Добавить».Загрузив ключи из файла, заполнится соответствующее поле – список ключей для построения.При включённой опции «С анимацией» после нажатия на кнопку «Создать дерево из ключей», пользователю будет наглядно показано построение дерева.Добавление ключа в построенное Б-деревоУдаление ключа из Б-дереваПоиск элемента в Б-деревеЗаключениеВ ходе работы над курсовой были решены поставленные цели. А именно:Были изучены и проанализированы различные существующие алгоритмы поиска, вставки и удаления данных в Б-дереве. Анализ позволил выделить преимущества и недостатки каждого алгоритма.Был проведен сравнительный анализ эффективности рассмотренных алгоритмов с точки зрения времени работы, сложности и использования памяти.На основе анализа был выбран наиболее оптимальный алгоритм для реализации в рамках курсовой работы.Была реализована программа, включающая в себя функции:построения Б-дерева;поиска, вставки и удаления данных с использованием выбранного алгоритма;Разработан пользовательский интерфейс с возможностью графического отображения Б-дерева.Были проведены эксперименты для оценки практической эффективности выбранного алгоритма.Сделаны выводы о преимуществах и недостатках использованного алгоритма в рамках данной реализации.В итоге курсовая работа позволила усовершенствовать навыки разработки программного обеспечения, изучить алгоритмы работы с Б-деревами и применить полученные знания на практике.Полученный опыт и знания могут быть полезны при создании других программ в дальнейшем.Список литературыБейли Р. «Управление базами данных». - М.: Мир, 1990.Вагнер Р.А., Фотер Дж. «Структуры данных и алгоритмы». - М.: Мир, 1990.Гутагевич Ю.Б. «Структуры данных». - М.: Финансы и статистика, 1986.Деванур А.Р., Дэвисон Б.Д. «Структуры данных и алгоритмы». - М.: Мир, 1991.Демидович Б.П. и др. «Теория алгоритмов». - М.: Высшая школа, 1990.Кнусс А.Г. «Теория и технология структур данных». - М.: Финансы и статистика, 1983.Кнут Д. «Искусство программирования». - Т. 3. «Упорядочение и поиск». - М.: Мир, 1985.Хенри Ричард. «Структуры данных и алгоритмы». - М.: Вильямс, 2002.Вирский Ю.М. «Структуры и алгоритмы структур данных». - 2005.Нив Д., Олдер С. «Информатика». - Кембриджский университет, 2010.ConsensР. и 16 др. «Using B-trees with structural distribution». - Inf. Syst.,1995.Робертсон Н. «Элементарная теория баз данных». 2014.Шривастава Р.А. «Структуры данных». - 1993.Дойль Д.Э. «Язык Си». - 1994.Sedgewick R. «Algorithms». - 2014.Сквайр Джон. «Структуры данных и алгоритмы на С#». 2015.Роберт Седжвик. «Алгоритмы на С#». 2-е издание. 2010 г.Тим Кортней. «Основы программирования на С#». 2017 г.Брэд Миллер. «Программирование на С#». 2013 г.Эндрю Трупп. «Структуры данных и алгоритмы на С#». 2015 г.