Подання бінарного дерева в прямокутній пам’яті

При поданні дерева в прямокутній пам’яті одне з полів R_Son або L_Son видаляється, тому що необхідність у ньому відпадає. Нащадок може розміщуватися поруч, тобто в безпосередній близькості. Щоб довідатися, чи є нащадок, уводиться додаткове поле L або R. Нехай, наприклад, відсутній лівий нащадок. Уведемо наступні змінні:

index = 0..max;

type Element = record

R_Son: index;

Data: BaseType;

L: boolean;

end;

var Tree = array [index] of Element;

R_Son Data L

а

b

c

f

g

D

e

h

T

F

T

F

F

Порядок називається прямим, якщо відсутнє ліве піддерево. Якщо ж відсутнє праве піддерево, то такий порядок називається фамільним.

6.1.8. Застосування бінарних дерев

1. Дерево Хафмана – двійкове дерево, листям якого є символи алфавіту, в кожній вершині якого зберігається частота символу (для листа) або сума частот його двох нащадків (називатимемо це число вагою вершини). При цьому виконується властивість: якщо відстань від кореня до вершини X більша, ніж до вершини Y, то вага X не перевищує вагу Y. Один із способів застосування дерев Хафмана – алгоритми кодування (архівування) інформації (детальніше див. розділ 10.3.3).

Код змінної довжини символа (змінний код у дереві Хафмана)– послідовність бітів, яку отримуємо при проходженні по ребрах від кореня до вершини із цим символом, якщо зіставити кожному ребру значення 1 або 0. У дереві Хафмана ребрам, що виходять із вершини до її нащадків присвоюються різні значення (вважатимемо далі, що ребро з 1 – ліве, а з 0 – праве).

Статичний метод Хафмана передбачає, що частоти символів алфавіту наперед відомі. Для цього, перш ніж почати стискання файла, програма проходить файлом і підраховує, який символ скільки разів зустрічається. Потім, відповідно до ймовірності появи символів, будується двійкове дерево Хафмана, з нього отримуються відповідні кожному символу коди змінної довжини. Нарешті, знову здійснюється проходження початковим файлом, при цьому кожен символ замінюється на свій код у дереві. Отже, статичному алгоритму потрібні два проходи по файлу-джерелу, щоб закодувати дані.

Статичний алгоритм:

{ Iніціалізуємо двійкове дерево}

InitTree;

For i:=0 to Length(CharCount)

{ Iніціалізуємо масив частот елементів алфавіту}

CharCount[i]:=0;

{Запускаємо перше проходження файлу}

While not EOF(Файл-джерело)

Begin

{Читаємо активний символ}

Read(Файл-джерело, C);

{Збільшуємо частоту його появи}

CharCount[C]= CharCount[C]+1;

End;

{За отриманими частотами будуємо двійкове дерево}

ReBuildTree;

WriteTree (Файл-приймач) {Записуємо у файл двійкове дерево}

{Запускаємо друге проходження файлу}

While not EOF(Файл-джерело)

Begin

Read(Файл-джерело, C); {Читаємо поточний символ}

{Запускаємо другий прохід файлу}

code=FindCodeInTree(C);

write(Файл-приймач, code); {Записуємо послідовність бітів у файл}

End

Процедура InitTree ініціалізує двійкове дерево, онулюючи значення, ваги, і вказівники на батька і нащадків активного листка. Далі виконується перший прохід по джерелу даних з метою перевірки частотності символів, результати якого запам'ятовуються у масив CharCount. Розмірність цього масиву повинна дорівнювати кількості елементів алфавіту джерела. У загальному випадку, для стискання заданого комп'ютерного файлу його довжина повинна становити 256 елементів. Потім, відповідно до отриманого набору частот,будуємо двійкове дерево ReBuildTree. Під час другого проходу перекодуємо джерело відповідно до дерева і записуємо одержані послідовності бітів у стиснутий файл. Для того, щоб мати можливість відновити стиснуті дані, необхідно в отриманий файл зберегти копію двійкового дерева WriteTree.

Динамічний алгоритм:

{ Iніціалізуємо двійкове дерево}

InitTree;

For i:=0 to Length(CharCount)

{ Iніціалізуємо масив частот елементів алфавіту}

CharCount[i]:=0;

{ Запускаємо проходження файлу}

While not EOF(Файл-джерело)

Read(Файл-джерело, C); {Читаємо активний символ}

If C немає в дереві then {Перевіряємо чи зустрічався символ раніше}

Code:=Код "порожнього" символу & Asc(C)

{Якщо ні, тo запам'ятовуємо код порожнього листка і ASCII код активного символу}

{ Інакше запам'ятовуємо код активного символу}

else

code:=Код C;

{Записуємо послідовність бітів у файл}

write(Файл-приймач, code);

{ Оновлюємо двійкове дерево символом}

ReBuildTree(С);

End;

Динамічний алгоритм дозволяє реалізувати однопрохідну модель стискання. Не знаючи реальної ймовірності появи символів у початковому файлі, програма поступово змінює двійкове дерево, з кожним символом, що зустрічається, збільшуючи частоту його появи e дереві та перебудовуючи зв’язки у самому дереві. Проте, стає очевидним, що, вигравши в кількості проходжень початковим файлом, ми втрачаємо у стисканні, оскільки у статичному алгоритмі реальні частоти символів були відомі із самого початку і довжини кодів цих символів ближчі до оптимальних, тоді як динамічний метод, вивчаючи джерело, поступово доходить до його реальних частотних характеристик. Але, оскільки динамічне двійкове дерево постійно модифікується новими символами, немає необхідності запам’ятовувати їх частоти заздалегідь – при розархівуванні програма, отримавши з архіву код символа, так само відновить дерево, як вона це робила при стисканні, і збільшить на одиницю частоту символа.

2. Будь-який алґебраїчний вираз містить змінні, числа, знаки операцій і дужки можна подавати у вигляді бінарного дерева (виходячи з бінарності цих операцій). При цьому знак операції міститься в корені, перший операнд – у лівому піддереві, а другий операнд – у правому. Дужки при цьому опускаються. У результаті всі числа й змінні виявляться в листках, а знаки операцій – у внутрішніх вузлах.

Розглянемо приклад: 3 (x – 2) + 4.

Звичною формою виразів є інфіксна, коли знак бінарної операції записується між позначеннями операндів цієї операції, наприклад, x-2. Розглянемо запис знаків операцій після позначень операндів, тобто постфіксний запис, наприклад, x 2 -. Такий запис має також назву зворотного польського, оскільки його запропонував польський логік Ян Лукасевич.

Сформулюємо правило обчислення значень виразу у інфіксному записі: вираз проглядається справа наліво, виділяються перші 2 операнди перед операцією, ця операція виконується, і її результат – це новий операнд.

Правило обчислення значення виразу в зворотному польському записі: вираз проглядається зліва направо, виділяються перші 2 операнди перед операцією, ця операція виконується, і її результат – це новий операнд.

Запис виразу в інфіксній формі: 4 + 3 * х – 2.

Запис виразу в зворотному польському записі: 4 3 х 2 - * +.

Алгоритм обходу зверху вниз:

Алгоритм обходу знизу вверх:

3. Класична програма із класу інтелектуальних: побудова дерев рішень. У цьому випадку не листкові (внутрішні) вузли містять предикати – запитання, відповіді на які можуть приймати значення “так” або “ні”. На рівні листків перебувають об’єкти (альтернативи, за допомогою яких розпізнаються програми). Користувач одержує запитання, починаючи з кореня, і, залежно від відповіді, спускається або на ліве піддерево, або на праве. Таким чином він виходить на той об’єкт, що відповідає сукупності відповідей на зппитання.

6.2. Види бінарних дерев

6.2.1. Збалансоване дерево

У програмуванні збалансоване дерево в загальному розумінні цього слова – це такий різновид бінарного дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем, мінімальною. Ця властивість є важливою тому, що час виконання більшості алгоритмів на бінарних деревах пошуку пропорційний до їхньої висоти, і звичайні бінарні дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях. Процедура зменшення (балансування) висоти дерева виконується за допомогою трансформацій, відомих як обернення дерева, в певні моменти часу (переважно при видаленні або додаванні нових елементів).

Більш строге визначення збалансованих дерев було дане Г.Адельсон-Вельським та Є.Ландісом. Ідеально збалансованим деревом за Адельсон-Вельським та Ландісом є таке, у якого для кожної вершини різниця між висотами лівого та правого піддерев не перевищує одиниці. Однак, така умова доволі складна для виконання на практиці і може вимагати значної перебудови дерева при додаванні або видаленні елементів.

Тому було запропоноване менш строге визначення, яке отримало назву умови АВЛ(AVL)-збалансованості і говорить, що бінарне дерево є збалансованим, якщо висоти лівого та правого піддерев різняться не більше ніж на одиницію. Дерева, що задовольняють такі умови, називаються AVL-деревами. Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-збалансованим, але не навпаки.

Наведемо програму додавання та знищення елемента у збалансованому дереві.

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; {h = false}

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.

6.2.2. Червоно-чорне дерево

Червоно-чорне дерево (англ. Red-black tree, RB tree) –різновид бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний). Точнішим є таке визначення: червоно-чорні дерева – різновид збалансованих дерев, в яких за допомогою спеціальних трансформацій ґарантується, що висота дерева h не буде перевищувати (log n). Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є (h), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.

Дата добавления: 2014-01-05