Создан заказ №3296491
4 ноября 2018
ФИО Басов Евгений Петрович Массив 1 2 3 4 5 6 7 8 9 10 11 12 Б А С О В Е Г Н И П Т Р Построить ИСДП
Как заказчик описал требования к работе:
Задание: сделать решение задач по базам данных за 2 дня, красиво оформить. Сколько стоит решение задач пишите точно.
Фрагмент выполненной работы:
ФИО:
Басов Евгений Петрович
Массив:
1 2 3 4 5 6 7 8 9 10 11 12
Б А С О В Е Г Н И П Т Р
Построить ИСДП, используя в качестве массива набор из 12 букв своих фамилии, имени, отчества.
Решение:
Идеально сбалансированное дерево поиска (ИСДП) – дерево, в котором для каждой его вершины размеры левого и правого поддеревьев отличаются не более чем на 1.
Отсортируем исходный массив данных:
1 2 3 4 5 6 7 8 9 10 11 12
А Б В Г Е И Н О П Р С Т
Построение ИСДП:
В качестве корня дерева берется средний элемент массива (Н).
Далее ИСДП строится с помощью следующих шагов:
- из элементов массива, расположенных левее среднего элемента, строится левое поддерево с nl = n DIV 2 вершинами тем же способом.
- из элементов массива, расположенных правее среднего элемента, строится правое поддерево с nr = n-nl-1 вершинами тем же способом.
Рисунок SEQ Рисунок \* ARABIC 1 - ИСПД
Построить СДП, используя в качестве массива набор из 12 букв своих фамилии, имени, отчества.
При решении многих типов задач объем данных заранее неизвестен, но необходима такая структура данных, для которой достаточно быстро выполняются операции поиска, добавления и удаления вершин. (работа была выполнена специалистами Автор 24) Одно из решений этой проблемы построение случайного дерева поиска (СДП).
Алгоритм добавления вершины в СДП заключается в следующем. Если дерево пустое, то создается корневая вершина, в которую записываются данные. В противном случае вершина добавляется к левому или правому поддереву в зависимости от результата сравнения с данными в текущей вершине.
1 2 3 4 5 6 7 8 9 10 11 12
Б А С О В Е Г Н И П Т Р
Рисунок SEQ Рисунок \* ARABIC 2 – СДП
Построить АВЛ-дерево, используя набор из 12 букв своих фамилии, имени, отчества.
1 2 3 4 5 6 7 8 9 10 11 12
Б А С О В Е Г Н И П Т Р
Дерево поиска называется сбалансированным по высоте, или АВЛ – деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.
Добавление новой вершины в АВЛ-дерево происходит следующим образом. Вначале добавим новую вершину в дерево так же как в случайное дерево поиска (проход по пути поиска до нужного места). Затем, двигаясь назад по пути поиска от новой вершины к корню дерева, будем искать вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). Если такая вершина найдена, то изменим структуру дерева для восстановления баланса с помощью процедур поворотов.
Рисунок SEQ Рисунок \* ARABIC 3 – АВЛ-дерево
Построить ДБ-дерево, используя набор из 12 букв своих фамилии, имени, отчества.
Построение двоичного Б-дерева происходит путем д..Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
5 ноября 2018
Заказ завершен, заказчик получил финальный файл с работой
5
ФИО
Басов Евгений Петрович
Массив
1 2 3 4 5 6 7 8 9 10 11 12
Б А С О В Е Г Н И П Т Р
Построить ИСДП.jpg
2019-05-15 18:50
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Хороший автор, советую. Многие моменты в работе автор объяснил. Выполняет все в срок.
Хочешь такую же работу?
300 ₽
