Структура данных Scapegoat Tree - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Структура данных Scapegoat Tree, слайд №1

Структура данных Scapegoat Tree, слайд №2

Структура данных Scapegoat Tree, слайд №3

Структура данных Scapegoat Tree, слайд №4

Структура данных Scapegoat Tree, слайд №5

Структура данных Scapegoat Tree, слайд №6

Структура данных Scapegoat Tree, слайд №7

Структура данных Scapegoat Tree, слайд №8

Структура данных Scapegoat Tree, слайд №9

Структура данных Scapegoat Tree, слайд №10

Структура данных Scapegoat Tree, слайд №11

Структура данных Scapegoat Tree, слайд №12

Структура данных Scapegoat Tree, слайд №13

Структура данных Scapegoat Tree, слайд №14

Структура данных Scapegoat Tree, слайд №15

Структура данных Scapegoat Tree, слайд №16

Структура данных Scapegoat Tree, слайд №17

Структура данных Scapegoat Tree, слайд №18

Структура данных Scapegoat Tree, слайд №19

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Структура данных Scapegoat Tree. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Scapegoat Tree Выполнил Димов А.А. ИМ15-06Б Руководитель Олейников Б.В.

Слайд 2

Описание слайда:

Разработана Arne Andersson, Igal Galperin, Ronald L. Rivest в 1962г.

Слайд 3

Описание слайда:

Scapegoat tree – структура данных, представляющее из себя самобалансирующееся бинарное дерево поиска. Scapegoat tree – структура данных, представляющее из себя самобалансирующееся бинарное дерево поиска. Операции поиска, вставки и удаления работают за при этом скорость одной операции может быть улучшена за счет другой

Слайд 4

Описание слайда:

Понятия, необходимые для работы с данным деревом: Понятия, необходимые для работы с данным деревом: ��−дерево ��[��]−корень дерева �� [��],��ℎ��[��]−левые и правый "сын" вершины ��ℎ��(��)− брат вершины (имеет общего родителя) ��ℎ(��)−глубина вершины (расстояние от вершины до корня) ℎ��ℎ��(��)−глубина дерева �� (��)−вес вершины �� (кол−во всех ее дочерних вершины+1) ��[��]−размер дерева �� (вес корня) ��_size[T] – максимальный размер дерева T.

Слайд 5

Описание слайда:

При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить Степень сбалансированности Коэффициэнт α — это число в диапазоне от [0.5; 1), определяющее требуемую степень качества балансировки дерева. Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен α * size(x) и вес ей правого сына меньше либо равен α * size(x).

Слайд 6

Описание слайда:

Примеры

Слайд 7

Описание слайда:

Плюсы и минусы Scapegoat дерева Плюсы Скорость одних операций возможно улучшить за счет других операций. Scapegoat tree работает быстрее, чем красно-черное дерево и декартово. Требуется меньше памяти (не надо хранить информацию для балансировки). Настройки скорости меняются в процессе выполнения. Не требуется перебалансировать дерево при поиске.

Слайд 8

Описание слайда:

Минусы Минусы В худшем случае операции модификации дерева могут занять ��(��) времени. В случае неправильного выбора парметра ��ℎ�� часто используемые операции будут работать долго, а редко используемые – быстро. При этом дерево будет уступать остальным по скорости

Слайд 9

Описание слайда:

Поиск Данная операция стандратна для двоичного дерева поиска. Необходимо пройти от корня, сравнивая каждую вершину с искомым значением, если найдено – возрват значения, иначе, если значение в вершине меньше, то рекурсивно ищем в левом поддереве, если больше – в правом. Сложность операции зависит от ��ℎ��: O()

Слайд 10

Описание слайда:

Вставка Начинается вставка нового элемента в Scapegoat-дерево классически: поиском ищем место, куда бы подвесить новую вершину и подвешиваем. Легко понять, что это действие могло нарушить α-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название структуре данных: мы ищем «козла отпущения» (Scapegoat-вершину) — вершину, для которой потерян α-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, «козлом отпущения» стать не может — у неё ещё нет «детей», а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Если на этом пути встретится вершина, для которой критерий α-сбалансированности по весу нарушился — мы полностью перестраиваем соответствующее ей поддерево так, чтобы восстановить α-сбалансированность по весу.

Слайд 11

Описание слайда:

Перебалансировка Обходим всё поддерево Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получаем отсортированный список (свойство In-order обхода бинарного дерева поиска). Находим медиану на этом отрезке, подвешиваем её в качестве корня поддерева. Для «левого» и «правого» поддерева рекурсивно повторяем ту же операцию.

Слайд 12

Описание слайда:

if start > ends then if start > ends then begin result := Nil; exit; end; mid := ceil((start + ends) / 2.0); d := nodesList[mid]; p := Node.Create(d.key); leftNode := self.buildTreeFromSortedList(nodesList, start, mid-1); p.left := leftNode; rightNode := self.buildTreeFromSortedList(nodesList, mid+1, ends); p.right := rightNode; result := p;

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Удаление Удаляем вершину обычным удалением вершины бинарного дерева поиска (поиск, удаление, возможное переподвешивание детей). Далее проверяем выполнение условия size[T] < α * max_size[T] Если оно выполняется — дерево могло потерять α-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить max_size[T] = size[T]