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