8.4. Деревья, упорядоченные в глубину

Упорядочение в глубину #

Упорядочение значений в дереве может быть произведено в глубину (условно говоря, по вертикали): значение в каждой вершине меньше, чем значения у прямых потомков. Рекурсивное применение такого утверждения приводит к тому, что в каждой вершине находится минимальное значение из всего подчиненного ей поддерева. Такое размещение данных позволяет предполагать, что их можно получить в порядке возрастания. Однако ни рекурсивный обход, ни «горизонтальный» (с использованием очереди) для этих целей не подходят. Такую возможность дает алгоритм рекурсивного слияния значений из вершин дерева с замещением «ушедших» значениями потомков. Аналогично, построение дерева производится путем вытеснения больших значений меньшими при их прохождении через промежуточные вершины. Во всех случаях выбор направления дальнейшего движения алгоритма производится в сторону потомка с меньшим значением.

Построение дерева, упорядоченного в глубину #

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

• алгоритм основывается на ветвлении: выполнение его для корневой вершины сопровождается выбором потомка, для которого алгоритм повторяется линейно - рекурсивно или циклически;

• «замещение»: если новое значение меньше, чем значение в текущей вершине, то оно вытесняет последнее, занимая его место. Вытесненное значение участвует в последующем погружении вместо нового. Заметим, что такой процесс не нарушает свойства упорядоченности дерева в глубину;

• для продолжения алгоритма может быть выбран любой потомок. Если выбирать потомка с минимальным количеством вершин в поддереве, то в процессе его построения будет поддерживаться его сбалансированность;

• для реализации предыдущего положения каждая вершина должна содержать счетчик вершин в поддереве, который будет увеличиваться при вставке каждого нового значения в поддерево.

//------------------------------------------------------84-01.cpp

//------- Дерево, упорядоченное в глубину.

// Построение дерева - вытеснение в поддерево

// с минимальным количеством вершин

struct vtree{

            int val;                           // значение

            vtree *l,*r;                      // потомки

            int cnt;                          // счетчик вершин

};

                                                // Ссылка на указатель

void insert(vtree *&p, int v){          // на текущую вершину

 if (p==NULL){                            // Найдено свободное место

            p=new vtree;                  // Создать новую вершину

            p->l = p->r = NULL;

            p->cnt = 1;

            p->val = v;

            return;

            }

 p->cnt++;                                                         // Увеличить счетчик вершин в текущей вершине

 if (v < p->val){                                                    // Вытеснение меньшим значением большего

             int c=p->val; p->val=v; v=c;                     // из текущей вершины

            }

 if (p->l == NULL || p->r !=NULL && p->l->cnt < p->r->cnt)

             insert(p->l,v);                                        // Выбор свободной ветви или

 else                                                                 // поддерева с минимумом вершин

             insert(p->r,v);

}

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

void scan(vtree *p, int level) {  // level – уровень вершины
 if (p == NULL) return;

 printf("l=%d v=%d\n",level,p->val);

 scan(p->l,level+1);

 scan(p->r,level+1);
}

«Слияние» данных из дерева, упорядоченного в глубину. #

Получение упорядоченной последовательности происходит путем обратного перемещения значений от потомков к предкам. Поскольку вершина каждого поддерева содержит минимальное значение в нем, то очередное значение берется из корневой вершины. На его место помещается значение, полученное от потомка. Чтобы свойство упорядоченности дерева в глубину сохранялось, необходимо выбирать потомка с минимальным значением. Процесс «заимствования» повторяется для него далее по дереву, пока не будет достигнута терминальная вершина, которая уничтожается. Похожий процесс объединения двух упорядоченных линейных последовательностей, как известно, называется, слиянием. Здесь можно применить тот же термин, хотя речь идет о замещении.

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

//------------------------------------------------------84-02.cpp

// "Слияние" дерева - замещение значения в текущей вершине значением минимального потомка

int shift(vtree *&p){

 if (p==NULL) return 0;

 int vv=p->val;                                         // Возвратить значение из текущей

 if (p->l==NULL && p->r==NULL){            // Нет потомков -  удалить вершину

            delete p;                                    // и возвратить ее значение

            p = NULL;

            return vv;

            }

 if (p->l==NULL || p->r!=NULL && p->r->val < p->l->val)

             p->val = shift(p->r);                    // Выбрать минимальное значение

 else                                                     // от потомков и заместить текущее

             p->val = shift(p->l);

return vv;                                               // вернуть значение вершины

}

Ограничение обхода дерева, упорядоченного в глубину. Рекурсивный обход упорядоченного в глубину дерева может быть эффективен, если в нем производится поиск значения, близкого к минимальному, либо всех значений не больше заданного. В этом случае погружение в поддерево прекращается, как только в вершине обнаружится значение, не входящее в диапазон.

//------------------------------------------------------84-03.cpp

//------- Дерево, упорядоченное в глубину.

// Поиск значений, не превышающих заданное

// Рекурсивный обход с ограничением глубины

void search(vtree *p,  int high, int &n){

 if (p==NULL) return;

 n++;                                        // Счетчик пройденных вершин

 if (p->val <= high){

            printf("v=%d\n",p->val);

            search(p->r,high,n);

            search(p->l,high,n);

            }}

Пирамидальная сортировка в массиве #

Идею упорядоченного в глубину дерева можно перенести в массив, где оно получает название пирамиды – модели дерева с двумя потомками. В ней используется следующий способ индексации вершин: вершина с индексом N имеет двух потомков с индексами 2N и 2N+1. Корневая вершина имеет индекс 1. При таком представлении единственной проблемой является сбалансированность дерева. Будучи сбалансированным, оно занимает все ячейки массива. При отображении несбалансированного дерева размерность необходимого массива равна 2L , где L – максимальная длина ветви: все отсутствующие вершины, тем не менее, представлены ячейками массива.

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

//--------------------------------------------------------------84-04.cpp

// Пирамидальная сортировка - построение пирамиды

// Погружение в дерево путем обмена с предком

void set_tree(int A[],int n){

int l,i;

for (l=2;l<=n;l++){                                               // l - индекс погружаемой вершины

for (i=l; i!=1;i=i/2){                                   // индекс предка = i/2

                        if (A[i]>A[i/2]) break;                   // предок меньше потомка - выйти

                        int c=A[i]; A[i]=A[i/2]; A[i/2]=c;    // поменяться с предком

                        }}}

Процесс слияния можно воспроизвести «по образу и подобию» аналогичного процесса в дереве. При этом удаляемые в процессе слияния вершины можно обозначить в массиве значениями MAXINT – максимального целого. Тогда процесс слияния будет естественным образом обходить несуществующие вершины и замещать терминальные (удаление). Единственный технологический нюанс – определение концевых вершин дерева, потомки которых выходят за размерность массива.

//------------------------------------------------------------------------84-05.cpp

// Пирамидальная сортировка – слияние пирамиды

// Сортировка - n раз выбрать из дерева с замещением на минимального потомка

// Извлекаемые элементы в конце массива, не имеющие потомков,

// заменяются на  MAXINT.  Значение MAXINT обозначает отсутствие вершины

void sort(int A[],int B[], int n){

for (int i=1; i<=n; i++){                                                    // повторить n раз

            int j,k;

            B[i]=A[1];                                                          // Корневая вершина – в выходной массив

            for (j=1;j<=n;j=k){                                               // j=k - переход к замещающему потомку

                        k=2*j;                                                    // k - левый потомок

                        if (k>n)  { A[j]=MAXINT; break; }               // нет потомков - MAXINT (затычка)

                        if (k+1>n)                                              // нет второго потомка - взять первого

{ A[j]=A[k]; A[k]=MAXINT; break; }

 

                        if (A[k+1]<A[k]) k++;                              // иначе - выбрать минимального из них

                        A[j]=A[k];                                              // скопировать значение потомка в предка

            }}}

Существует и более элегантное решение, позволяющее обойтись одним массивом. В нем корневая вершина обменивается значением с последней, после чего последняя вершина из дерева исключается. Значение же корневой вершины погружается в дерево путем обмена с минимальным из потомков, пока не достигнет большего себя. В результате массив будет упорядочен по убыванию.

//------------------------------------------------------------------------84-06.cpp

// Слияние дерева, упорядоченного в глубину.

// На каждом шаге размерность дерева уменьшается на 1

void sort(int A[], int n){

int m,j,k;

for (m=n; m>1; m--){                               // Текущий размер дерева 1..m-1

   int c=A[1]; A[1]=A[m]; A[m]=c;                        // Обмен: вершина дерева (min) - с последним

   int j,k;                                                            // Последний далее не учитывается (размерность <m)

   for (k=1;2*k<m; k=j){                           // j=k - переход к замещающему потомку

      j=2*k;                                              // j - левый потомок

      if (j+1<m && A[j+1]<A[j]) j++;                       // Если правый есть и меньше левого - взять его

      if (A[k]<A[j]) break;                           // Достиг большего себя - прекратить обмен

      c=A[k]; A[k]=A[j]; A[j]=c;                  // Обмен с потомком

            }}}

Оценка трудоемкости. Верхнюю границу трудоемкости оценить легко. При погружении значений в дерево и их слиянии из него для каждого из них производится не более log2N обменов (длина ветви сбалансированного дерева) в каждом случае. Для N таких элементов получаем Tmax=2Nlog2N. Но даже эта оценка является завышенной, поскольку не учитывает, что для i-го элемента массива длина ветви будет log2i, то есть меньше N.