Математическая логика и теория алгоритмов. Стенюшкина В.А. - 77 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

4.2.2 Сортировка с помощью двоичного (бинарного) дерева
Бинарное дерево – ациклический граф с выделенной вершиной (корнем),
у которой нет предшественников. Адрес корня – 1.Любая другая вершина имеет
Рисунок 4.1
только одного предшественника и одного или двух преемников. (рисунок 4.1).
Для каждой вершины k, k=1…n, могут быть вычислены адреса предшест-
венников и преемников по формулам:
- для родителей х(k) =k\2, k=1… n;
- для потомков слева у(k)= 2k, k=1…(n\2), y
k
=0, k> (n\2),
- для потомков справа z(k)= 2k+1, k=1…((n-1)\2), z(k)= 0, k > (n-1)\2.
Нумерация вершин (адресация) идет по уровням (сверху–вниз, слева–
направо).
Сортировка с помощью бинарного дерева выполняется следующим обра-
зом. Элементы массива помещаем в вершины нижнего уровня (рисунок 4.2).
Первый этап – построение дерева. На первом шаге попарным сравнением
надстраиваем уровень дерева и помещаем в вершины – родители меньшие эле-
менты пары потомков. На втором шаге надстраиваем очередной уровень дере-
ва (по аналогичному правилу) и т.д. В результате построения дерева его корнем
будет минимальный элемент.
Второй этап – собственно сортировка. Объявляем число µ в корне дерева
очередным элементом сортированного массива и спускаемся в дереве Д по обо-
значенному им пути. Если путей несколько, выбираем тот, который включает
потомков слева. Заменяем в нижнем уровне µ на +∞ и выполняем пересчет вер-
хних уровней с учетом замены. Результат пересчета показан на рисунке 4.3.
После n-кратного выполнения этапа 2 дерево D будет состоять из значений +∞,
и процесс сортировки закончится. Для однократного выполнения второго этапа
требуется выполнить log n сравнений. Поэтому общая трудоемкость сортиров-
ки составляет O(n log n) операций.
Уровень 0
Уровень 1
Уровень 2
Уровень 3
        4.2.2 Сортировка с помощью двоичного (бинарного) дерева

       Бинарное дерево – ациклический граф с выделенной вершиной (корнем),
у которой нет предшественников. Адрес корня – 1.Любая другая вершина имеет


                                                                    Уровень 0

                                                                    Уровень 1

                                                                    Уровень 2



                                                                    Уровень 3


                                Рисунок 4.1

только одного предшественника и одного или двух преемников. (рисунок 4.1).
      Для каждой вершины k, k=1…n, могут быть вычислены адреса предшест-
венников и преемников по формулам:
      - для родителей х(k) =k\2, k=1… n;
      - для потомков слева у(k)= 2k, k=1…(n\2), yk=0, k> (n\2),
      - для потомков справа z(k)= 2k+1, k=1…((n-1)\2), z(k)= 0, k > (n-1)\2.
      Нумерация вершин (адресация) идет по уровням (сверху–вниз, слева–
направо).
      Сортировка с помощью бинарного дерева выполняется следующим обра-
зом. Элементы массива помещаем в вершины нижнего уровня (рисунок 4.2).
      Первый этап – построение дерева. На первом шаге попарным сравнением
надстраиваем уровень дерева и помещаем в вершины – родители меньшие эле-
менты пары потомков. На втором шаге надстраиваем очередной уровень дере-
ва (по аналогичному правилу) и т.д. В результате построения дерева его корнем
будет минимальный элемент.
      Второй этап – собственно сортировка. Объявляем число µ в корне дерева
очередным элементом сортированного массива и спускаемся в дереве Д по обо-
значенному им пути. Если путей несколько, выбираем тот, который включает
потомков слева. Заменяем в нижнем уровне µ на +∞ и выполняем пересчет вер-
хних уровней с учетом замены. Результат пересчета показан на рисунке 4.3.
После n-кратного выполнения этапа 2 дерево D будет состоять из значений +∞,
и процесс сортировки закончится. Для однократного выполнения второго этапа
требуется выполнить log n сравнений. Поэтому общая трудоемкость сортиров-
ки составляет O(n log n) операций.

Страницы