Двоичное дерево. Логическое описание. Построение и визуализация

Тип данных дерево обычно отсутствует в универсальных языках программирования, и нужно его моделировать программно. Так же, как и в списках, цепная структура дерева будет состоять из динамически порождаемых элементов, в которых предусмотрены ссылки на очередные компоненты структуры:

struct node {

char key;

struct node* 1;

struct node* r; }

Динамическая структура выглядит так: >>>>>>>

Рассмотрим программу построения дерева из n вершин, значения которых поступают из входного текстового файла input. Если нам нужно построить из этих вершин какое- нибудь дерево, то можно первую из них сделать корнем, вторую правым поддеревом, третью правым поддеревом правого поддерева, и т. д. В результате получим линей­ное дерево (список) максимальной глубины (n). Интереснее обратная задача: построить из этих же вершин дерево минимальной глубины. Для этого при построении дерева надо добиться его равномерного заполнения (ау. сплошное турнирное представление!), разме­щая приходящие вершины поровну слева и справа от каждой вершины по следующему рекурсивному(!) правилу:

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

2)построить тем же способом левое поддерево с = n_l div 2 вершинами;

3)построить тем же способом правое поддерево с n_r = n — n_l — 1 вершиной.

25 Двоичное дерево. Физическое представление. Прошивка.

На массиве: цельный кусок памяти, на первом месте корень, на 2м и 3м – его левый и правый сыновья, а далее – по паром сыновья каждого родителя, т.е. Сыновья i-го родителя лежат на местах 2i и 2i+1 (j-ый элемент i-го уровня находится на месте 2^(j-1) + j – 1.

Основным неудобством сплошного представления дерева является высокая цена вставки и удаления элементов + перерасход памяти.

Для деревьев можно использовать рекурсивные ссылочные представления, которые были разработаны для списков, но с той лишь разницей, что указатели вперёд и назад по линейной структуре теперь направляются к левому и к правому поддеревьям соответственно.

Динамическая структура: каждый элемент указывает на место своих сыновей {сложнее читать/искать, но проще добавлять/удалять}

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

Связь-нить – в поле l указывает на узел-предшественник при обратном обходе, а в поле r – на узел-приемник.

Для прошитых деревьев можно выполнить не рекурсивный обход без использования стека.

Прошитое дерево линеаризовано и может быть помещено в очередь или список => можно применить итераторы для обработки, т.к функциональность совпадает.

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

26 Алгоритмы обхода деревьев.

Обход дерево – просматривание дерева по определённому алгоритму так, что все вершины будут просмотрены.

Для бинарного дерева:

I прямой обход (сверху вниз; КЛП; корень прежде; preorder) 1) если дерево пусто – конец обхода 2) берём корень 3) обходим левое поддерево 4) обходим правое поддерево

II обратный обход (слева направо; ЛКП; корень между; inorder) 1) если дерево пусто – конец обхода 2)обходим левое поддерево 3) берём корень 4)обходим правое поддерево

III концевой обход (снизу вверх; ЛПК; корень в конце; posorder) 1) если дерево пусто – конец обхода 2) обходим левое поддерево 3) обходим правое поддерево 4) берём корень

 

Для обычного дерева:

I поиск в глубину: 1) если дерево пусто – конец обхода

2) берём корень 3) ищем в глубину для поддерева старшего сына 4) ищем в глубину для поддерева следующего брата

II поиск в ширину: 1) поместить в пустую очередь корень дерева 2) если очередь узлов пуста – конец обхода 3) извлечь первый элемент из очереди и поместить в конец всех его сыновей 4) вернуться к п. 2)

27 Особенности представления и обработки деревьев общего вида (преобразование к двоичному,...)

Сплошное представление деревьев удобно пояснить на примере турнирного дерева с фик­сированной структурой. Считая, что участники турнира образуют полные пары нужной кратности, введём жёсткое размещение элементов дерева в массиве. В первом элементе массива разместим корень дерева, во 2-ом и 3-ем — его левого и правого потомков. Далее поместим пары потомков потомков и т. д. Сыновья элемента дерева с индексом i хранятся в элементах массива с индексами 2i и 2i + 1. Согласно данной схеме размещения, j-ып элемент i-ого уровня имеет индекс 2^i-[ + j — 1.

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

В представлении бинарного дерева содержатся два указателя на левое и правое подде­ревья (обозначим их l и г, соответственно). У листьев дерева оба эти указателя пустые. Поскольку в бинарном дереве, как правило, около половины узлов являются листьями (если не рассматривать вырожденные случаи), то такое представление оказывается неэко­номичным с точки зрения расхода памяти.

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

Деревья выражений

Деревья выражений – деревья, в узлах которых стоят элементы выражения (+, _, *, /, a = const, x!= const).

при прямом обходе получаем префиксную (польскую) форму: * + a / bc – d * ef (КЛП – Левый-Корень-Правый)

при обратном обходе получаем инфиксную (обычную) форму без скобок: a + b / c * d – e * f (ЛКП)

при концовом обходе получаем постфиксную (обратную польскую) форму: abc / + def * - *( ЛПК)

Пример1:Выражение (1+2)*4+3 в ОПН может быть записано так: 1 2 + 4 × 3 +

Вычисление производится следующим образом (указано состояние стека после выполнения операции):

Ввод Операция Стек

1 поместить в стек 1

2 поместить в стек 1, 2

+ сложение 3

4 поместить в стек 3, 4

* умножение 12

3 поместить в стек 12, 3

+ сложение 15

Результат: 15, в конце вычислений находится на вершине стека.

Пример2: для вычисления деревья выражений можно применить алгоритм Дейкстры основанный на применении стеков с приоритетами и польской записью:

30 Деревья поиска. Дерево поиска – это такое дерево, для каждого узла t которого выполняются следующие условия: 1) ключи всех узлов в левом поддереве меньше значения t 2) ключи всех узлов в правом поддереве больше значения t.

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

Дерево поиска может быть использовано для упорядочивания данных. Для этого надо разместить эти данные в дереве поиска, а потом составить в результате его обхода упо­рядоченную последовательность. Но для решения этой задачи обычное дерево поиска не подходит: оно не допускает вхождения равнозначных элементов. Поэтому всякий новый элемент теперь должен быть включён в дерево. Для этого случай х = р^.key необходимо рассматривать вместе с одним из других. Если его объединить с х > р^.кеу, то порядок следования элементов с одинаковыми ключами совпадёт с хронологией их поступления в дерево. Возможность сочетания поиска и упорядочивания растущего множества дан­ных, предоставляемая деревом поиска с включениями, даёт новое качество по сравнению с хранением данных как в списках, так и в массивах. Например, этим способом можно эффективно решить задачу составления таблицы перекрёстных ссылок слов текста.

 

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

Т.к. введение новой вершины в идеально сбалансированное дерево его разбалансирует, то решили делать балансировку после вставки.

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

(идеально сбалансированное дерево является AVL-деревом)В AVL-дереве можно найти искомую вершину, добавить новую или удалить старую.

Схема алгоритма включения в сбалансированное дерево такова:

1. поиск элемента в дереве; 2. включение новой вершины и определение результирующего показателя сбалансированности; 3. отход по пути поиска с проверкой показателя сбалансированности для каждой проходимой вершины, балансируя в необходимых случаях соответствующие поддеревья.

Сложность балансировки оправдана тогда, когда поиск данных происходит значительно чаще¸ чем вставка. Двудетные вершины дерева обрабатываются путем замены самой правой вершины из левого поддерева. Удаление элементов выглядит так:

32 Простые методы поиска.

Линейный поиск – последовательный просмотр массива как списка (цикл). Поиск происходит за O(N). Индексация начинается с 0. Ускорить поиск можно с помощью барьерного элемента. Его следует поместить в N+1 -ый элемент массива. Этот метод поиска единственный для структур данных со строго последовательным доступом.

int function LinearSearch (Array A, int L, int R, int Key);

Begin

for X = L to R do

if A[X] = Key then

Return X