🗊Презентация Структура данных Scapegoat Tree

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

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

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

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

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

Примеры

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

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

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

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

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

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;

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