Нелинейная организация данных

Алгоритм построения упорядоченного бинарного дерева. Нелинейные списковые структуры данных. Методы ускоренного доступа к данным. Организация записей в соответствии с адресной функцией. Способы организации индексируемого массива. Организация записей.
Краткое сожержание материала:

Размещено на

1. Нелинейная организация данных

1.1 Древовидная организация данных

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

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

1. Первая запись массива с ключом А₁ становится корнем дерева;

2. Значение ключа второй записи А₂ сравнивается с А₁, находящемся в корне дерева;

3. Если А₂ < А₁, то вторая запись помещается на левой от корня ветви, в противном случае - на правой ветви;

4. Далее на каждом шаге создается упорядоченное дерево из первых i записей;

5. Выбор места i-й записи массива в дереве производится следующим образом. Ключ А_i сравнивается с корневым значением и выполняется переход по левому адресу, если А₁ > А_i. Если А₁ А_i, то по правому адресу. Ключ, записанный по этому адресу, сравнивается с А_i, и снова организуется переход по левому или правому адресу до нахождения свободного места. Если требуемый адрес не заполнен, то он должен адресовать запись с ключом А_i.

Задание 1. Построить упорядоченное бинарное дерево со следующими значениями ключевых признаков и подравнять их (приложить подробный протокол подравнивания со всеми итерациями и описаниями их): 62, 30, 70, 85, 35, 96, 26, 18, 47, 66, 42, 34, 71, 54, 93.

Построим упорядоченное бинарное дерево для записей с ключевыми признаками: 62, 30, 70, 85, 35, 96, 26, 18, 47, 66, 42, 34, 71, 54, 93 (рис. 2.1).

Упорядоченное бинарное дерево построено следующим образом:

1. Первая запись с ключом 62 становится корнем дерева;

2. Значение ключа второй записи 30 сравнивается с 62 (30 < 62), запись помещаем на левой от корня ветви;

3. Далее сравниваем ключ третей записи 70 с коревым значением 62 (70 > 62), запись помещаем на правой от корня ветви;

Рисунок 2.1 - Упорядоченное бинарное дерево

4. Сравниваем ключ 85 с коревым значением 62 (85 > 62), выполняется переход по правому адресу, далее сравниваем значение 85 со значением 70 (85 > 70), запись помещаем на правой ветви;

5. Сравниваем ключ 35 с коревым значением 62 (35 < 62), выполняется переход по левому адресу, далее сравниваем значение 35 со значением 30 (35 > 30), запись помещаем на правой ветви;

6. Сравниваем ключ 96 с коревым значением 62 (96 > 62), выполняется переход по правому адресу, далее сравниваем значение 96 со значением 70 (96 > 70), выполняется переход по правому адресу, далее сравниваем значение 96 со значением 85 (96 > 85), запись помещаем на правой ветви;

7. Сравниваем ключ 26 с коревым значением 62 (26 < 62), выполняется переход по левому адресу, далее сравниваем значение 26 со значением 30 (26 < 30), запись помещаем на левой ветви;

8. Сравниваем ключ 18 с коревым значением 62 (18 < 62), выполняется переход по левому адресу, далее сравниваем значение 18 со значением 30 (18 < 30), выполняется переход по левому адресу, сравниваем значение 18 со значением 26 (18 < 26), запись помещаем на левой ветви;

9. Сравниваем ключ 47 с коревым значением 62 (47 < 62), выполняется переход по левому адресу, далее сравниваем значение 47 со значением 30 (47 > 30), выполняется переход по правому адресу, сравниваем значение 47 со значением 35 (47 > 35), запись помещаем на правой ветви;

10. Сравниваем ключ 66 с коревым значением 62 (66 > 62), выполняется переход по правому адресу, далее сравниваем значение 66 со значением 70 (66 < 70), запись помещаем на левой ветви;

11. Сравниваем ключ 42 с коревым значением 62 (42 < 62), выполняется переход по левому адресу, далее сравниваем значение 42 со значением 30 (42 > 30), выполняется переход по правому адресу, сравниваем значение 42 со значением 35 (42 > 35), выполняется переход по правому адресу, сравниваем значение 42 со значением 47 (42 < 47), запись помещаем на левой ветви;

12. Сравниваем ключ 34 с коревым значением 62 (34 < 62), выполняется переход по левому адресу, сравниваем значение 34 со значением 30 (34 > 30), выполняется переход по правому адресу, сравниваем значение 34 со значением 35 (34 < 35), запись помещаем на левой ветви;

13. Сравниваем ключ 71 с коревым значением 62 (71 > 62), выполняется переход по правому адресу, далее сравниваем значение 71 со значением 70 (71 > 70), выполняется переход по правому адресу, далее сравниваем значение 71 со значением 85 (71 < 85), запись помещаем на левой ветви;

14. Сравниваем ключ 54 с коревым значением 62 (54 < 62), выполняется переход по левому адресу, далее сравниваем значение 54 со значением 30 (54 > 30), выполняется переход по правому адресу, сравниваем значение 54 со значением 35 (54 > 35), выполняется переход по правому адресу, сравниваем значение 54 со значением 47 (54 > 47), запись помещаем на правой ветви;

15. Сравниваем ключ 93 с коревым значением 62 (93 > 62), выполняется переход по правому адресу, далее сравниваем значение 93 со значением 70 (93 > 70), выполняется переход по правому адресу, далее сравниваем значение 93 со значением 85 (93 > 85), выполняется переход по правому адресу, сравниваем значение 93 со значением 96 (93 < 96), запись помещаем на левой ветви.

На рисунке 2.1 записи со значениями 62, 30, 70, 35, 85, 47 являются полными, т. к. у них заполнены два адреса связи; записи со значениями 26, 96 с одним адресом - неполные; записи 18, 34, 42, 54, 66, 71, 93 с двумя незаполненными адресами - концевые.

Ранг данного упорядоченного дерева равен 5, т. к. количество уровней в дереве 5.

Ранг упорядоченного бинарного дерева можно сократить с помощью специальных преобразований - подравниваний. Если для некоторой записи длины ее ветвей различаются не более чем на единицу, то она называется сбалансированной. Бинарное дерево называется подравненным, если все его записи являются сбалансированными. Для того чтобы подравнять бинарное дерево необходимо для каждой несбалансированной записи найти соседнюю слева запись, если у нее левая ветвь длиннее правой, или найти соседнюю справа запись, если правая ветвь длиннее. Найденная соседняя запись помещается на место несбалансированной, а сама несбалансированная запись заново включается в дерево.

В упорядоченном бинарном дереве (рис. 2.1), несбалансированной записью является запись 70, т. к. у этой вершины разница ветвей равна 2 (длина левой ветви равна 1, длина правой ветви - 3, следовательно, 3 - 1 = 2). Все остальные вершины являются сбалансированными.

1 итерация. Подравняем вершину со значением 70. На место вершины 70 ставим вершину со значением 85 вместе со всеми вытекающими из нее вершинами (71, 96, 93), далее перераспределяем вершину 66, затем перераспределяем вершину 70 (рис. 2.2).

Рисунок 2.2 - Подравнивание вершины 70

2 итерация. На рисунке 2.2, видно, что несбалансированной записью является запись 71, т. к. у этой вершины разница ветвей равна 2 (длина левой ветви равна 2, длина правой ветви - 0, следовательно, 2 - 0 = 2). Все остальные вершины являются сбалансированными.

Подравняем вершину. На место вершины 71 ставим вершину со значением 66 вместе с вытекающей из нее вершиной 70, далее перераспределяем вершину 71 (рис. 2.3).

Рисунок 2.3 - Подравнивание вершины 71

3 итерация. Из рисунка 2.3, видно, что несбалансированной записью является запись 66, у этой вершины разница ветвей равна 2 (длина левой ветви равна 0, длина правой ветви - 1, следовательно, 2 - 0 = 2). Все остальные вершины являются сбалансированными.

Выполним подравнивание вершины. На место вершины 66 ставим вершину со значением 70 вместе с вытекающей из нее вершиной 71, далее перераспределим вершину 70 (рис. 2.4).

Рисунок 2.4 - Подравнивание вершины 66

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

Рисунок 2.5 - Итоговое подравненное бинарное дерево

Задание 2. Проставить в вершинах бинарного дерева ключевые признаки от 1 до 12 так, чтобы дерево стало упорядоченным (подравнивать не надо) (рис. 2.6).



Рисунок 2.6 - Пример головоломки

Проставляя в вершинах б...