Сортировка с помощью бинарного дерева

При обработке данных в ЭВМ важно знать и информаци­онное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка - это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значе­ния ключа от начала к концу в массиве.Различают следующие типы сортировок:• внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины• внешняя сортировка - сортировка во внешней памяти.Схематичное представление двоичного дерева: имеется набор вершин, соединенных стрелками. Из каждой вершины выходит не более двух стрелок (ветвей), направ­ленных влево - вниз или вправо - вниз. Должна существовать единственная вершина, в которую не входит ни одна стрелка - эта вершина называется корнем дерева. В каждую из остав­шихся вершин входит одна стрелка.

Существует множество способов упорядочивания дерева. Рассмотрим один из них: «Левый» сын имеет ключ меньше, чем ключ "Отца" "Правый" сын имеет ключ больше, чем ключ «Отца»Получили бинарное упорядоченное дерево с минималь­ным числом уровней. Строго сбалансированное дерево: дерево, в котором ле­вое и правое поддерево имеют уровни, отличающиеся не более чем на единицу. Рассмотрим принцип построения дерева при занесении элементов в массив:Пусть в первоначально пустой массив заносятся последо­вательно поступающие элементы: 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86; Т.к. это еще пустое дерево, то ссылки left и right равны nil (left - указатель на левого сына (элемент), right - указатель на правого сына (элемент)).

Четвертый из поступающих элементов 87. Т.к. этот ключ больше ключа 70 (корень), то новая вершина должна раз­мещаться на правой ветви дерева. Чтобы определить ее ме­сто, спускаемся по правой стрелке к очередной вершине (с ключом 85), и если поступивший ключ больше 85, то новую вершину делаем правым сыном вершины с ключом 85.

В рассмотренном примере ПРИНЦИП ПОСТРОЕНИЯ ДЕРЕВА имеет следующий вид: если поступает очередной элемент массива, то начиная с корня дерева (в зависимости от сравнения текущего элемента с очередной вершиной) идем влево или вправо от нее до тех пор, пока не найдем подходя­щую вершину, к которой можно подключить новую вершину с текущим ключом. В зависимости от результата сравнения ключей, новую вершину делаем левой или правой для най­денной вершины.

Алгоритм

Для создания дерева необходимо создать в памяти эле­мент следующего типа:

Тип на ПАСКАЛе:

type pelem = ^еlem;

elem = record

left: pointer;

right: pointer;

К: integer;

end;

К - элемент массива, V - указатель на созданный элемент.

В процедуре создания дерева бинарного поиска будут ис­пользованы следующие указатели:

tree - указатель на корень дерева;р - рабочий указатель;q - указатель отстающий на шаг от р;key - новый элемент массива;Создание дерева бинарного поиска

(псевдокод)

writeln(' Введите элемент массива ');readln(key); tree:=maketree(key); p:=tree; while not eof do begin readln(key); v:=maketree(key); while p<>nil do begin

q:=P; if key<k(p) then p:=left(p) else p:=right(p); end; if p=nil then begin writeln('Это корень'); tree:=v; end else if key<k(q) then left(p):=v else righ(p):=v; end;

При обходе дерева слева - направо получаем отсортиро­ванный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).

Обход дерева слева - направо

procedure InTree(tree);

begin if Tree = nil then writе('Дерево пусто') else with Tree^ do begin if left <> nil then InTree(left); if right <> nil then InTree(right); end; end;