Сортування злиттям

Злиття означує об'єднання двох або більше послідовностей (масивів) в одну впорядковану послідовність.

Розглянемо більш детально алгоритм двохшляхового злиття.

Дано два впорядкованих масиви x_i , i=1, n, y_j , j=1, m. Отримати масив Z_k, k=1, n+m.

1. Визначаємо найменший елемент x_i і y_j .
2. Порівнюємо найменші елементи і обраний найменший елемент записуємо в Z, виключаючи його з відповідного масиву (наприклад x_i ).
3. Відшукуємо новий min у масиві x_i і порівнюємо його з min y_j .
4. Записуємо обраний min в Z і виключаємо його з відповідного масиву, і т.д. поки всі елементи x_i й y_j не будуть записані в Z.

Методи роботи з структурами «дерево»

 

Структура „дерево” є узагальненням лінійного списку. В списку кожен вузол має показник на другий вузол. В дереві, кожен вузол містить декілька показників на декілька вузлів. Якщо показника два (правий і лівий), таке дерево називається бінарним. Один із показників може бути рівним Nil. Якщо правий і лівий показник рівний Nil , такій вузол називається лист. Початкова точка дерева називається кореневим вузлом.

У кореневого вузла немає гілок які в нього входять, є тільки ті, що виходять з нього. Вершина, до якої виходить показник із другої вершини, називається потомком цієї вершини. Вершина, із якої виходить показник до другої вершини, називається предком.

Приклад структури «дерево».

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

 

Основні операції над елементами дерева :

 

1. Занесення елементів в дерево.

2. Видалення елементів з дерева.

3. Обхід дерева.

 

Приклад опису структури «дерево»:

 

type tree = ^elem ; { показник на елемент дерева }

elem = record

info : integer; { інформаційне поле елемента дерева }

left : tree; { адресне поле елемента дерева – показник на лівого потомка }

right : tree; { адресне поле елемента дерева – показник на правого потомка }

end;

var beg : tree ; { показник на кореневий елемент (вузол) дерева }

 

 

Далі розглянемо основні операції зі структурою «дерево».