Delphi World - Сортировка двоичным деревом - древесная сортировка
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Сортировка двоичным деревом - древесная сортировка

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

  При добавлении в дерево нового элемента его последовательно сравнивают
с нижестоящими узлами, таким образом вставляя на место.
  Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
и так далее, пока есть сыновья, с которыми можно сравнить.

 Вот процесс построения дерева из последовательности 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 элементов для 
простого дерева. 
   
  Пример использования выбора с замещением можно увидеть в
многофазной сортировке (см соответствующий вопрос). Элементы обоих 
'древесных' сортировок также используются в смежных 
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования