Идеально сбалансированное дерево построение

Tree ++++

Идеально сбалансированные бинарные деревья Бинарное дерево называется идеально сбалансированным , если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1 .

Высота идеально сбалансированного бинарного дерева Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не превосходит величины:

2	log		n
h	n 1	log	n 2	2	2	1

Алгоритм построения идеально сбалансированного бинарного дерева Формулируется с помощью рекурсии. Для достижения минимальной высоты при заданном числе вершин, нужно располагать максимально возможное число вершин на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие в дерево вершины поровну слева и справа от каждой вершины. Идея алгоритма: взять одну вершину в качестве корня. построить левое поддерево с n1 = n / 2 вершинами тем же способом. построить правое поддерево с n2 = n-n1-1 вершинами тем же способом. 53

Программа построения идеально сбалансированного бинарного дерева TREE *CreateIdealTree (int n, TREE *&p) // p — указатель на корень дерева. < TREE *q=p; int x, nL, nR; if(!n) return 0; nL = n/2; nR = n – nL - 1; input(x); q = (TREE*) malloc(sizeof(TREE)); q->key = x; CreateIdealTree (nL, q->left); CreateIdealTree (nR, q->right); p = q; return p;

> // CreateIdealTree

54

АВЛ (AVL) — сбалансированные по высоте деревья Бинарное дерево поиска называется сбалансированным по высоте , если для каждой его вершины высота её двух поддеревьев различается не более, чем на 1 . Деревья, удовлетворяющие этому условию, часто называют АВЛдеревьями (по первым буквам фамилий их изобретателей Г.М. Адельсона-Вельского и Е.М. Ландиса ). Показатель сбалансированности вершины бинарного дерева есть разность высоты его правого и левого поддерева . Все идеально сбалансированные деревья являются также и АВЛ — деревьями и среди АВЛ-деревьев они являются деревьями с минимальной высотой при заданном числе вершин.

АВЛ — деревья Адельсон-Вельский и Ландис доказали, что АВЛдерево никогда не будет более, чем на 45% выше соответствующего идеально сбалансированного дерева независимо от количества узлов. Проведённый анализ показывает, что АВЛдеревья имеют достаточно короткие пути из корня в листья, что позволяет использовать их для организации поиска в больших массивах информации . Чтобы убедиться в этом, нужно показать, что включение и исключение узлов можно проводить, оставляя деревья АВЛсбалансированными. 57

Алгоритмы балансировки. Общие положения Рассмотрим теперь, что может произойти при включении в сбалансированное дерево новой вершины. Если у нас есть корень r , левое ( L ) и правое ( R ) поддеревья, то необходимо различать три возможных случая. Предположим, что включение в L новой вершины увеличит на 1 его высоту; тогда возможны три случая: сначала было h L = h R . После включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен; сначала было h L < h R . После включения L и R станут равной высоты, то есть критерий сбалансированности даже улучшится; сначала было h L >h R . После включения критерий сбалансированности нарушится и дерево необходимо перестраивать. 58

Пример дерева Вершины с ключами 9 и 11 можно включить в дерево, не нарушив его сбалансированности: дерево с корнем 10 становится односторонним , а дерево с корнем 8 — лучше сбалансированным. Однако включение значений 1, 3, 5 и 7 требует последующей балансировки. Алгоритм включения и балансировки существенно зависит от того, каким способом хранится информация о сбалансированности дерева. Удобно хранить в каждой вершине показатель

сбалансированности.

59

Источник

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

Двоичное дерево называется идеально сбалансированным (ИСД), если для каждой его вершины размеры левого и правого поддеревьев отличаются не более чем на 1. На рисунке приведены примеры деревьев, одно из которых является идеально сбалансированным, а другое – нет. Рисунок 4 Примеры ИСД и неИСД Отметим некоторые свойства идеально сбалансированного дерева. Свойство 1.Высота ИСД сnвершинами минимальна и равнаh_ИСД(n)= h_min(n) =log(n+1). Свойство 2.Если дерево идеально сбалансировано, то все его поддеревья также идеально сбалансированы. Задача построения идеально сбалансированного дерева поиска из элементов массива А = (а₁, а₂, … , а_n) решается в два этапа:

1. Сортировка массива А.
2. В качестве корня дерева возьмем средний элемент отсортированного массива, из меньших элементов массива строим левое поддерево, из больших – правое поддерево. Далее процесс построения продолжается до тех пор, пока левое или правое поддерево не станет пустым.

Пример. Построить ИСДП из элементов массива А. Пусть n = 16, а элементы массива это числа в 16-ричной системе счисления. А: В 9 2 4 1 7 Е F A D C 3 5 8 6 А_упор:1 2 3 4 5 6 7 8 9 А В С D E F Рисунок 5 Построение ИСДП Приведем на псевдокоде алгоритм построения ИСДП. Функция ИСДП (L, R) возвращает указатель на построенное дерево, где L, R – левая и правая границы той части массива, из элементов которой строится дерево.

Алгоритм на псевдокоде

Контрольные вопросы

1. Дайте определение двоичного дерева поиска.
2. Что такое идеально сбалансированное дерево поиска?
3. Какова высота ИСДП?
4. Каким образом строится ИДСП?

Случайное дерево поиска

Определение случайного дерева поиска

При решении многих типов задач объем данных заранее неизвестен, но необходима такая структура данных, для которой достаточно быстро выполняются операции поиска, добавления и удаления вершин. Одно из решений этой проблемы построение случайного дерева поиска (СДП). При построении СДП данные поступают последовательно в произвольном порядке и добавление нового элемента происходит в уже имеющееся дерево. Пример случайного дерева поиска для последовательности D: B 9 2 4 1 7 E F A D C 3 5 8 6 приведен на рисунке 6. Рисунок 6 Случайное дерево поиска Это дерево не является ИСДП. В худшем случае СДП может выродиться в список. Пример. 1) D: 1 2 3 4 5 2) D: 5 1 2 4 3 Рисунок 7 Плохие СДП Таким образом, средняя высота случайного дерева поиска может изменяться в пределах log n< h_срcд< n при больших n. В [1] показано, что ( h_{ср сд} / h_{ср исдп}) = 2ln 2 = 1,386. и h_{ср сд} =О(log n) при n→∞.

Источник

5.3. Идеально сбалансированные деревья

В заключение данной темы рассмотрим один частный случай ДД – так называемое идеально сбалансированное дерево (ИСД). Как будет отмечено в дальнейшем, эффективное использование деревьев на практике часто требует управления ростом дерева для устранения крайних случаев, когда дерево вырождается в линейный список и тем самым теряет всю свою привлекательность (с вычислительной точки зрения, разумеется).

В этом смысле ИСД полностью оправдывает свое название, поскольку вершины в нем распределяются наиболее равномерно и тем самым ИСД имеет минимально возможную высоту. Более точно, ДД называется идеально сбалансированным, если длякаждойвершины число вершин в левом и правом ее поддеревьях отличаются не более чем на единицу. Обратим внимание, что данное условие должно выполняться для всех вершин дерева!

Это – не ИСД (нарушение условия для корня!)

Это тоже не ИСД (совсем плохо, почти список!)

ИСД легко строится, если заранее известно количество вершин Nв этом дереве. В этом случае ИСД можно построить с помощью следующего рекурсивного алгоритма:

• взять первую по порядку вершину в качестве корневой
• найти количество вершин в левых и правых поддеревьях:

• построить левое поддерево с Nlвершинами точно таким же образом (пока не получимNl= 0)
• построить правое поддерево с Nrвершинами точно таким же образом (пока не получимNr= 0)

• Главная программа: вызов AddNodes(pRoot, 3)

• П/п 1: Nl= 1,Nr= 1, создание вершиныA, вызовAddNodes(A.left, 1)
• П/п 1-2: сохранение в стеке значений Nl= 1,Nr= 1, адресаA
• П/п 1-2: Nl= 0,Nr= 0, создание вершиныB, вызов

• П/п 1-2-3: сохранение в стеке значений Nl= 0,Nr= 0, адресаB
• П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
• П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр B.left = nil
• П/п 1-2: вызов AddNodes (B.right, 0)
• П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B
• П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
• П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр B.right = nil
• П/п 1-2: pCurrent = адрес B, возврат к 1
• П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A.left=адрес B
• П/п 1: вызов AddNodes (A.right, 1)
• П/п 1-2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A
• П/п 1-2: Nl = 0, Nr = 0, создание вершины C, вызов

• П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C
• П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
• П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр C.left = nil
• П/п 1-2: вызов AddNodes (C.right, 0)
• П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C
• П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
• П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр C.right = nil
• П/п 1-2: pCurrent = адрес C, возврат к 1
• П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A.right=адрес C
• П/п 1: pCurrent = адрес A, возврат в главную программу

• Главная программа: установка выходного параметра pRoot = адрес A

Источник

5.1. Построение идеально сбалансированного дерева.

Дерево называется идеально сбалансированным, если число вершин в его ле­вых и правых поддеревьях отличается не более чем на 1. Прежде чем обсуждать, как выполнять операциями над ними, приведем при­мер, как программа может строить сами деревья. Предположим, что дерево, кото­рое требуется сформировать, содержит вершины, относящиеся к типу u, а значения этих вершин – числа, поступающие из входного файла или другого источника (напри­мер, генератора случайных чисел). Пусть требуется построить дерево минималь­ной глубины и состоящее из n вершин. Очевидно, минимальная высота при заданном числе вершин достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число вершин. Этого просто добиться, разме­щая приходящие вершины поровну слева и справа от каждой вершины. Такое де­рево носит название идеально сбалансированного.

Правило равномерного распределения для известного числа вершин n лучше всего сформулировать, используя рекурсию:

1. Взять одну вершину в качестве корня.

2. Построить тем же способом левое поддерево с n1=n Div 2 вершинами.

3. Построить тем же способом правое поддерево с n2=n—n1-1 * вершинами.

(* — одну вершину занимает корень)

Ниже приведена процедура построения идеально сбалансированного дерева.

If k = 0 Then Begin Tree := Nil; Exit; End;

Вызов Begin …. h:=Tree(n); ….. End.

5.2. Визуализация дерева

На экране монитора в графическом режиме дерево можно нарисовать с помощью рекурсивной процедурой ShowTree:

Рrocedure ShowTree ( h :u; x, y, w, f :Integer );

If h < >Nil Then Begin

ShowTree (h ^.L, x-w div 4, y+4*r, w div 2, 1);

If f < >0 Then Line( x, y, x + f*(w div 2), y-4*r ); рисование ребра>

ShowTree (h^.R, x+w div 4, y+4*r, w div 2,-1);

Перевод экрана в графический режим;

SetTextJustify ( CenterText, CenterText );

Источник