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

Avl — деревья

На прошлом занятии мы изучили упорядоченные бинарные деревья(УБД). Однако при некоторых данных дерево может оказаться вырожденным. Тогда его высота будет n и доступ к данным существенно замедлится.

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

Высотой некоторого бинарного дерева является максимальный уровень его листьев.

Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.

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

АVL — дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так.

Следует заметить, что сбалансированные деревья очень эффективны для поиска. Предположим у нас сбалансированное дерево и упорядоченное бинарное дерево, которое вырождено, оба эти дерева содержат 10000 узлов. Так, например, упорядоченном бинарном дереве следует просмотреть 9999 уровней дерева прежде, чем он найдет самый крайний правый узел, а сбалансированном дереве 8 уровней.

Давайте расставим балансы для каждого узла для следующего дерева.

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

Мы рассмотрим только вставку в сбалансированное дерево, удаление очень сложное и поэтому его мы рассматривать не будем.

Включение в сбалансированное дерево

1. h_L = h_R: L и R становятся неравной высоты, но критерий сбалансированности не нарушается
2. h_L < h_R: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается
3. h_L > h_R: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.

1. Прохождение трансформированного дерева в симметричном порядке должно быть таким же, как и для первоначального дерева (т.е. трансформированное дерево должно оставаться деревом бинарного поиска)
2. Трансформированное дерево должно быть сбалансированным

Одинарный поворот вправо происходит тогда, когда родительский узел Р и его левый сын LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывая правое поддерево узла LC (ST) присоединяется к Р в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла Р. Поворот уравновешивает как родителя, так и его левого сына.

Двойной поворот вправо происходит тогда, когда родительский узел (Р) становится перевешивающим влево, а его левый сын (LC) — перевешивающим вправо. NP — корень правого перевешивающего дерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

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

Принцип работы алгоритма показан на рисунках.

Рассмотрим бинарное дерево (а), которое состоит только из двух узлов.

Включение ключа 7 вначале дает несбалансированное дерево (т. е. линейный список). Его балансировка требует однократного — левого поворота, давая в результате идеально сбалансированное дерево (b).

Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным правым поворотом (d).

Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота направо и налево; результатом является дерево (е).

Теперь при следующем включении потерять сбалансированность может лишь узел 5. Включение узла 6 должно привести двукратному повороту налево и направо.

Давайте напишем программу поиска и вставки узла.

Type node = record
Key: integer;
Left, right: ref;
Bal: -1..1;
End;

procedure search(x: integer; var p: ref; var h: boolean);
var
p1, p2: ref;
begin
if p = nil then
begin <узла нет в дереве; включить его>
new(p);
h := true;
with p^ do
begin
key := x;
count := 1;
left := nil;
right := nil;
bal := 0;
end
end
else
if x < p^.key then
begin
search(x, p^.left, h);
if h then <выросла левая ветвь>
case p^.bal of
1: begin p^.bal := 0; h := false end ;
0: p^.bal := -1;
-1: begin <балансировка>
p1:= p^.left;
if p1^.bal = -1 then
begin <однократный правый поворот>
p^.left := p1^.right;
p1^.right := p;
p^.bal := 0;
p := p1
end
else
begin <двукратный правый - левый поворот>
p2 := p1^.right;
p1^.right := p2^.left;
p2^.left :=p1;
p^.left := p2^.right;
p2^. right := p;
if p2^.bal =-1 then p^.bal:=1 else p^.bal := 0;
it p2^.bal = 1 then p1^.bal := -1 else p1.^bal :=0;
p :=p2;
end;
p^.bal := 0;
h := false;
end
end
end
else
if x > p^.key then
begin
search(x, p^.right, h);
if h then <выросла правая ветвь>
case p^.bal of
-1: begin p^.bal := 0; h :=false; end ;
0: p^.bal := 1;
1: begin <балансировка>
p1 := p^.right;
if р1^.bal =1 then
begin <однократный левый поворот>
p^.right := p1^.left;
p1^.left := p;
p^.bal := 0;
p := p1;
end
else
begin <двукратный левый - правый поворот>
p2 := p1^.left;
p1^.left := p2^.right;
p2^.right := p1;
p^.right := p2^.left;
p2^.left := p;
if p2^.bal = 1 then p^.bal := -1 else p^.bal:=0;
if p2^.bal = -1 then p1^.bal := 1 else p1^.bal: = 0;
p :=p2;
end ;
p^.bal := 0; h:= false;
end
end
end
else
begin
p^.count := p^.count + 1; h :=false;
end
end

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

Существует несколько определений того, что такое дерево. Например, дерево – это лес, состоящий из одного связного компонента (т.е. из одного дерева) (рекурсивное определение). Или (с точки зрения теории графов), дерево – это граф без циклов. Рассмотрим деревья с точки зрения структур данных, которые должны использоваться в программах и храниться в памяти.

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

Эти структуры данных в общем случае можно разделить на две группы, которые отличаются друг от друга способом построения и (как следствие) реализацией процедур обработки – собственно деревья и пирамиды (или «кучи«). Но у обеих этих групп сохраняется общий древовидный характер и часто их объединяют под общим коротким названием «деревья«. Отличие пирамид от деревьев (и значения термина «куча«) будет рассмотрено позже.

Обычно предполагается, что дерево – это неориентированная структура данных, но при реализации связей, аналогичной спискам, направление (т.е. ориентация) задаётся автоматически. Кроме того, некоторые алгоритмы обработки деревьев предполагают, что дерево является ориентированным (что не всегда удобно).

Классификация. Существует очень большое количество видов древовидных структур данных, которые можно классифицировать по нескольким различным признакам. Одно такое разделение уже было приведено – деревья и пирамиды.

Из других признаков классификации следует указать (в 1-ю очередь) число ветвей, отходящих от корня дерева. Деревья могут быть:

— двоичными (или бинарными) – имеющими не более двух ветвей (примеров таких деревьев очень много, они будут приведены позже);

– с числом ветвей больше 2 – часто такие деревья называют мультивариантными (многопутевыми) или K-деревьями (т.е. K-мерными). Примерами могут быть 2-3-деревья (и им подобные), Б-деревья (различные деревья Байера с подвариантами, например, дерево Байера-МакКрейта, Байера-Баума) и т.п. Видов K-деревьев очень много (свыше 40 различных древовидных структур для представления многомерной информации: R-Tree, R+-Tree, Hilbert R-Tree, hB-Tree, hBII-Tree, BV-Tree, BD-Tree, GBD-Tree, G-Tree, SKD-Tree, kd-Tree, kd2B-Tree, BSP-Tree, LSD-Tree, P-Tree, TR-Tree, Cell-Tree, Quadtree, Grid File, Z-Hashing, SS-Tree).

Важным признаком является состояние сбалансированности дерева и способы его достижения. Деревья могут быть:

– идеально сбалансированными (отличие этих двух первых состояний будет рассмотрено позже);

– отличающимися более или менее сильно от сбалансированных и от вырожденных.

Автоматическая балансировка дерева выполняется, например, для АВЛ-деревьев, красно-чёрных деревьев (все эти деревья являются двоичными), Б-деревьев и некоторых других видов деревьев.

Ещё один важный признак классификации – применение деревьев (хотя не всегда из названия дерева следует, что оно применяется именно с этой целью). В качестве примера можно указать деревья поиска или сортировки, но из названия «дерево поиска» не следует, что оно применяется только для поиска.

Отдельные типы деревьев применяются для решения специальных задач, например остовные деревья на графах (каркасы графов, Spanning Tree) или PATRICIA-деревья (Practical Algorithm To Retrieve Information Coded In Alphanumeric), используемые для поиска данных на основе их поразрядного двоичного представления.

Несколько несвязанных между собой деревьев образуют структуру данных, которая называется «лес» (иногда её называют «бор«).

4.1 Двоичные деревья поиска

Ещё раз дадим определение дерева как структуры данных.

Дерево — динамическая нелинейная структура данных, каждый элемент которой содержит собственно информацию (или ссылку на то место в памяти ЭВМ, где хранится информация) и ссылки на несколько (не менее двух) других таких же элементов. Для двоичного (бинарного) дерева таких ссылок две: на правый соседний и левый соседний элементы.

В общем случае данные, хранящиеся в дереве, не обязаны быть упорядочены каким-либо образом. Но часто требуется соблюдение упорядоченности по некоторому принципу. Именно по такому принципу упорядоченности и отличаются «пирамиды» и «деревья«:

– пирамида («куча«) – древовидная структура данных, в которой значения всех узлов, размещённых на одном уровне, больше (или меньше) значений узлов, размещённых на выше лежащем уровне (см. рисунок);

Рисунок 4.1 – Двоичная пирамида

– дерево – древовидная структура данных, в которой значения всех узлов, размещённых правее некоторого узла, больше значений узлов, размещённых левее, причём это справедливо как для всего дерева, так и для любой его части (см. рисунок). Здесь необходимо сделать одно существенное уточнение: по указанному принципу строится дерево, получившее название «двоичного дерева поиска» (Binary Search Tree, BST), т.е. дерево, в котором очень удобно искать данные, причём с высокой эффективностью этого поиска. В дальнейшем под двоичными деревьями будут подразумеваться именно двоичные деревья поиска.

Рисунок 4.2 – Двоичное дерево поиска

Как видно из сравнения рисунков 4.1 и 4.2, структура у пирамиды и дерева практически одинакова, отличаются они только характером размещения данных.

Также на этих рисунках видны и связи между элементами деревьев (узлами), похожие на связи между звеньями списка. Чем же отличается двоичное дерево от двусвязного списка? Иногда ничем, не только от двусвязного, но и от односвязного списка. Основное отличие — у списка соседними являются предшествующий и последующий элементы, и структура линейна; а у двоичного дерева поиска соседними являются элементы с меньшим и большим ключом, и структура, в общем случае ветвящаяся — в виде дерева, откуда она и получила свое название. Кроме того, любая часть дерева по своей структуре повторяет всё дерево в целом, т.е. дерево (любое, не только двоичное) – это рекурсивная структура данных (фактически дерево можно считать фрактальной структурой).

Рисунок 4.3 – Фрактальные деревья

Нужно помнить, что дерево – это только метод логической организации информации в памяти, а память – линейна.

В случае, если информация хранится в произвольном (и неизвестном программисту) месте памяти, а ключ и информация – разные понятия (иногда они могут и совпадать), структура узла дерева может быть представлена следующим образом:

Рисунок 4.4 – Обобщённая структура узла дерева

Этой структуре соответствует набор типов на языке Паскаль:

type
info = (* тип хранимых данных *);
ptr = ^node;
node = record
key: Integer;
left, right: ptr;
data: ^info
tree: ptr;

И на языках Си/Си++:

struct node
<
int key; // Ключ, по которому строится дерево
float data; // Полезные данные (могут быть любого типа)
node *left, *right; // Указатели на соседние узлы
>;

Двоичное дерево, образованное такими элементами, показано ниже.


Рисунок 4.5 – Двоичное дерево

Элемент дерева получил название «узел» (node). Единственный начальный элемент (откуда дерево развивается) – корень (root). Фрагмент (часть) дерева – поддерево или ветвь. Узел, от которого не отходят ветви – конечный или терминальный узел, иногда его называют листом. Как видно на рисунках, узлы располагаются по уровням. Количество уровней – высота дерева (иногда вместо высоты используют термин «глубина«). Поскольку дерево – рекурсивная структура данных, то любой его узел может считаться корнем какой-либо ветви, в том числе пустой.

Области применения деревьев: для хранения информации, как таковой; в процедурах поиска и сортировки; для описания хранения файлов на дисковых носителях; при построении эффективных кодов для сжатия информации (коды Шеннона–Фано и Хаффмэна).

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

4.2 Операции с деревьями

Для деревьев имеются те же основные операции, что и для списков – добавление элемента, удаление, прохождение (просмотр) и поиск элементов. Кроме них можно использовать операции принудительной балансировки, подсчёта числа узлов в дереве, измерения высоты дерева, поиска ближайшего общего корня (ближайшего общего предка – Nearest Common Ancestor (nca)) для двух элементов (в многопутевых деревьях – для более чем двух элементов). При балансировке деревьев используются операции поворотов (вращений), простых и двойных, левых и правых.

Поскольку дерево – рекурсивная структура данных, то наиболее эффективными при работе с деревьями оказываются рекурсивные процедуры. Хотя возможно применение и нерекурсивных процедур. Рассмотрим разные варианты построения этих процедур.

4.2.1 Добавление узла в дерево

Рассмотрим принцип построения дерева при занесении в него информации. Пусть последовательно вводятся записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86, 82.

2. 60 70, следовательно новый узел будет расположен справа от 70;


Рисунок 4.6 – Процесс построения дерева

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

Рекурсивная процедура добавления узла в дерево на языке "Паскаль"

if r = nil then
begin
new(r);
r^.left := nil;
r^.right := nil;
r^.key := newkey;
r^.data := newdata;
if tree = nil then
tree := r; (* Первый узел *)
if newkey<prev^.key then
prev^.left := r
prev^.right := r
addnode_r(r^.left,r,newkey)
addnode_r(r^.right,r,newkey)

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

— указатель на корень дерева или ветви, в котором ищется место для нового узла;

— указатель на предыдущий узел;

— сохраняемые данные или указатель на них.

При первом вызове второй аргумент может быть равен nil.

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

Рассмотренная процедура использует ранее опредёленный указатель на дерево tree, которому необходимо присвоить значение nil перед первым вызовом этой процедуры (поскольку оно проверяется в строке if tree = nil . ). Приведём пример аналогичной функции на языке Си++, у которой такой же указатель является аргументом (это позволяет избежать использования глобальных структур данных):

void add_node(node*& tree, node*& r, node*& prev, node& buf)

if (buf.key < prev->key)

add_node(tree, r->left, r, buf);

add_node(tree, r->right, r, buf);

Аргументы этой функции:
tree – указатель на всё дерево;
r – указатель на некоторый текущий узел;
prev – указатель на узел, «родительский» для r;
buf – буферная структура данных типа node, содержащая вводимые данные.
Перед первым вызовом указатель tree должен быть обнулён, а сам вызов может быть следующим:

tree = NULL;
node buf;
// .
buf.key = . // Ввод данных в буферную область памяти
buf.data = .
// .
add_node(tree,tree,tree,buf);

4.2.2 Прохождение дерева

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

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

Существует три способа прохождения дерева:

1. Последовательный – дерево проходится, начиная с левой ветви вверх к корню, затем к правой ветви;

2. Нисходящий – от корня к левой ветви, затем к правой;

3. Восходящий – проходится левая ветвь, затем правая, затем корень.


Рисунок 4.7 – Обход дерева

Под корнем здесь понимается как корень всего дерева, так и корень текущей ветви (поддерева).

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

Нисходящий способ удобен для сохранения дерева (т.е. данных, в нём хранящихся) в файл так, чтобы при последующем считывании была бы полностью восстановлена структура дерева.

Рекурсивные процедуры прохождения дерева в последовательном (inorder), нисходящем (preorder) и восходящем (postorder) порядках на языке "Паскаль"

if r = nil then exit;
inorder(r^.left);
writeln( . ); <Вывод информации>
inorder(r^.right)
if r = nil then exit;
writeln( . ); <Вывод информации>
preorder(r^.left);
preorder(r^.right)
if r = nil then exit;
postorder(r^.left);
postorder(r^.right)
writeln( . ); end;

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

Аналогичные процедуры на языке Си:

void inorder(node* r)
<
if (r == NULL) return;
inorder(r->left);
cout<<r->key right);
>

void preorder(node* r)
<
if (r == NULL) return;
cout<<r->key left);
preorder(r->right);
>

void postorder(node* r)
<
if (!r) return;
postorder(r->left);
postorder(r->right);
cout<<r->key

4.2.3 Поиск узла в дереве

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

void poisk1(node* r, int skey, node*& f)
<
if (r == NULL || f) return;
if (r->key == skey)
< f = r; return; >// Выход, если нашли
else
if (skey < r->key)
poisk1(r->left, skey, f);
else
poisk1(r->right, skey, f);
>

Третий аргумент node*& f – одновременно узел, в котором находятся найденные данные, и признак успеха поиска. Перед вызовом этой функции соответствующий фактический аргумент должен быть равен нулю.

Рекурсивные процедуры и функции, при всех их достоинствах, обладают одним серьёзным недостатком – возможностью переполнения стека возврата из подпрограмм при большом количестве рекурсивных вызовов (а это может произойти при большом размере структуры данных), поэтому рассмотрим другой вариант реализации поиска – использование нерекурсивной процедуры:


Нерекурсивная функция поиска в двоичном дереве на языке "Паскаль"

p, q: ptr;
b: boolean;
b := false;
p := tree;
if tree <> nil then
repeat
q := p;
if p^.key = skey then
 
b := true
if skey < p^.key then
p := p^.left
p := p^.right

Аналогичная функция на языке Си++:

Эта функция практически идентична по общей структуре предыдущей рекурсивной функции. В этом примере виден и способ преобразования рекурсивных функций в нерекурсивные: рекурсивный вызов, находящийся в конце процедуры («хвостовая» рекурсия) заменяется на цикл (в этом примере – цикл с предусловием), а рекурсивный вызов, размещённый где-либо до конца процедуры, заменяется на оператор if.

Длительность поиска зависит от структуры дерева. Для сбалансированного дерева (изображено на рисунке) поиск аналогичен двоичному – то есть нужно просмотреть не более log₂(N) узлов.


Рисунок 4.8 – Сбалансированное дерево

Для вырожденного дерева (изображено на рисунке) поиск аналогичен поиску в односвязном списке – в среднем нужно просмотреть половину узлов.


Рисунок 4.9 – Вырожденное дерево

Используя поиск узла, можно заменить рекурсивную процедуру добавления узла на нерекурсивную:


Нерекурсивная процедура добавления нового узла в дерево на языке "Паскаль"

r,s:ptr;
t:^info;
if not search_tree(skey,tree,r) then
begin
new(t); <Занесение>
t:=newdata; <данных>
new(s); <новый>
s^.key:=skey;
s^.left:=nil; <узел>
s^.right:=nil;
s^.data:=t;
if tree=nil then
tree:=s
if skey<r^.key then
r^.left:=s
r^.right:=s

4.2.4 Удаление узла из дерева

Удаление узла из дерева – существенно более сложный процесс, чем поиск, так как удаляемый узел может быть корневым, левым или правым. Узел может давать начало ветвям (в двоичном дереве их может быть от 0 до двух).

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


Рисунок 4.10 – Удаление узла из дерева

Для этого достаточно скорректировать соответствующий указатель у предшествующего узла.

Наиболее трудный случай – удаление корневого узла поддерева (или всего дерева) с двумя ветвями, поскольку приходится корректировать несколько указателей. Нужно найти подходящий узел, который можно было бы вставить на место удаляемого, причем этот подходящий узел должен просто перемещаться. Такой узел всегда существует. Это либо самый левый узел правой ветви, либо самый правый узел левой ветви.

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

Такой узел может иметь не более одной ветви.

Пример удаления из дерева узла с ключом 50.


Рисунок 4.11 – Пример удаления узла из дерева

Процедура удаления узла должна различать три случая:

— узла с данным ключом в дереве нет;

— узел с заданным ключом имеет не более одной ветви;

— узел с заданным ключом имеет две ветви.

Процедура удаления узла (автор — Никлаус Вирт)

Процедура удаления узла двоичного дерева на языке "Паскаль"

q: ptr;
if r^.right = nil then
begin
q^.key := r^.key;
q^.data := r^.data;
q := r;
r := r^.left
del1(r^.right)
if d = nil then exit (* Первый случай *)
else
if key < d^.key then
delnode(d^.left,key)
if key > d^.key then
delnode(d^.right,key)
q := d; (* Второй случай *)
if q^.right = nil then
d := q^.left
if q^.left = nil then
d := q^.right
del1(q^.left);
dispose(q) (* Собственно удаление *)

Вспомогательная рекурсивная процедура del1 вызывается только в третьем случае. Она проходит дерево до самого правого узла левого поддерева, начиная с удаляемого узла q^, и заменяет значения полей key и data в q^ соответствующими записями полей узла r^. После этого узел, на который указывает r можно исключить (r := r^.left).

void del_node(node*& d, int key)
<
node* q;
if (d == NULL)
return;
else
if (key < d->key)
del_node(d->left, key);
else
if (key > d->key)
del_node(d->right, key);
else
<
q = d;
if (q->right == NULL)
d = q->left;
else
if (q->left == NULL)
d = q->right;
else
del1(q->left, q);
delete q; // Удаление
>
>

4.2.5 Удаление всех узлов

Эта операция выполняется по тому же принципу, что и просмотр дерева:
void del_all(node*& r)
<
if (!r) return;
del_all(r->left);
del_all(r->right);
delete r;
r = NULL;
>

4.2.6 Подсчёт узлов

Это же справедливо и для подсчёта числа узлов в дереве:
void Nnodes(node* r, int& p)
<
if (r == NULL) return;
p++;
Nnodes(r->left, p);
Nnodes(r->right, p);
>

Число узлов сохраняется в аргументе p.Соответствующий ему фактический аргумент должен быть обнулён перед вызовом функции для получения правильного результата.

4.2.7 Определение высоты дерева

То же самое справедливо и при подсчёте числа уровней. После завершения работы функции высота дерева сохраняется в формальном аргументе h и в соответствующем фактическом аргументе.
void Height(node* r, int p, int& h)
<
if ( r == NULL) return;
p++;
key if( r->left == NULL && r->right == NULL) // Проверка на достижение терминального узла
if (p > h)
h = p;
Height(r->left, p, h);
Height(r->right, p, h);
>

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

4.3 Сбалансированные деревья

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

Сбалансированное бинарное дерево – максимально широкое и низкое. Именно такими являются деревья, показанные на рисунках 4.2, 4.5, 4.7 и 4.8. Фактически все эти деревья, кроме 4.5, являются идеально сбалансированными.

Менее строгое, но практически более удобное определение сбалансированности дерева – дерево является сбалансированным, если для каждого узла исходящие ветви отличаются по высоте не более, чем на одни уровень.

Обратный случай – вырожденное дерево – выродившееся в линейный односвязный список. Такое дерево получается, если заносимые в него данные упорядочены по-возрастанию (рисунок 4.9) или по-убыванию.

Вырожденные деревья также получили название лево- или право-ассоциативных или «лоз«, а также являются частным случаем ориентированных деревьев.

Если данные случайны, то получается дерево, в той или иной степени приближающееся к сбалансированному (рисунки 4.6, 4.11).

Для двоичного идеально сбалансированного дерева с максимально возможным (для идеальной сбалансированности) числом узлов существуют простые соотношения между этим числом узлов N_узлов и высотой дерева (т.е. числом уровней) n_{уровней} :
N_узлов = 2 n_{уровней} − 1
n_{уровней} = log₂(N_узлов + 1)

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

4.3.1 АВЛ-дерево

АВЛ-дерево получило своё название по фамилиям его разработчиков – советских математиков Георгия Максимовича Адельсон-Вельского (родился 8 января 1922 г. в Самаре) и Евгения Михайловича Ландиса, которые предложили использовать такое дерево в 1962 году.

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

4.3.2 Красно-чёрное дерево

Красно-чёрное дерево (RB-tree) отличается от АВЛ-дерева смыслом признака сбалансированности: вместо разности высот ветвей используется абстрактный «цвет» (красный или чёрный) и дерево строится по следующим правилам:

1. Все указатели на терминальные узлы считаются непустыми (т.е. в дереве имеются фиктивные терминальные узлы).

2. Все такие терминальные узлы считаются «чёрными«.

3. Все узлы, соседние с «красными» узлами, считаются «чёрными» (т.е. запрещена ситуация с двумя «красными» узлами подряд).

4. В левой и правой ветвях дерева, ведущих от его корня к листьям, число «чёрных» узлов одинаково. Это число называется «чёрной высотой» дерева.

Рисунок 4.12 – Пример красно-чёрного дерева с фиктивными чёрными терминальными узлами

Теоретически считается, что красно-чёрное дерево требует меньшего объёма памяти для хранения отдельного узла, чем АВЛ-дерево, т.к. для представления цвета достаточно всего одного бита. Но на практике это преимущество реализовать без потерь на дополнительные операции доступа к отдельным битам весьма сложно. Даже один из вариантов реализации красно-чёрного дерева – когда «красные» узлы обозначаются нечётными ключами, а «чёрные» узлы – чётными (или наоборот), не всегда пригоден на практике, т.к. решаемая задача может не допускать такого разделения узлов.

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

Рисунок 4.13 – Операция вращения (поворота)

Здесь чёрным цветом показано исходное несбалансированное дерево (ветви показаны большими треугольниками, внутри этих ветвей узлы могут быть ужЕ сбалансированы). Можно считать, что дерево «подвешено» за свой текущий корень на красный крюк. Поворот состоит в «подвеске» дерева за другой узел (который станет новым корнем) на зелёный крюк и коррекции связей: к левой ветви нового корня проводится новая связь (показана зелёным) от старого корня (эта ветка будет новой правой веткой старого корня), связь от нового корня к его старой левой ветви рвётся (зачёркнуто зелёным), и связь между старым и новым корнями меняет направление (фактически существующая связь в одном направлении уже порвана, а в обратном направлении – проводится заново). В итоге дерево «поворачивается» вокруг новой точки подвески, откуда эта операция и получила своё название. После вращения в рассматриваемом случае высоты левой и правой ветвей нового корня будут одинаковыми.

Для выполнения операции вращения может потребоваться информация о текущем узле и связанных с ним узлах (его «родителе» и его «сыне»), т.е. адреса этих узлов в памяти. Или информация о текущем узле, его «отце» и «деде», или информация о текущем узле, его «сыне» и «внуке» (в зависимости от того, рассматривается дерево как ненаправленная структура данных, или как направленная).

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

Рисунок 4.14 – Преобразование дерева в «лозу». 1-й этап

Затем «лоза» преобразуется в сбалансированное дерево при помощи той же операции.

Рисунок 4.15 – Однократный правый поворот


Рисунок 4.16 – Начало преобразования «лозы» в дерево. 2-й этап


Рисунок 4.17 – Преобразование «лозы» в дерево. 3-й этап


Рисунок 4.18 – Завершение преобразования «лозы» в дерево.

Рекурсивная функция построения идеально сбалансированного дерева с заданным числом узлов на языке "Паскаль"

newnode: ptr;
newkey, nl, nr: integer;
if n_node = 0 then
newnode := nil
nl := n_node div 2;
nr := n_node — nl — 1; (* Ввод ключа и данных *)
read(newkey);
new(newnode);
with newnode^ do
begin
key := newkey;
left := maketree(nl);
right := maketree(nr)
read(n); (* Ввод числа узлов *)
tree := maketree(n); (* Первый вызов *)

4.3.3 Б-деревья

Б-деревья являются сбалансированными деревьями, у которых число ветвей, исходящих из узлов, может быть 2 и более. Узел, корневой для двух ветвей, содержит единственный ключ, а узел, корневой для нескольких ветвей, содержит составной ключ – несколько ключей, число которых на 1 меньше числа ветвей. Упрощенная архитектура Б-дерева показана на рисунке:

Рисунок 4.19 – Б-дерево

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

Существуют способы преобразования двоичного дерева в Б-дерево и наоборот.

Модификацией Б-дерева является Б+ дерево – Б-дерево, у которого терминальные узлы соединены в связный список (см. рисунок):

Рисунок 4.20 – Б+ дерево

Именно по такому принципу хранятся данные в базах данных по технологии Microsoft SQL Server.

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

В тех случаях, когда максимальное число ветвей, исходящих из узла, ограничено, пролучаются, например, 2-3-деревья и 2-3-4-деревья.

4.4 Многоключевые деревья

Б-деревья могут считаться частным случаем многоключевых деревьев (с переменным числом ключей). Ещё один такой частный случай – Декартово дерево. Это древовидная структура данных, в каждом узле которой содержится 2 ключа, по одному ключу она является двоичной пирамидой, а по второму ключу – двоичным деревом поиска.

Более простая ситуация – двухключевое дерево, которое является двоичным деревом поиска либо только по одному из ключей, либо по сумме ключей (именно в этом случае возможно повторение сумм ключей). Такое дерево может использоваться для описания рёбер графа. При этом также возможно повторение ключей в дереве, в зависимости от структуры графа.

Операции с такими двухключевыми деревьями ничем не отличаются от операций с обычными двоичными деревьями.

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

1. Что представляют собой древовидные структуры данных?
2. Какие существуют виды деревьев?
3. Что представляет собой двоичное дерево?
4. В чем заключается особенность дерева как структуры данных?
5. Опишите организацию связей в дереве.
6. Перечислите основные области применения деревьев.
7. Какие операции осуществляются над деревьями?
8. В чем преимущества использования деревьев?
9. Чем отличаются двоичные деревья от списков?
10. Изобразите структуру элемента двоичного дерева.
11. Чем отличаются: сбалансированное, несбалансированное и вырожденное двоичные деревья. Проиллюстрируйте рисунками.
12. Что означают термины «сбалансированное дерево» и «идеально сбалансированное дерево»?
13. Чем вырожденное дерево отличается от односвязного списка?
14. Перечислите основные способы прохождения двоичного дерева.
15. Почему рекурсивные функции наиболее эффективны при работе с деревьями?
16. Процедуры какого характера наиболее эффективны при работе с деревьями?
17. В чем заключается вставка узла в дерево?
18. В чем заключается удаление узла из дерева?
19. Проиллюстрируйте процесс удаления узла. Как действует алгоритм в каждом из трех возможных случаев?
20. Что такое высота дерева?
21. Как сохранить сбалансированность дерева при вставке и удалении узлов?
22. Чем отличается красно-чёрное дерево от АВЛ-дерева?
23. Каковы основные особенности красно-чёрного и АВЛ-дерева?
24. На каких структурах данных могут строится деревья?

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

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 21.12.2006

Репутация: нет
Всего: 2

Код

procedure kolvo(top: pnode; var k: integer); begin if top <> nil then begin kolvo(top^.left, k); inc(k); kolvo(top^.right, k); end; end;

Код

type people = record Name: string[NameL]; mark: real; end; massiv = array[1..200] of people; pmassiv = ^massiv;

Записать в него данные по возрастанию, уничтожить это дерево, и создать новое таким образом:
1. Корень дерева — элемент массива с номером (k div 2);
2. Левый сын — ((k div 2) div 2);
3. Правый сын — ((k div 2) div 2) + (k div 2);
4. Далее с каждым сыном поступаем так же, как с корнем.

У меня не получается реализовать этот алгоритм. Если кто знает как сбалансировать дерево (этим алгоритмом или другим) то прошу помочь.
Если же найдены ошибки в коде или алгоритме прошу исправить.

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 21.12.2006

Репутация: нет
Всего: 2

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!

• Название темы должно отражать её суть! (Не следует добавлять туда слова «помогите», «срочно» и т.п.)
• При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
• В названии темы не нужно указывать происхождение задачи (например «школьная задача», «задача из учебника» и т.п.), не нужно указывать ее сложность («простая задача», «легкий вопрос» и т.п.). Все это можно писать в тексте самой задачи.
• Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
• Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку «Код»). Не забывайте выбирать при этом соответствующий язык.
• Помните: один топик — один вопрос!
• В данном разделе запрещено поднимать темы , т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
• Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
• Если вопрос решён, то воспользуйтесь ссылкой «Пометить как решённый», которая находится под кнопками создания темы или специальным флажком при ответе.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)

0 Пользователей:

« Предыдущая тема | Центр помощи | Следующая тема »

[ Время генерации скрипта: 0.1039 ] [ Использовано запросов: 21 ] [ GZIP включён ]

Тема: Представление деревьев. Основные операции над деревом.

Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

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

Type TreeLink = ^Tree; Tree = Record Data : <тип данных>; Left, Right : TreeLink; End;

Корень дерева опишем в разделе описания переменных:

Var kd : TreeLink;

К основным операциям над деревьями относятся:

занесение элемента в дерево;

Рассмотрим вставку и обход дерева на примере следующей задачи.

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

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

Procedure InsTree(n : integer; Var t : TreeLink); Begin if t=nil then begin new(t); with t^ do begin Left := nil; Right := nil; Data := n; end; end; else if n<=t^.data then InsTree(n, t^.Left) else InsTree(n, t^.Right) End;

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

вывод числа, хранящегося в узле;

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

прямой вывод (сверху вниз);

Процедура обратного вывода дерева имеет следующий вид:

Procedure PrintTree(t : TreeLink); Begin if t<>Nil then begin PrintTree(t^.Left); Write(t^.Data:3); PrintTree(t^.Right); end; End;

Задание. Написать процедуры прямого и концевого вывода значений элементов дерева.

Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.

Begin writeln(‘Вводите вершины дерева. Окончание ввода – 0’); kd := nil; read(Digit); while Digit <> 0 do begin InsTree(Digit, kd); writeln(‘ Введите очередное число ‘); read(Digit); end; PrintTree(kd); End.

Задание. Напишите программу создания и вывода на экран двоичного дерева, используя свою процедуру вывода. Протестируйте программу и представьте учителю файл и листинг для оценки.

 
Похожие публикации:
1. Как добавить dsa в sshd linux
2. Как перенести почту outlook на другой компьютер
3. Ноутбук не перезагружается что делать
4. Что значит пустой массив