31. Сбалансированные и несбалансированные деревья поиска

Дерево называется идеально сбалансированным, если все его уровни, за исключением, может быть, последнего, полностью заполнены. В бинарном дереве полностью заполненный уровень n содержит 2n узлов.

Если дерево поиска близко к сбалансированному, то даже в худшем случае за время порядка O(log₂n) в нем можно:

• Найти вершину с заданным значением или выяснить, что такой вершины нет.

• Включить новую вершину.

• Исключить вершину.

С реднее время выполнения этих операций будет также близким к O(log₂n), так как в идеально сбалансированном дереве при полностью заполненных уровнях на последнем уровне находится больше половины узлов дерева. Например, последовательность значений 4, 6, 2, 1, 5, 3, 7 дает следующее идеально сбалансированное дерево:

В этом дереве 7 узлов, на последнем уровне находится 4 узла. Если доступ к одному узлу требует 1 единицу времени, то до узла 4 можно добраться за 1 единицу времени, до 2 и 6 - за 2, до 1, 3, 5, 7 - за 3.

То есть в худшем случае требуется 3 единицы времени, в среднем: (1+2*2+3*4)/7 = 2.4 единицы времени.

Однако значения в последовательности могут идти и в другом порядке, что может привести к построению несбалансированного дерева. В худшем случае можно получить вырожденное дерево, подобное линейному списку. То есть для вырожденного дерева затраты на доступ к узлам в худшем случае имеют порядок O(n), в среднем - O(n/2). при работе с деревьями поиска больших размеров крайне желательно, чтобы они были близки к сбалансированным.Приведение уже существующего дерева к идеально сбалансированному - процесс сложный. Проще балансировать дерево в процессе его роста, т.е. после включения каждого узла. Однако требование идеальной сбалансированности делает и этот процесс достаточно сложным, способным затрагивать все узлы дерева.

31. АВЛ-деревья

В 1962 году советские математики Г.М.Адельсон-Вельский и Е.А.Ландис предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log₂n). При этом деревьям разрешается отклоняться от идеальной сбалансированности, но в небольшой степени, чтобы среднее время доступа к узлам было лишь немногим больше, чем в идеально сбалансированном дереве. Такие деревья называются АВЛ-деревьями.

Критерий сбалансированности АВЛ-дерева. Дерево называется сбалансированным тогда и только тогда, когда для каждого его узла высоты его левого и правого поддеревьев отличаются не более чем на единицу.

Примеры АВЛ-сбалансированных деревьев:

У ровень 0 Для каждого узла дерева можно определить показатель

Уровень 1 сбалансированности как разность между высотой правого и

Уровень 2 левого поддерева данного узла. Пусть h_R - высота правого

Уровень 3 поддерева, h_L - высота левого. Тогда показатель сбалансированности есть h_R - h_L.Если дерево АВЛ-сбалансировано, то для каждого узла выполняется: |h_R - h_L| £1.

Если хотя бы для одного узла дерева это не так, то дерево не является АВЛ-сбалансированным. После включения нового узла в АВЛ-дерево оно должно оставаться сбалансированным. Рассмотрим, в каких случаях потребуется балансировка дерева после включения узла. Во всех случаях будем указывать показатель сбалансированности корневого узла. Балансировка выполняется с помощью действий, называемых поворотами узлов.

Одинарный LL-поворот.

Выполняется, когда «перевес» идет по пути L-L Одинарный RR-поворот.

о т узла с нарушенной балансировкой Выполняется, когда «перевес» идет по пути R-R от узла с нарушенной балансировкой.

.

Одинарный LR-поворот.

Выполняется, когда «перевес» идет по пути L-R от

узла с нарушенной балансировкой.

Одинарный RL-поворот. Выполняется, когда «перевес» идет по пути R-L от узла с нарушенной балансировкой.

Правило балансировки:

При включении узлов повороты выполняются

для ближайшего узла к включенному с нарушенной балансировкой. То есть если после включения узла в дереве образуется несколько узлов с нарушенной балансировкой, поворот выполняется для того, который находится ниже (то есть ближе к включенному). После балансировки этого узла восстанавливается баланс и выше расположенных узлов. Ясно, что включение узла в АВЛ-дерево в среднем требует больше времени, чем включение в обычное дерево, так как может возникать необходимость проведения балансировки. Поэтому АВЛ-деревья целесообразно использовать в тех случаях, когда поиск узлов в дереве происходит гораздо чаще, чем включение и исключение улов.

31. Для представления графов можно использовать различные структуры данных.

Выбор структуры данных зависит от операторов, которые будут применяться к вершинам и ребрам графа.

Представления графов матрицей смежности. Одним из наиболее общих представлений графа G = (V, Е) является матрица смежности. Пусть G=(V, E), где V={v1, v2, …, vn}.Матрица смежности для графа G - это матрица А размера nхn со значениями булевого типа, где A[i, j] = true тогда и только тогда, когда существует ребро из вершины i в вершину j. Часто в матрицах смежности значение true заменяется на 1, а значение false - на 0.

Время доступа к элементам матрицы смежности зависит от размеров множества вершин и множества ребер.

Представление графа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо часто обрабатывать ребра между парами вершин.Для представления неориентированных графов можно применять матрицу смежности, если неориентированное ребро между вершинами v и w рассматривать как две ориентированных дуги от вершины v к вершине w и от вершины w к вершине v. Очевидно, что матрица смежности для неориентированного графа симметрична. Представления графов матрицей инциденций. Если количество ребер или дуг графа значительно меньше количества вершин, то эффективно представлять графы матрицами инциденций. Пусть G=(V, E), где V={v₁, v₂, …, v_n}, E={e₁, e₂, …, e_m}.Матрица инциденций для графа G - это матрица B размера nхm со значениями булевого типа, где B[i, j] = true тогда и только тогда, когда ребро из вершины i инцидентно ребру j. Часто в матрицах инциденций значение true заменяется на 1, а значение false - на 0. В каждом столбце матрицы инциденций всегда ровно две единицы, остальные элементы равны нулю. Если в графе все вершины имеют степень ноль, то матрицы инциденций не существует. Время доступа к элементам матрицы инциденций зависит от размеров множества вершин и множества дуг. Представление графа в виде матрицы инциденций удобно применять в тех алгоритмах, в которых надо часто обрабатывать ребра между парами вершин для построения путей, обхода ребер и т.п..Представления графов списками смежности. Вместо матриц смежности или инциденций часто используется другое представление для графа G = (V, Е), называемое представлением посредством списков смежности. Списком смежности для вершины i называется список всех вершин, смежных с вершиной i, причем определенным образом упорядоченный. Таким образом, граф G можно представить посредством массива HEAD (Заголовок), чей элемент HEAD[i] является указателем на список смежности вершины i. Представление графа с помощью списков смежности требует для хранения объем памяти, пропорциональный сумме количества вершин и количества дуг. Если количество дуг имеет порядок О(n), то и общий объем необходимой памяти имеет такой же порядок. Но и для списков смежности время поиска определенной дуги может иметь порядок О(n), так как такой же порядок может иметь количество дуг у определенной вершины.