воскресенье, 19 сентября 2010 г.

Сортировка с помощью бинарного дерева (Tree_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика
: informatics.mccme.ru

Реализация:

В своей реализации эта сортировка использует структуру данных: бинарное дерево, каждый элемент которого можно описать следующим образом:
  1. struct tree
  2. {
  3.   tree* left; // левый сын
  4.   tree* right; // правый сын
  5.   int value// значение
  6. };
* This source code was highlighted with Source Code Highlighter.

Само бинарное дерево удобно формировать по мере поступления новых данных, например при считывании данных из файла или с консоли.

Каждый элемент дерева соответствует двум правилам:
1. Значение левого сына строго меньше значения родителя
2. Значение правого сына не меньше значения родителя

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

Проилюстрируем это следующими функциями:

  1. void add_to_tree(tree* &node, int value)
  2. {
  3.   if (node == NULL)
  4.   {
  5.     node = new tree(value);
  6.     return;
  7.   }
  8.   if (node->value > value)
  9.     add_to_tree(node->left,value);
  10.   else
  11.     add_to_tree(node->right,value);
  12. }
  13. void input_tree(tree* &root)
  14. {
  15.   cin>>n;
  16.   for (int i=0;i<n;i++)
  17.   {
  18.     scanf("%d",&value);
  19.     add_to_tree(root,value);
  20.   }
  21. }
* This source code was highlighted with Source Code Highlighter.

После того, как дерево сформировано, осталось вывести ответ.
Если организовать обход по правилу:
левый сын – родитель – правый сын
и последовательно выводить значения родителя, то получим отсортированный массив:

  1. void output_tree(tree* node)
  2. {
  3.   if (node == NULL)
  4.     return;
  5.   output_tree(node->left);
  6.   printf("%d ",node->value);
  7.   output_tree(node->right);
  8. }
* This source code was highlighted with Source Code Highlighter.

Полный исходник лежит здесь

Как видно на каждый элемент входного массива в дереве тратиться дополнительно 8 байт на указатели на сыновей. Этот дополнительный расход памяти делает этот метод менее привлекательным. Но тем не менее саму идею использования дерева можно применить в других прикладных задачах.

3 комментария:

  1. Данный метод без балансировки дерева будет квадратичным. Если взять например уже отсортированный массив или реверс отсортированный.

    ОтветитьУдалить
  2. Балансировку рассамотрим, когда будем разбирать работу с двоичным дерева поиска

    ОтветитьУдалить
  3. Замечание по поводу:
    Каждый элемент дерева соответствует двум правилам:
    1. Значение левого сына строго меньше значения родителя
    2. Значение правого сына не меньше значения родителя


    Не совсем так, правильнее: Корень больше любого элемента из левого поддерева и не больше любого элемента из правого поддерева.

    ОтветитьУдалить