Проблемы использования деревьев поиска

Как было отмечено выше, эффективность поиска при помощи ДП очень находится в зависимости от структуры дерева: чем поближе дерево к совершенно равновесному, тем меньше высота дерева и тем выше эффективность поиска. К огорчению, входные данные при построении дерева могут быть такими, что дерево начинает деформироваться на лево либо на право - становится Проблемы использования деревьев поиска разбалансированным. В последнем случае, дерево преобразуется в обыденный линейный перечень, т.е. становится вырожденным. Отсюда следует, что процесс построения дерева должен контролироваться надлежащими методами, которые при выполнении процедур прибавления либо удаления могли бы делать перестройку дерева с целью сохранения его структуры очень близкой к совершенно равновесной.

К примеру, один и Проблемы использования деревьев поиска тот же входной набор числовых ключей, но поступающий в разном порядке, может приводить к значительно различным ДП.

“Не плохая” входная последовательность: 20 – 10 – 30 – 15 – 25 – 5 - 40 “Нехорошая” входная последовательность: 10 – 15 – 20 – 5 – 25 – 30 - 40

Данная неувязка исследуется уже около 40 лет, существует несколько способов сохранения “неплохой” структуры дерева. К огорчению, требование безупречной сбалансированности дерева оказалось очень сильным и до сего Проблемы использования деревьев поиска времени нет добротных алгоритмов поддержания структуры дерева всегда в совершенно равновесном виде. Заместо этого сильного требования было предложено несколько более обычных, но комфортных с вычислительной точки зрения критериев “неплохого” дерева.

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

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

Разумеется, что хоть Проблемы использования деревьев поиска какое совершенно равновесное дерево является также и АВЛ-сбалансированным, но не напротив.

Совершенно равновесное и оно же АВЛ-сбалансированное АВЛ-сбалансированное, но не совершенно равновесное Не АВЛ-сбалансированное (нарушение – для корня)

Для реализации алгоритмов АВЛ-балансировки в каждой верхушке дерева комфортно хранить так именуемый коэффициент балансировки (КБ) как разность высот правого Проблемы использования деревьев поиска и левого поддеревьев. Для АВЛ-деревьев у всех вершин значение КБ равно –1, 0 либо +1.

25 (0)
10 (0)
40 (0)
20 (0)
30 (-1)

27 (0)
22 (0)
25 (0)
10 (0)
20 (+1)
40 (0)
30 (-2)

АВЛ-сбалансированное дерево несбалансированное дерево

Так как коэффициент балансировки употребляется для каждой вершин, комфортно ввести его в структуру данных, описывающих эту верхушку:

Type Tp = ^TNode;

TNode = record

Inf : ;

Left, right : Tp;

Balance : shortInt;

end;

Метод АВЛ-балансировки при добавлении верхушки Проблемы использования деревьев поиска.

· производится поиск в дереве места для новейшей дополнительной верхушки, при всем этом для каждой верхушки высчитывается коэффициент балансировки

· если нужно, то производится добавление самой верхушки с наполнением всех полей, в том числе и КБ =0 (т.к. потомков у вновь сделанной верхушки пока нет)

· меняется на 1 коэффициент балансировки Проблемы использования деревьев поиска у родителя добавленной верхушки: КБ = КБ + 1 если добавлен правый потомок, по другому КБ = КБ - 1

· проверяем новое значение КБ у родительской верхушки: если он имеет допустимое значение, то перебегаем еще на уровень выше для конфигурации и анализа КБ у деда новейшей верхушки и т.д – до корневой верхушки (время от Проблемы использования деревьев поиска времени условие балансировки может нарушиться только для корневой верхушки, потому приходится инспектировать все верхушки на пути от вновь добавленной до корневой)

· если у какой или верхушки нарушается условие балансировки, запускается особый метод перестановки вершин, который восстанавливает АВЛ-балансировку дерева и в то же время сохраняет упорядоченную структуру дерева поиска

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

5 (0)
10 (-1)
20 (0)
15 (-1)
40 (0)
30 (-2)

5 (0)
40 (0)
20 (0)
30 (0)
10 (-1)
15 (0)

до балансировки после балансировки

Данная ситуация является более обычной и определяется последующими критериями:

· верхушка с нарушенным условием балансировки Проблемы использования деревьев поиска деформирована на лево, КБ(30) = -2

· ее левый потомок также перевешивает в левую сторону, КБ(15) = -1

Для исправления этой ситуации производится однократный поворот на право:

· верхушка 15 подменяет верхушку 30

· левое поддерево верхушки 15 не меняется (15 – 10 – 5)

· правое поддерево верхушки 15 появляется корневой верхушкой 30

· у верхушки 30 правое поддерево не меняется (30 – 40)

· левое поддерево верхушки 30 появляется бывшим правым потомком Проблемы использования деревьев поиска верхушки 15, т.е. 20

Аналогично производится однократный поворот на лево, если верхушка с нарушенным условием балансировки перевешивает на право (КБ = 2), а ее правый потомок тоже перевешивает на право (КБ = 1).

Более сложные случаи появляются при несогласованном перевешивании корневой верхушки и ее потомков (коэффициенты балансировки имеют различные знаки). К примеру, разглядим случай, когда корневая верхушка поддерева Проблемы использования деревьев поиска с нарушенным условием перевешивает на лево (КБ = -2), но ее левый потомок перевешивает на право (КБ = 1).

23 (0)
5 (0)
17 (0)
50 (0)
10 (-1)
20 (+1)
25 (-1)
15 (+1)
40 (+1)
30 (-2)

50 (0)
23 (0)
5 (0)
40 (+1)
10 (-1)
25 (-1)
17 (0)
30 (0)
15 (-1)
20 (0)

до балансировки после балансировки

Двукратный поворот содержит в себе:

· верхушка 30 заменяется верхушкой 20, т.е. правым потомком левого потомка

· левый потомок верхушки 20 (верхушка 17) становится правым потомком верхушки 15

· левое поддерево с корнем 15 без конфигураций остается левым поддеревом верхушки 20

· правое поддерево Проблемы использования деревьев поиска верхушки 20 начинается с верхушки 30

· правое поддерево верхушки 30 не изменяется (30 – 40 – 50)

· левое поддерево верхушки 30 появляется правым поддеревом верхушки 20 (25 – 23)

Удаление вершин из АВЛ-дерева производится аналогично:

· ищется удаляемая верхушка

· если требуется – определяется вершина-заменитель и производится обмен

· после удаления верхушки пересчитываются КБ и по мере надобности делается балансировка точно по таким же правилам

В отличие Проблемы использования деревьев поиска от прибавления, при удалении вероятны ситуации, когда балансировка будет нужно для всех вершин на пути от удаленной верхушки до корня дерева.

Практика использования АВЛ-деревьев показала, что балансировка требуется приблизительно в половине случаев вставки и удаления вершин.

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


problemi-i-perspektivi-razvitiya-menedzhmenta.html
problemi-i-perspektivi-razvitiya-sudebnoj-stroitelno-tehnicheskoj-ekspertizi-stranica-6.html
problemi-i-perspektivi-rekeacionnih-resursov-italii.html