8.3. Линейные структуры данных на деревьях
Существуют задачи, где древовидные структуры являются элементом внешнего представления, например, древовидная организация папок и файлов, документов, объектов и т.п.. Любая свободно развивающаяся иерархическая система с произвольным количеством уровней – и есть дерево. Мы будем рассматривать задачи другого типа, где древовидная структура скрыта от внешнего пользователя, а является технологическим приемом, обеспечивающим эффективное решение задачи.
То есть пользователь дерева не видит и воспринимает структуру данных, как будто она имеет обычную линейную природу, в виде последовательности, каждый элемент которой имеет в ней собственный логический (порядковый) номер. И здесь возникает вопрос: а каким образом нумеруются вершины дерева и, следовательно, хранимые в них данные? Для этого устанавливается способ или алгоритм обхода. Обычно он бывает рекурсивным, как и само дерево. Вот несколько примеров:
рекурсивная нумерация «сверху вниз»: рекурсивный алгоритм сначала нумерует текущую вершину, а затем рекурсивно вершины в поддеревьях;
рекурсивная нумерация «снизу вверх»: алгоритм сначала рекурсивно нумерует вершины в поддеревьях, а затем текущую вершину;
рекурсивная нумерация «справа налево» в дереве с двумя потомками и единственным значением в вершине. В нем обход производится в последовательности «левое поддерево, текущая вершина, правое поддерево»;
при использовании вместо стека очереди вершин можно произвести обход и, соответственно, нумерацию вершин «по горизонтали».
Алгоритм нумерации линеаризует дерево, и создает внешнее представление о нем, как о линейной последовательности данных. Соответственно, все остальные алгоритмы должны работать по правилам этой «иллюзии». В информационных технологиях для этого используется термин логическое, в отличие от реального или физического. Иначе говоря, дерево – это физическое представление данных, а его линеаризация – его логическое представление в виде последовательности.
Деревья обладают еще одним важным свойством. В массиве и списке одну и ту же последовательность значений можно разместить одним единственным способом. Но можно построить множество деревьев, в которых при общем правиле обхода будет содержаться одна и та же последовательность. Опять же, выражаясь терминологически точно, одному логическому представлению может соответствовать множество физических, как это видно на рисунке.
![рис. 83.1. Деревья с обходом «сверху-вниз»]./assets/083-01.png)
Функция обхода дерева «сверху-вниз» имеет три параметра: указатель на текущую вершину, текущий уровень (глубина) дерева и логический номер, передаваемый по ссылке. В данном случае по ссылке передается параметр, который являются общим для всех вершин дерева в целом.
//----------------------------------------------------------------------------------------------------------------83-02.cpp
// Полный рекурсивный обход дерева
struct tree{
int val;
tree *l,*r;
};
void scan(tree *p, int level, int &ln){ // level – уровень вершины (длина ветви)
if (p==NULL) return; // ln - общий счетчик логических номеров
printf("%d %d %d\n", ln, level, p->val); // Сначала – вывод текущей вершины
ln++;
scan(p->l, level+1,ln); // Затем рекурсивный обход потомков
scan(p->r, level+1,ln); }Дерево с данными в концевых вершинах
Для начала разберем простой, не очень эффективный вариант. Пусть это будет «учебное» дерево, на котором мы обсудим все проблемы, касающиеся реальных деревьев. Итак, каждая вершина дерева имеет двух потомков – левого (left) и правого (right). Данные хранятся только в концевых вершинах, промежуточные вершины их не содержат. На каждом следующем уровне число вершин удваивается, т.е. на уровне n оно равно 2n. На всех предыдущих уровнях будет 1+2+4+…+2n-1 = 2n-1, т.е. на 1 меньше. Таким образом, получается эффективность около 50%.
Это видно на приведенном рисунке: 6 промежуточных и 7 оконечных вершин. В таком дереве упрощаются процедуры нумерации (задания логических номеров вершин), вставки и удаления. Именно ради простоты алгоритма вставки мы идем на такие расходы. Заметим, что при вставке по заданному логическому номеру требуется сначала найти вершину с таким номером. Сама вставка (замещение) состоит в превращении найденной вершины в промежуточную, новое значение включается левым потомком, а значение текущей вершины переносится в правого потомка.
Все это напоминает вставку в список в том смысле, что большинство элементов остается на своих местах, а новые включаются за счет переустановки связей. Но список растет «в длину», линейно, а дерево – «в глубину», за счет ветвления.
![рис. 83.2. Дерево с данными в концевых вершинах]./assets/083-02.png)
Есть еще одно свойство. Как любят говорить студенты, «интуитивно ясно», что у промежуточных вершин будут всегда два потомка, если учитывать предложенный способ вставки. Еще проще будет добавление последним. Нужно найти самую правую концевую вершину и сделать вставку «после»: превратить ее в промежуточную, текущее значение передать левому потомку, а новое – правому.
Для поиска вершины с заданным логическим номером можно применить тот же рекурсивный обход. Но будет все тот же линейный поиск. Более эффективный алгоритм, основанный на ветвлении, можно реализовать, если в каждую вершину добавить счетчик значений, хранимых в поддереве (иначе говоря, счетчик концевых вершин). Чтобы значения счетчиков были корректны, их нужно «накручивать» по всему пройденному пути при вставке и добавлении и «скручивать» при удалении.
Потомок выбирается просто: если логический номер меньше количества значений в левом поддереве nl, то уходим туда с тем же самым номером, иначе выбираем правое поддерево, нологический номер уменьшаем на это самое значение nl. Ясно, что этот алгоритм индуктивно замыкается на всех вершинах, поскольку сохраняет соотношение (инвариант), используемый при нумерации: в любом дереве сначала нумеруют вершины левого потомка, а затем – правого.
//------------------------------------------------------83-01.cpp
// Линейная СД на основе дерева с двумя потомками
// и данными в концевых вершинах
struct tree2{
int cnt; // Количество терминальных вершин в дереве
char *s; // Данные - строка текста
tree2 *l,*r; // Левый и правый потомки
};
// Создание терминальной вершины
tree2 *create(char *ss){
tree2 *q=new tree2;
q->l = q->r = NULL;
q->cnt = 1;
q->s = ss;
return q; }
// Поиск вершины по логическому номеру
char *get_n(tree2 *p, int n){
if (p==NULL) return NULL;
if (n >= p->cnt) return NULL; // Проверка на диапазон ЛН
if (p->cnt==1) return p->s; // Вершина концевая - найден
int ll=p->l->cnt; // ll - счетчик значений у левого потомка
if (n<ll) return get_n(p->l,n); // ЛН меньше, чем у левого - идти в него
return get_n(p->r,n-ll); // Иначе - в правого потомка с вычетом ll
}
// Добавление последним
void add(tree2 *&p, char *ss){
if (p==NULL) p=create(ss); // Для пустого дерева
else {
p->cnt++; // Накручивать счетчики вершин
if (p->r==NULL){ // Вершина концевая -
p->l=create(p->s); // Значение текущей - левому потомку
p->r=create(ss); // Правому потомку -новое
}
else add(p->r,ss); // Не концевая - направо
}}
// Включение по логическому номеру
void insert(tree2 *&p, int n, char *ss){
if (p == NULL) { p=create(ss); return; }
if (n >= p->cnt) return; // Проверка на диапазон ЛН
p->cnt++;
if (p->r==NULL){ // концевая вершина -
p->l=create(ss); // сделать ее промежуточной
p->r=create(p->s); // текущие данные - правому
return; // потомку, новые - левому
}
int ll=p->l->cnt; // ll - вершин у левого потомка
if (n<ll) insert(p->l,n,ss); // ЛН в диапазоне левого
else insert(p->r,n-ll,ss); } // Иначе - перейти в правый с остаткомОстается еще процедура удаления по логическому номеру. При удалении происходят изменения у предка той вершины, которая удаляется. Она должна «подтянуть к себе» оставшихся потомков, чтобы заполнить освободившееся место. Тогда сохранятся правила построения дерева. Здесь есть два варианта. Если оставшийся потомок – концевая вершина, то он должен сам стать концевой вершиной. Если же промежуточная, то он должен взять ее потомков себе.
![рис. 83.3. Удаление по логическому номеру]./assets/083-03.png)
А как это будет выглядеть в программе? Ведь вершина не может «убить себя». Хотя, по большому счету, это уже вопрос, касающийся программного кода. В принципе, функция, получающая указатель на вершину (или даже ссылку на указатель), может освободить указуемую память, а затем возвратиться из рекурсивного вызова к предку. Более того, в объектно-ориентированном программировании можно освободить память, занимаемую текущим объектом (delete this), если в текущем методе мы не будем к нему больше обращаться. Но лучше не пилить сук, на котором сидишь.
Но лучше сделать, чтобы текущая вершина была удалена предком. Рекурсивный вызов, который работает с концевой вершиной, возвращает предку логическое значение, указывающее, что ее нужно удалить. Кроме того, не нужно забывать «скручивать» счетчики во всех промежуточных вершинах.
//------------------------------------------------------83-01.cpp
// Удаление по логическому номеру
// результат - сообщение предку от концевой вершины
int remove(tree2 *p, int n){
tree2 *q;
if (p == NULL) return 0;
if (n >= p->cnt) return 0;
p->cnt--;
if (p->cnt==0) return 1; // концевая вершина - "убей меня"
int ll=p->l->cnt; // вершин у левого потомка
if (n<ll) {
if (remove(p->l,n)){ // Левый потомок просит удалить себя
delete p->l; // Удалить левого потомка
q=p->r; // Совместить правого
p->s=q->s; // потомка с текущей
p->l=q->l; // вершиной
p->r=q->r;
delete q; }
}
else {
if (remove(p->r,n-ll)){ // Аналогично - просит правый
delete p->r;
q=p->l;
p->s=q->s;
p->l=q->l;
p->r=q->r;
delete q;}
}
return 0; } // Промежуточная вершина "не просит удалить себя"В приведенном фрагменте перетягиваются все данные из потомка, смежного с удаляемым, независимо от того, конечный он или промежуточный. Можно даже предложил просто копировать вершины, как структурированные переменные (Замечание: с объектами такой способ был бы не совсем корректен).
if (remove(p->r,n-ll)){ // Аналогично - просит правый
delete p->r;
q=p->l;
*p=*q; // ВОТ ТАК !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
delete q;}
Еще раз о способах наведения порядка
Теперь давайте поговорим о трудоемкости. Общие выводы уже сделаны. Все алгоритмы «добираются» до нужной концевой вершины с помощью ветвления, то есть в сбалансированном дереве T=log2N, в вырожденном T=N/2. Кстати, добавление значения последним создает именно такое дерево. Непосредственно само добавление, вставка и удаление вершин затрагивает не более двух потомков, т.е. эти действия имеют постоянную трудоемкость.
![рис. 83.4. Дерево, созданное процедурой добавления]./assets/083-04.png)
Можно разработать алгоритмы, сохраняющие сбалансированность дерева, но они связаны с топологическим преобразованиями деревьев и пока нам не по зубам. Существует другой, менее радикальный способ, связанный с периодическим «наведением порядка». Очевидно, можно предложить процедуру наведения порядка – балансировки, которая периодически выравнивает структуру данных. Это можно сделать в рамках существующего дерева, «перебрасывая» данные из поддерева с большим количеством вершин в поддерево с меньшим. Начиная, само собой, с корня и повторяя рекурсивно для всех потомков. Значительно проще использовать вспомогательную структуру данных, например, собрать все концевые вершины в массив указателей, используя полный рекурсивный обход, а потом построить на нем сбалансированное дерево методом деления пополам.
Функция, строящая дерево, получает интервал в массиве указателей. (первоначально он соответствует всему массиву). Она создает промежуточную вершину, делит интервал пополам и раздает эти половины рекурсивным вызовам. Они возвращают поддеревья, которые присоединяются к текущей вершине как потомки. Так продолжается до тех пор, пока в интервале не останется одна вершина, она будет концевой
Кстати, трудоемкость такого алгоритма – линейна (рекуррентное определение трудоемкости TN=2TN/2+1, окончательное T=2N (см.7.1)). И еще одна мелочь. Промежуточные вершины в процессе сбора концевых вершин необходимо уничтожать, а при построении дерева – создавать как динамические переменные.
//------------------------------------------------------83-01.cpp
// Балансировка дерева
// Создание дерева из ДМУ на концевые вершины
tree2 *balance(tree2 *pp[], int a, int b){
tree2 *q;
if (a==b) {
q=pp[a]; // В интервале одна вершина
q->cnt=1; // Возвратить ее как концевую
q->r=q->l=NULL;
return q; }
q=new tree2; // промежуточная вершина
int m=(a+b)/2; // середина интервала
q->l=balance(pp,a,m); // создать поддеревья
q->r=balance(pp,m+1,b); // на половинах интервала
q->cnt=b-a+1; // Сформировать новый счетчик
return q; // Возвратить поддерево
}
// Обход с заполнением ДМУ на концевые вершины
void create(tree2 *p, tree2 *pp[], int &ln){ // ln - ссылка на текущий ЛН
if (p==NULL) return;
if (p->cnt==1) pp[ln++]=p; // Концевая вершина - запомнить
else {
create(p->l,pp,ln); // Промежуточные - обход потомков
create(p->r,pp,ln);
delete p; // Промежуточные - удаляются
}}
// Общая процедура балансировки
void balance(tree2 *&ph){
if (ph==NULL) return;
int sz=ph->cnt;
tree2 **pp=new tree2*[sz]; // создать ДМУ
int i=0; create(ph,pp,i); // собрать концевые вершины в ДМУ
ph=balance(pp,0,sz-1); // построит дерево на ДМУ
delete pp;} // уничтожить ДМУЖелательно проверять программу на реальных данных, например, загружая текстовые файлы большого объема. Еще бы желательно, чтобы программа выводила характеристики дерева: количество вершин, степень сбалансированности. Чтобы это оценить, можно измерить расстояния от корневой до каждой конечной вершины и усреднить их. У сбалансированного дерева оно должно быть равно log2N, а для дерева, полученного с помощью алгоритма добавления, получим L=(1+2+3+…N-1+N-1)/N ≈ (N2/2)/N=N/2, т.е. линейная зависимость. Для подсчета этого значения можно было бы использовать функцию обхода, добавив в нее еще результат – сумму длин путей.
//------------------------------------------------------83-01.cpp
// Обход дерева – выводит все вершины и возвращает сумму длин путей
int scan(tree2 *p, int level, int &ln){ // level – текущая глубина
if (p==NULL) return 0; // ln – логический номер
int L=0;
if (p->l==NULL){
printf("l=%d n=%d cnt=%d :%s\n", level, ln, p->cnt, p->s);
ln++;
return level;
}
else { printf("l=%d cnt=%d\n", level, p->cnt);
return scan(p->l, level+1,ln)+scan(p->r, level+1,ln);
}}Дерево с нумерацией вершин «сверху-вниз»
Давайте слегка усложним задачу. Дерево с двумя потомками теперь будет содержать данные во всех вершинах. Нумеровать их будем «сверху-вниз»: сначала нумеруется корневая вершина поддерева, потом вершины левого потомка, а затем – правого. Аналогично, для реализации поиска по логическому номеру в каждую вершину введем счетчик вершин в поддереве.
![рис. 83.5. Дерево с нумерацией вершин «сверху-вниз»]./assets/083-05.png)
Некоторые алгоритмы просто корректируются в соответствии с изменившимся порядком нумерации. Функция, выполняющая полный рекурсивный обход дерева, пронумеровывает вершины, используя общих для всех вызовов счетчик, передаваемый по ссылке: сначала текущую вершину, затем левое и правое поддеревья.
//----------------------------------------------------------------------------------------------------------------83-02.cpp
// Полный рекурсивный обход дерева
void scan(tree2 *p, int level, int &ln){ // level – уровень вершины (длина ветви)
if (p==NULL) return; // ln - порядковый (логический) номер
printf("l=%d n=%d cnt=%d :%s\n", level, ln, p->cnt, p->s);
ln++;
scan(p->l, level+1,ln);
scan(p->r, level+1,ln); }Имея в каждой вершине счетчики вершин поддерева, мы, тем самым, получаем диапазоны логических номеров вершин (как текущей, так и каждого потомка), для которых получается простой алгоритм ветвления:
если текущий логический номер (ЛН) меньше количества вершин в текущем поддереве, то вершины с таким ЛН не существует;
если ЛН при входе в поддереве равен 0, то он соответствует корневой вершине;
иначе от ЛН отнимается единица и при наличии левого поддерева проверяется вхождение ЛН в его диапазон. Если это так, то функция рекурсивно вызывается для левого поддерева;
иначе от ЛН отбрасывается количество вершин в левом поддереве и с полученным остатком алгоритм выполняется для правого поддерева.
//--------------------------------------------------------------------------------------------------------------83-02.cpp
// Поиск значения по логическому номеру
char *get_n(tree2 *p, int n){
if (p==NULL) return NULL;
if (n >= p->cnt) return NULL; // ЛН вне диапазона дерева
if (n-- ==0) return p->s; // ЛН = 0 для корневой вершины
if (p->l!=NULL){ // Если есть левое поддерево
int ll=p->l->cnt; // и ЛН-1 попадает в его диапазон ll
if (n<ll) return get_n(p->l,n); // Искать в нем с тем же ЛН-1
n-=ll; // Иначе отбросить число вершин
} // в левом поддереве и корень
return get_n(p->r,n); } // и искать остаток в правом поддеревеПри вставке новое значение «замещает» старое на его месте. Тогда по отношению к «лишним» данным нужно выполнить тот же самый алгоритм вставки в поддерево найденной вершины. Данные вытесняются из вершины, она, в свою очередь, становится корневой вершиной дерева, тогда их нужно включить в левое поддерево «в начало», т.е. с относительным логическим номером, равным 0.
//--------------------------------------------------------------------------------------------------------------83-02.cpp
// Включение по логическому номеру
void insert(tree2 *&p, int n, char *ss){
if (p == NULL) { p=create(ss); return; }
if (n >= p->cnt) return;
p->cnt++; // увеличивать счетчики в проходимых вершинах
if (n-- ==0) // если текущий ЛН=0 - вершина найдена,
insert(p->l,0,p->s),p->s=ss; // данные из нее сносятся в левое поддерево
else // с ЛН=0, а на их место помещаются новые
if (p->l!=NULL){ // Иначе - рекурсивный вызов аналогично алгоритму
int ll=p->l->cnt; // поиска по ЛН
if (n<ll) { insert(p->l,n,ss); return; }
n-=ll; }
else insert(p->r,n,ss);}Обратите внимание, что здесь передается ссылка на указатель на текущую вершину, т.е. «отображение» на то место, где хранится указатель на текущую вершину. Это позволяет создавать новую вершину на свободной ветви, т.е. когда мы ссылаемся на указатель, содержащий NULL. При удалении, похоже, можно сделать «вытеснение наоборот», т.е. удалять найденную вершину, а на ее место помещать одного из потомков. Если использовать ту же технику – ссылка на указатель, то под ссылку нужно помещать указатель на «следующего» в порядке нумерации потомка. Перечислим все возможные варианты.
Если потомков нет, то NULL, если потомок один, то указатель на него. А что делать, если потомков два? Ведь нельзя под одну ссылку поместить сразу два указателя? А ведь потомки тоже могут быть промежуточными вершинами. В этом случае надо отказаться от перемещения вершин и вспомнить, что мы делали с «лишними» данными при вставке. И сделать наоборот, т.е. «занять» недостающие данные, исключив их из левого поддерева с логическим номером 0.
//--------------------------------------------------------------------------------------------------------------83-02.cpp
// Удаление по логическому номеру
char *remove(tree2 *&p, int n){ // ссылка на место размещения указателя
if (p == NULL) return NULL; // удаляемой вершины
if (n >= p->cnt) return NULL; // Для удаляемой вершины производится замещение
p->cnt--; // Если нет потомков - удаляется
if (n-- ==0) { // Если есть один потомок - удаляется, на ее место
char *ss = p->s; // помещается потомок
tree2 *q; // Иначе замещается значением, удаляемым по ЛН=0
// из левого поддерева
if (p->l==NULL && p->r==NULL) { delete p; p=NULL; return ss;}
if (p->l==NULL) { q=p->r; delete p; p=q; return ss; }
if (p->r==NULL) { q=p->l; delete p; p=q; return ss; }
p->s = remove(p->l,0); return ss;
}
if (p->l!=NULL){ // Иначе - рекурсивный вызов аналогично алгоритму
int ll=p->l->cnt; // поиска по ЛН
if (n<ll) return remove(p->l,n);
n-=ll; }
else return remove(p->r,n); }Кстати, мы уже обсуждали, может ли вершина «убить себя». Оказывается, что может. В нашем примере по ссылке на текущую вершину производится ее уничтожение (освобождение памяти), а потом под эту ссылку записывается указатель на выбранного потомка.
Что касается балансировки, то здесь, отличия несущественные. Собирать вершины в массив указателей можно обходом теперь уже всех вершин, а строить дерево – в соответствии с правилом нумерации – первая вершина интервала – корневая, а остаток, начиная со второй, аналогично разбивается на две равные части.
Здесь есть еще одна тонкость. В этом дереве возможны интервалы нулевой длины. Допустим, создается дерево из 2 вершин. Первая становится корневой, вторая – левым поддеревом, а интервал правого – нулевой длины. В этом случае функция возвращает NULL-указатель.
//----------------------------------------------------------------------------------------------------------------83-02.cpp
// Балансировка поддерева в диапазоне логических номеров [a...b]
// Функция формирует сбалансированное поддерево из вершин интервала
tree2 *balance(tree2 *pp[], int a, int b){
if (a>b) return NULL; // диапазон "стянулся" в точку
tree2 *q;
if (a==b) // в диапазоне - единственная вершина
{ q=pp[a]; q->l=q->r=NULL; q->cnt=1; return q; }
q=pp[a]; // первая вершина интервала - корневая
int m=(a+b+1)/2; // середина оставшегося интервала
q->l=balance(pp,a+1,m-1); // левое и правое поддерево сформировать
q->r=balance(pp,m,b); // рекурсивно из половинок интервала
q->cnt=b-a+1; // счетчик вершин в поддереве -
return q; // ширина интервала
}
// Обход дерева с заполнением массива указателей на вершины
void set(tree2 *pp[], tree2 *p, int &ln){
if (p==NULL) return; // ln - порядковый (логический) номер
pp[ln++]=p; // запомнить указатель на текущую вершину
set(pp,p->l,ln); // рекурсивно выполнить для поддеревьев
set(pp,p->r,ln); }
// Балансировка поддерева с использованием динамического массива указателей
void balance(tree2 *&ph){
int sz=ph->cnt; // создать динамический массив указателей
tree2 **pp=new tree2*[sz];
int ln=0;
set(pp,ph,ln); // заполнить
ph=balance(pp,0,sz-1); // вызвать рекурсивную функцию балансировки
} // для всего интервала
