6.3. Впорядкування файла бінарним деревом

Алгоритм впорядкування файла лінійним списком використовує послідовний пошук місця елемента. Як зазначено у п. 3.4, ефективнішим є пошук місця за допомогою методу поділу відрізка навпіл (програма binary Insert). Виграш особливо відчутний для послідовностей великих розмірів, а файли, зазвичай, є досить великими.

З метою реалізації бінарного пошуку використовують двійкове дерево (визначення дерева та опис алгоритмів їхньої обробки див. у п. 10.3). кожна вершина якого містить унікальний ключ, причому для кожної вершини правильним є твердження про те, що ліве її піддерево містить лише вершини з меншими ключами, а праве - з більшими. Таке дерево називають деревом пошуку. Необхідний ключ можна знайти, скориставшись алгоритмом бінарного пошуку: якщо шуканий ключ менший за ключ у корені, то пошук продовжують у лівому піддереві; якщо більший, — то у правому; якщо рівний, то елемент знайдено; в іншому випадку знайдено місце для нового елемента, його необхідно долучити до дерева. Час виконання цього алгоритму є величиною порядку 0(log₂n), де n — кількість ключів у дереві.

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

program sortByTree;

type fileRec=record key:integer;

{. . . ВСІ ІНШІ ПОЛЯ . . . }

end;{fileRec}

dataBase=file of fileRec; tree=^node; {дерево}

node=record elem:fileRec; {вершина дерева містить запис,}

left,right:tree end; {поля зв'язку з піддеревами.}

procedure searchAndlnclude (x: fileRec; var t:tree); { процедура searchAndlnclude виконує пошук з } { включенням запису х у дереві t }

begin if t=nil then {запис не знайшли, включаємо його в дерево)

begin t:=new(tree); with t^ do

begin elem:=x; left:=nil; right:=nil end {witn} end {then} else with t^ do {шукаємо в непорожньому дереві:}

if x.key<elem.key then {менший ключ - ліворуч,}

searchAndlnclude(x,left) else {більший - праворуч.}

searchAndlnclude(х,right)

end; {searchAndlnclude}

procedure writeTree(var f:dataBase; t:tree); { процедура writeTree записує непорожнє дерево t } { у файл f, виконуючи лівосторонній обхід. }

begin with t^ do

begin if left<>nil then writeTree (f, left) ; {друкуємо ліве} write(f,elem); {піддерево, потім - корінь,}

if righf<>nil then writeTree(f,right) {а тоді - праве.}

end {wi th}

end;{writeTree}

var f:dataBase; fіleName:string; {змінні для приєднання до}

{заданого зовнішнього файла} x:fileRec; t:tree; {будуватимемо дерево Т)

Begin write('Введіть ім'я файла: '); readln(fileName);

assign (f, filename) ; reset(f); {відкрили файл}

t:=nil; {дерево спочатку порожнє}

while not EoF(f) do {читаємо і вставляємо всі слова}

begin read(f,x); searchAndlnclude(x, t)

end;{while дерево готове!)

seek(f , 0) ;writeTree(f,t); {тепер перезапишемо файл}

close(f)

End.

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