Деревья способы представления деревьев

Содержание

8 . Нелинейные структуры данных. Деревья и графы
8 .1. Деревья и рекурсивные алгоритмы
Способы представления деревьев
Эффективность алгоритмов, работающих с деревьями
Структуры данных. Деревья
1 Что такое деревья (в программировании)?
2 Деревья и другие структуры данных
3 Деревья поиска
4 Kd-деревья

8 . Нелинейные структуры данных. Деревья и графы

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

8 .1. Деревья и рекурсивные алгоритмы

Определение дерева. Дерево и рекурсия

void ScanTree ( текущая вершина)<

if ( текущая вершина ==NULL) return;

for ( перебор потомков) ScanTree ( i -ый потомок)

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

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

— если алгоритм предполагает навигацию по дереву во всех направлениях, как вверх, так и вниз по дереву (например, в древовидной системе каталогов), то предполагается наличие как прямых, так и обратных ссылок от потомков к предкам (в системе каталогов – ссылка на родительский каталог);

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

Способы представления деревьев

До сих пор мы говорили о деревьях абстрактно, как о логической структуре. А теперь спустимся на грешную землю и обсудим варианты его физического размещения. Составными частями физического представления дерева могут быть массивы, списки, массивы указателей. Начнем с самого простого.

void scan_m(mtree A[], int n, int k, int level)< // k – индекс предка

printf(«l=%d node=%d s=%s\n»,level,k,A[k].s);

for ( int i =0; i n ; i ++) // Цикл выбора потомков вершины

if (A[i].parent==k) scan_m(A,n,i,level+1);>

void scan _2( int A[], int n, int k,int level)< // k – индекс текущей вершины

printf(«l=%d node=%d val=%d\n»,level,k,A[k]);

// 0 1 2 3 4 5 6 7 8 9

Получается быстро, а главное, без дополнительной информации, индекс массива однозначно определяет положение вершины. Но за это приходится расплачиваться. Каждый следующий уровень требует удвоения размерности массива, вне зависимости от того, сколько вершин этого уровня используются. Поэтому основное требование – сбалансированность. Если есть хотя бы одна ветвь, сильно отличающаяся по длине, то эффективность использования памяти резко снижается. Если же дерево вырождается в список, то размерность массива растет экспоненциально W=2 N .

Каждая вершина содержит два указателя – на «старшего сына» – заголовок списка следующего уровня, и на «следующего брата» — ссылка в списке вершин текущего уровня.

// Представление дерева в виде разветвляющегося списка

ltree *son,*bro; // Указатели на старшего сына

>; // и младшего брата

ltree A=<"aa",NULL,NULL>, // Последняя в списке

C=<"cc",NULL,&B>, // Список потомков — концевых вершин A,B,C D =<" dd ", NULL , NULL >,

F=<"ff",&D,&E>, // Список потомков G — вершин F,E

void scan_l(ltree *p, int level)<

if (p==NULL) return;

for (ltree *q=p->son;q!=NULL;q=q->bro)

int n ; // Количество потомков в МУ

void scan(tree *p, int level)<

if (p==NULL) return;

Эффективность алгоритмов, работающих с деревьями

Можно провести аналогии между парой «деревья — рекурсивные алгоритмы» и «пространство-время». При работе рекурсивной программы происходит развертке дерева вызовов функции во времени, а дерево, как структура данных, выглядит как отображенный в памяти результат выполнения рекурсивного алгоритма. Именно поэтому к деревьям применимы выводы относительно эффективности рекурсивных алгоритмов:

— полный рекурсивный обход дерева имеет линейную трудоемкость;

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

— возможно использование формального параметра – ссылки, которая передается по цепочке рекурсивных вызовов. В этом случае все рекурсивные вызовы ссылаются на общую переменную, которая играет роль глобальных данных, используемых для накопления результата.

Читайте также: Герметик абро способ применения

N = 1 + m + m 2 + m 3 + … + m L m L , L

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

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

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

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

На житейском уровне эту альтернативу можно сформулировать как «идеальный порядок или периодическая генеральная уборка». Аналогичная ситуация возникает в любых системах динамического распределения и утилизации ресурсов: в системе динамического распределения памяти (2.6), при планировании двоичного файла (9.2), в системе управления файлами операционной системы, где она имеет похожие решения.

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

— наличие в вершине дополнительной (избыточной) информации, позволяющей сделать такой выбор «здесь и сейчас»;

— наличие определенного порядка размещения данных в дереве.

Источник

Структуры данных. Деревья

Статья познакомит вас с понятием дерева как структуры данных, пояснит в каких случаях и для чего можно их применять:

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

1 Что такое деревья (в программировании)?

Математическое определение дерева — «граф без петель и циклов» вряд-ли пояснит рядовому человеку какие выгоды можно извлечь из такой структуры данных.

В некоторых книгах, посвященным разработке алгоритмов, деревья определяются рекурсивно. Дерево является либо пустым, либо состоит из узла (корня), являющегося родительским узлом для некоторого количества деревьев (это количество определяет арность дерева) [1, 2].

Рабочее определение (в рамках этой статьи): дерево — это способ организации данных в виде иерархической структуры.

Когда применяются древовидные структуры:

иногда такая иерархия существует в предметной области вашей программы, например, она должна обрабатывать гениалогическое дерево или работать со структурой каталогов на жестком диске. В таких случаях инода имеет смысл сохранить между объектами вашей программы существующие отношения иерархии:
Дерево каталогов операционной системы UNIX
в других случаях между объектами, которые обрабатывает ваша программа отношения иерархии явно не заданы, однако, их можно задать и это сделает обработку данных в программе более удобной. Например, при разработке парсеров или трансляторов полезным может оказаться дерево синтаксического разбора (синтаксическое дерево) [4], хотя в выражениях типа «1+7*3» иерархия операций не так очевидна;
не секрет, что поиск объектов наиболее эффективен если они упорядочены. В частности, поиск значения в неупорядоченном наборе из 1000 элементов в худшем случае потребует 1000 операций, а в упорядоченном — можно обойтись всего 10.

Двоичный поиск [3] выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения — либо левая, либо правая части могут быть «отброшены».

Иерархия — способ упорядочивания объектов, соответственно применять ее можно для ускорения поиска. Именно этому посвящена остальная часть статьи.

2 Деревья и другие структуры данных

Итак, у нас есть много данных — возможно это информация о температуре за несколько лет, а может быть — данные о фирмах в вашем городе. Как хранить их внутри вашего приложения? — Правильный ответ зависит от того, как именно вы будете пользоваться этими данными.

В таблице приведены асимптотические оценки часто используемых операций над некоторыми структурами данных. На случай если вы еще не освоили асимптотический анализ, в таблице показано примерное значение количества действий, необходимых для выполнения операции над контейнером из 10 тысяч элементов.

удаление элемента по указателю (итератору)

10000

Операция

неупорядоченный массив

упорядоченный массив

неупорядоченный двусвязный список

сбалансированное дерево поиска

O(n)

10000

O(1)

поиск элемента с заданным значением

10000

O(log(n))

10000

O(log(n))

вставка элемента (значения)

10000

O(n)

10000

O(1)

(вернет i-тый по значению элемент)

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

при удалении элемента нужно «сдвинуть» все значения, размещенные «справа»;
при вставке может потребоваться создание массива большего размера и копирование туда всех данных из старого массива;

При поиске значения в массиве мы в худшем случае переберем все элементы, то есть выполним O(n) операций. Однако, если массив упорядочен — мы можем применить двоичный поиск, который значительно эффективнее.

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

Деревья поиска, как и связные списки состоят из узлов, связанных указателями. Однако узлы эти упорядочены определенным образом — за счет этого увеличивается эффективность поиска, но осложняется операция вставки элемента. Эта структура данных, в ряде случаев,может иметь преимущества над массивами и связными списками — посмотрим за счет чего это обеспечивается…

3 Деревья поиска

Двоичное дерево состоит из узлов, каждый из которых хранит свое значение, а также две ссылки — на правое и левое поддерево. Если справа или слева нет узлов — соответствующая ссылка равна нулю (в С++ — нулевой указатель). Дерево представляется корнем (ссылкой на самый верхний узел).

Особенность дерева поиска заключается в алгоритме построения — значения вершин левого поддерева должны всегда оказываться меньше или равны значению корневого узла, а правого – больше.

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

В процессе поиска элемента в дереве, мы сравниваем его со значением корня, если корень оказался больше — то нам нет смысла рассматривать правое поддерево (ведь там все значения еще больше). За счет этого на каждом сравнении «отсекается» узлов дерева, а значит — мы получаем поиск с оценкой сложности O(log(n)) .

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

если дерево является пустым – то E помещается в корневую вершину;
если значение E больше значения корневой вершины – осуществляется вставка E в правое поддерево (рекурсивно), иначе – в левое.

Пример использования такого алгоритма приведен в таблице:

Шаг 0: исходное дерево
Шаг 1: определям, что вставлять нужно в левое поддерево
Шаг 2: 6 > 4 , поэтому вставляем в правое поддерево
Шаг 3: 6 , вставка в левое поддеррево
Шаг 4: 6 > 5 , вставляем справа, но там пусто.

В качестве упражнения полезно попробовать вставить в дерево узел со значением 8.5 , а также, взять пустое дерево (без элементов) и добавить в него последовательно узлы [1, 11, 32, 46, 48] . Если в результате у вас получится дерево, как на приведенной ниже картинке — вы все поняли и сделали правильно:

Этот пример иллюстрирует основную проблему описанного тут алгоритма вставки узлов — если подать ему на вход упорядоченные данные — то дерево «вытянется» в обыкновенный двусвязный список. В частности, для выполнения поиска в таком «дереве» из N элементов нам придется перейти по укзателям N раз.

Удаление элемента из дерева поиска, несколько запутаннее, поэтому алгоритм тут не приведен, зато приведены поясняющие иллюстрации:

Исходное дерево
Удаление листа (не имеющего дочерних узлов). Красным обозначен удаленный узел, желтым — измененный (у узла 7 изменилась левая ссылка).
Удаление узла, имеющего ровно одного потомка также выполняется достаточно просто. Мы заменяем ссылку на удаляемый узел ссылкой на его потомка.
При удалении узла X , имеющего обоих потомков, необходимо заменить ссылку на него, ссылкой на его потомка Y в отсортированном порядке. Этот узел Y должен иметь наименьшее значение ключа в правом поддереве, а именно быть самым левым узлом в правом поддереве дерева с корнем X [2].

Такие алгоритмы добавления элемента и удаления элемента не гарантируют сбалансированности полученного дерева, то есть дерево может «вырождаться» в список, как показано на рисунке выше. Существуют самобалансирующиеся деревья поиска, например, красно-черные деревья, АВЛ-деревья или расширяющиеся деревья, но их рассмотрение выходит за рамки статьи [2, 5, 6]. Нужно знать, что аналогичные операции для, таких деревьев реализуются несколько труднее, но их вычислительная сложность можно оценить как O(log(N)) . Эти алгоритмы уже реализованы во множестве библиотек и обычно их не требуется писать самостоятельно. Например, в стандартной библиотеке С++ они представлены классами std::map и std::set .

4 Kd-деревья

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

Игровой уровень обычно значительно больше, чем видимая в данный момент область экрана, а отрисовывать необходимо только видимые объекты. Значит движок должен уметь быстро получать объекты, входящие в заданную прямоугольную область. Кроме того, объекты умеют перемещаться и сталкиваться друг с другом — когда Марио собирает монетку, она исчезает, а счет увеличивается. Игровой движок должен эффективно реализовывать обработку столкновения объектов — подумайте почему эта задача сводится к первой. Примитивная реализация поиска столкнувшихся объектов может заключаться в переборе всех пар, то есть имеет вычислительную сложность O(n^2) . Даже в Марио (которой более 20 лет) уровни содержали тысячи объектов, а значит такой алгоритм не подойдет.

Мы уже разобрались с тем, что для эффективной реализации поиска объекты нужно хранить упорядоченными. Однако, как хранить точки? — ведь у них есть две (или три) координаты, а сортировка по одной из них не обеспечит приемлемую скорость поиска. Именно эти проблемы решают Kd-деревья.

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

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

Первый вариант решения:

выберем произвольную точку на плоскости (желательно ближе к центру), поместим ее в корень дерева. Плоскость разобьем на 2 части — левую и правую (относительно точки);
выделим в каждой области по точке, которую поместим в корень поддерева, разобьем каждое подпространство на два — нижнее и верхнее;
описанный процесс повторяется до тех пор, пока в каждой области плоскости не окажется по одной точке. При разбиении чередуются измерения, на основе которых выполняется разделение пространства (верхнее-нижнее, левое-правое).

Пример построения такого дерева приведен на рисунке. Тут плоскость сначала разбита относительно точки А на левую и правую, правая в свою очередь разбита на нижнюю и верхнюю относительно точки С. Нижняя опять разбивается на левую и правую относительно точки D .

С такой структурой данных, алгоритм вывода всех точек, входящих в Прямоугольник может выглядеть так:

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

При перемещении объектов может возникать необходимость перестроения дерева — если объект переместился из одной области «родительского» объекта в другую.

Описанный подход называется Kd-деревья с циклическим проходом по измерениям. Возможны и другие варианты выбора секущей плоскости — например каждый узел квадрадерева делит свою часть плоскости на 4 части (левая верхняя, левая нижняя, правая верхняя, права нижняя). Если в какой-то части оказывается более 1 объекта — то она делится дальше. Октадеревья адаптируют эту идею к трехмерному пространству.

Источник