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

Основные понятия
Двоичные деревья – обычный способ хранения и обработки информации в компьютерных программах.
Алгоритм добавления нового элемента в такой тип деревьев представляет собой следующее: начиная с корня дерева по очереди производится сравнение значения всех узлов со значением нового элемента.

Рис. 1. Упорядоченный список: 1, 2, 4, 6, 7, 9
Рис. 2. Упорядоченный список: 1, 2, 4, 6, 7, 8, 9

procedure InsertItem(var node: PSortNode; new_value: Integer);
begin
if (node = nil) then
begin // Достигли листа.
// Вставка элемента в этом месте.
GetMem(node, SizeOf(TSortNode));
node^.Value := new_value;
end
else
if (new_value <= node^.Value) then
begin
// Левая ветвь.
InsertItem(node^.LeftChild,new_value);
end
else begin
// Правая ветвь.
InsertItem(node^.RightChild, new_value);
end; end;
Если вызванная процедура изменяет значение параметра node, в вызывающей процедуре указа­тель на потомка также автоматически обновляется, что добавляет созданный но­вый узел к дереву.
InsertItem(node^.RightChild,new_value);

Симметричный обход упорядоченных деревьев
Алгоритм сортировки:
1. В сортированное дерево добавляется элемент.
2. Элементы выводятся с помощью симметричного обхода.
8
4
9
2
7
5
6
Рис. 3. Симметричный обход сортированного дерева: 2, 4, 5, 6, 7,8,9

Обход упорядоченных деревьев
1
6
5
2
3
4
При добавлении элементов в каком-либо определенном порядке, дерево может стать длинным и тонким.
Рис. 4. Дерево, образованное при добавлении элементов в порядке 1, 6, 5, 2, 3, 4