|
====================================================================
> 7. Сортировка двоичным деревом, 'древесная сортировка'.
====================================================================
Двоичным(бинарным) деревом назовем упорядоченную структуру данных,
в которой каждому элементу - предшественнику или корню (под)дерева -
поставлены в соответствие по крайней мере два других элемента (преемника).
Причем для каждого предшественника выполнено следующее правило:
левый преемник всегда меньше, а правый преемник всегда больше или равен
предшественнику.
Вместо 'предшественник' и 'преемник' также употребляют термины
'родитель' и 'сын'. Все элементы дерева также называют 'узлами'.
При добавлении в дерево нового элемента его последовательно сравнивают
с нижестоящими узлами, таким образом вставляя на место.
Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
и так далее, пока есть сыновья, с которыми можно сравнить.
Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:
44 44 44 44 44
\ / \ / \ / \
55 12 55 12 55 12 55
\ \ \
42 42 94
(**) 44 44 (*) 44
/ \ / \ / \
12 55 12 55 12 55
\ \ / \ \ / \ \
42 94 06 42 94 06 42 94
/ / / /
18 18 18 67
Дерево может быть и более-менее ровным, как на (*), может и иметь всего
две основные ветви (**), а если входная последовательность уже отсортирована,
то дерево выродится в линейный список.
Если мы будем рекурсивно обходить дерево по правилу
"левый сын - родитель - правый сын", то, записывая все
встречающиеся элементы в массив, мы получим упорядоченное
в порядке возрастания множество. Hа этом и основана идея сортировки деревом.
Более подробно правило обхода можно сформулировать как
обойти левое поддерево - вывести корень - обойти правое поддерево,
где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается
с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.
/*********** сортировка с помощью двоичного дерева *************/
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
int a; // данные
struct tree *left; // левый сын
struct tree *right; // правый сын
} TREE;
TREE *add_to_tree(TREE *root, int new_value)
{
if (root==NULL) // если нет сыновей - создаем новый элемент
{
root = (TREE*)malloc(sizeof(TREE));
root->a = new_value;
root->left = root->right = 0;
return root;
}
if (root->a < new_value) // добавлем ветвь
root->right = add_to_tree(root->right, new_value);
else
root->left = add_to_tree(root->left, new_value);
return root;
}
void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
{
static max2=0; // счетчик элементов нового массива
if (root==NULL) return; // условие окончания - нет сыновей
tree_to_array(root->left, a); // обход левого поддерева
a[max2++] = root->a;
tree_to_array(root->right, a); // обход правого поддерева
free(root);
}
void sort_tree(int a[], int elem_total) // собственно сортировка
{
TREE *root;
int i;
root = NULL;
for (i=0; i<elem_total; i++) // проход массива и заполнение дерева
root = add_to_tree(root, a[i]);
tree_to_array(root, a); // заполнение массива
}
/* тестовая программа */
void main() {
int i;
/* Это будем сортировать */
int a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
sort_tree(a, 14);
printf("sorted array:\n");
for (i=0;i<14;i++) printf("%d ",a[i]);
}
Общее быстродействие метода O(nlogn). Поведение неестественно,
устойчивости, вообще говоря, нет.
Основной недостаток этого метода - большие требования к памяти
под дерево. Очевидно, нужно n места под ключи и, кроме того, память
на 2 указателя для каждого из них.
Поэтому TreeSort обычно применяют там, где
- построенное дерево можно с успехом применить для других задач.
- данные уже построены в 'дерево'. } не тратится
- данные можно считывать непосредственно в дерево. } лишняя
Hапример, при потоковом вводе с консоли или из файла. } память
Кроме того, ее элементы иногда используются в смежных задачах.
> Другое описание метода 'древесной сортровки' можно найти, например,
> у H. Вирта в книге 'Алгоритмы + Структуры Данных = Программы'.
Основное различие - строится не представление данных в виде дерева,
а 'дерево выбора'. С помощью n/2 сравнений можно определить
наименьший элемент из каждой пары, при помощи следующих n/4 -
наименьший из каждой пары таких наименьших ключей и т.д
При этом за n-1 сравнений мы можем построить дерево выбора, как
показано для чисел 44 55 12 42 94 18 06 67:
06 Это HЕ двоичное дерево в смысле,
/ \ определенном выше.
/ \ И это HЕ пирамида, используемая в HeapSort
/ \
/ \
/ \
/ \
12 06 Hа втором шаге мы спускаемся по
/ \ / \ пути, указанному наименьшим ключом
/ \ / \ и исключаем его, последовательно
/ \ / \ заменяя либо на 'дыру' (или ключ
44 12 18 06 'бесконечность'(БЕСК), либо на элемент,
/ \ / \ / \ / \ находящийся на противоположной
44 55 12 42 94 18 06 67 ветви промежуточного узла:
взяли ключ 06 сверху опять выбрали наименьший с учетом, что любой
БЕСК 12 ключ < БЕСК.
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
12 БЕСК 12 18
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
44 12 18 БЕСК 44 12 18 67
/ \ / \ / \ / \ / \ / \ / \ / \
44 55 12 42 94 18 БЕСК 67 44 55 12 42 94 18 БЕСК 67
Очевидно, требуется n операций на создание первоначального дерева,
а затем n шагов, каждый по log n сравнений для выбора нового наименьшего.
2
Такой вариант TreeSort довольно сильно отличается от изложенного выше.
Этот алгоритм еще называют 'выбор с замещением' и его можно неплохо
применять в тех же случаях, что и выше.
При этом он может быть даже выгоднее предыдущего метода,
хотя бы потому, что не нужно запоминать позицию, на которой мы остановились
при обходе дерева, т.е можно взять верхний элемент -> восстановить дерево ->
проделать некоторые операции -> взять следующий элемент и т.п.
Обходить же дерево удобно сразу целиком, либо какую-то его большую часть.
Кроме того, самой структура дерева выбора также может быть полезна.
Однако, нужно учесть, что памяти для дерева выбора нужно на
2n-1 элементов (элемент = ключ + указатели), в отличие от n элементов для
простого дерева.
Пример использования выбора с замещением можно увидеть в
многофазной сортировке (см соответствующий вопрос). Элементы обоих
'древесных' сортировок также используются в смежных
|
