Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Сортировка / FAQ /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Сортировка двоичным деревом, древесная сортировка. - Программирование от RIN.RU
Сортировка двоичным деревом, древесная сортировка.

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


Вместо 'предшественник' и 'преемник' также употребляют термины 'родитель' и 'сын'. Все элементы дерева также называют 'узлами'. При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом вставляя на место. Если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить. Вот процесс построения дерева из последовательности 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
#include
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 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 сравнений для выбора нового наименьшего.


Такой вариант TreeSort довольно сильно отличается от изложенного выше. Этот алгоритм еще называют 'выбор с замещением' и его можно неплохо рименять в тех же случаях, что и выше. При этом он может быть даже выгоднее предыдущего метода, хотя бы потому, что не нужно запоминать позицию, на которой мы остановились при обходе дерева, т.е можно взять верхний элемент -> восстановить дерево -> проделать некоторые операции -> взять следующий элемент и т.п. Обходить же дерево удобно сразу целиком, либо какую-то его большую часть. Кроме того, самой структура дерева выбора также может быть полезна.


Однако, нужно учесть, что памяти для дерева выбора нужно на 2n-1 элементов (элемент = ключ + указатели), в отличие от n элементов для простого дерева.


Пример использования выбора с замещением можно увидеть в многофазной сортировке (см соответствующий вопрос). Элементы обоих 'древесных' сортировок также используются в смежных.



 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
По материалам: Эмери: игрокам "Валенсии есть над чем поработать. . По материалам: Причина отмены трансляции матча "Торпедо" - "Крылья" на данный момент неизвестна.