Структуры данных. Деревья
Статья познакомит вас с понятием дерева как структуры данных, пояснит в каких случаях и для чего можно их применять:
- рассмотрены достоинства и недостатки деревьев относительно списков и массивов, исходя из которых вы сможете выбрать наиболее подходящую структуру данных для своей задачи;
- показаны основные проблемы реализации деревьев поиска, которые должны подтолкнуть вас использовать готовые библиотеки, а не пытаться сделать все самостоятельно;
- описаны Kd-деревья — решаемые проблемы и предлагаемые подходы.
1 Что такое деревья (в программировании)?
Математическое определение дерева — «граф без петель и циклов» вряд-ли пояснит рядовому человеку какие выгоды можно извлечь из такой структуры данных.
В некоторых книгах, посвященным разработке алгоритмов, деревья определяются рекурсивно. Дерево является либо пустым, либо состоит из узла (корня), являющегося родительским узлом для некоторого количества деревьев (это количество определяет арность дерева) [1, 2].
Рабочее определение (в рамках этой статьи): дерево — это способ организации данных в виде иерархической структуры.
Когда применяются древовидные структуры:
- иногда такая иерархия существует в предметной области вашей программы, например, она должна обрабатывать гениалогическое дерево или работать со структурой каталогов на жестком диске. В таких случаях инода имеет смысл сохранить между объектами вашей программы существующие отношения иерархии:
- в других случаях между объектами, которые обрабатывает ваша программа отношения иерархии явно не заданы, однако, их можно задать и это сделает обработку данных в программе более удобной. Например, при разработке парсеров или трансляторов полезным может оказаться дерево синтаксического разбора (синтаксическое дерево) [4], хотя в выражениях типа «1+7*3» иерархия операций не так очевидна;
- не секрет, что поиск объектов наиболее эффективен если они упорядочены. В частности, поиск значения в неупорядоченном наборе из 1000 элементов в худшем случае потребует 1000 операций, а в упорядоченном — можно обойтись всего 10.
Двоичный поиск [3] выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения — либо левая, либо правая части могут быть «отброшены».
2 Деревья и другие структуры данных
Итак, у нас есть много данных — возможно это информация о температуре за несколько лет, а может быть — данные о фирмах в вашем городе. Как хранить их внутри вашего приложения? — Правильный ответ зависит от того, как именно вы будете пользоваться этими данными.
В таблице приведены асимптотические оценки часто используемых операций над некоторыми структурами данных. На случай если вы еще не освоили асимптотический анализ, в таблице показано примерное значение количества действий, необходимых для выполнения операции над контейнером из 10 тысяч элементов.
удаление элемента по указателю (итератору)
поиск элемента с заданным значением
вставка элемента (значения)
(вернет i-тый по значению элемент)
Особенностью массивов является хранение данных в непрерывной области памяти. За счет этого обеспечивается максимальная эффективность операции произвольного доступа, однако:
- при удалении элемента нужно «сдвинуть» все значения, размещенные «справа»;
- при вставке может потребоваться создание массива большего размера и копирование туда всех данных из старого массива;
При поиске значения в массиве мы в худшем случае переберем все элементы, то есть выполним O(n) операций. Однако, если массив упорядочен — мы можем применить двоичный поиск, который значительно эффективнее.
Связные списки хранят значения в узлах, разбросанных по памяти и связанных между собой указателями. За счет этого, вставка и удаление работает очень быстро, однако для обращения к N -ному элементу списка придется пройти по указателям N раз.
Деревья поиска, как и связные списки состоят из узлов, связанных указателями. Однако узлы эти упорядочены определенным образом — за счет этого увеличивается эффективность поиска, но осложняется операция вставки элемента. Эта структура данных, в ряде случаев,может иметь преимущества над массивами и связными списками — посмотрим за счет чего это обеспечивается…
3 Деревья поиска
Двоичное дерево состоит из узлов, каждый из которых хранит свое значение, а также две ссылки — на правое и левое поддерево. Если справа или слева нет узлов — соответствующая ссылка равна нулю (в С++ — нулевой указатель). Дерево представляется корнем (ссылкой на самый верхний узел).
Особенность дерева поиска заключается в алгоритме построения — значения вершин левого поддерева должны всегда оказываться меньше или равны значению корневого узла, а правого – больше.
При обходе такого дерева, начиная с левого поддерева, значения будут просмотрены в порядке неубывания, начиная с правого – невозрастания, т.е. дерево поиска хранит отсортированные данные:
начало - функция "обход(Дерево = Узел(Левый, Значение, Правый))" 1. если Левый <> null то выполни обход(Левый); 2. вывод: Значение 3. если Правый <> null то выполни обход(Правый); 4. конец
В процессе поиска элемента в дереве, мы сравниваем его со значением корня, если корень оказался больше — то нам нет смысла рассматривать правое поддерево (ведь там все значения еще больше). За счет этого на каждом сравнении «отсекается» узлов дерева, а значит — мы получаем поиск с оценкой сложности O(log(n)) .
Операция вставки выполняет добавление листа в дерево, то справа и слева от нового узла будет пусто ( null ). При вставке мы выполняем поиск подходящей свободной позиции, с учетом требования «значения вершин левого поддерева должны всегда оказываться меньше или равны значению корневого узла, а правого – больше». Алгоритм вставки значения E в дерево может выглядеть так:
- если дерево является пустым – то E помещается в корневую вершину;
- если значение E больше значения корневой вершины – осуществляется вставка E в правое поддерево (рекурсивно), иначе – в левое.
Пример использования такого алгоритма приведен в таблице:
| Шаг 0: исходное дерево |  |
| Шаг 1: определям, что вставлять нужно в левое поддерево |  |
| Шаг 2: 6 > 4 , поэтому вставляем в правое поддерево |  |
| Шаг 3: 6 < 7 , вставка в левое поддеррево |  |
| Шаг 4: 6 > 5 , вставляем справа, но там пусто. |  |
В качестве упражнения полезно попробовать вставить в дерево узел со значением 8.5 , а также, взять пустое дерево (без элементов) и добавить в него последовательно узлы [1, 11, 32, 46, 48] . Если в результате у вас получится дерево, как на приведенной ниже картинке — вы все поняли и сделали правильно:
Этот пример иллюстрирует основную проблему описанного тут алгоритма вставки узлов — если подать ему на вход упорядоченные данные — то дерево «вытянется» в обыкновенный двусвязный список. В частности, для выполнения поиска в таком «дереве» из N элементов нам придется перейти по укзателям N раз.
Удаление элемента из дерева поиска, несколько запутаннее, поэтому алгоритм тут не приведен, зато приведены поясняющие иллюстрации:
Такие алгоритмы добавления элемента и удаления элемента не гарантируют сбалансированности полученного дерева, то есть дерево может «вырождаться» в список, как показано на рисунке выше. Существуют самобалансирующиеся деревья поиска, например, красно-черные деревья, АВЛ-деревья или расширяющиеся деревья, но их рассмотрение выходит за рамки статьи [2, 5, 6]. Нужно знать, что аналогичные операции для, таких деревьев реализуются несколько труднее, но их вычислительная сложность можно оценить как O(log(N)) . Эти алгоритмы уже реализованы во множестве библиотек и обычно их не требуется писать самостоятельно. Например, в стандартной библиотеке С++ они представлены классами std::map и std::set .
4 Kd-деревья
Во многих программах появляется необходимость хранения и эффективной обработки объектов на плоскости. Это не только картографические приложения, но и все двумерные игры. Задумывались ли вы о том, как эту задачу решают игровые движки?
Игровой уровень обычно значительно больше, чем видимая в данный момент область экрана, а отрисовывать необходимо только видимые объекты. Значит движок должен уметь быстро получать объекты, входящие в заданную прямоугольную область. Кроме того, объекты умеют перемещаться и сталкиваться друг с другом — когда Марио собирает монетку, она исчезает, а счет увеличивается. Игровой движок должен эффективно реализовывать обработку столкновения объектов — подумайте почему эта задача сводится к первой. Примитивная реализация поиска столкнувшихся объектов может заключаться в переборе всех пар, то есть имеет вычислительную сложность O(n^2) . Даже в Марио (которой более 20 лет) уровни содержали тысячи объектов, а значит такой алгоритм не подойдет.
Мы уже разобрались с тем, что для эффективной реализации поиска объекты нужно хранить упорядоченными. Однако, как хранить точки? — ведь у них есть две (или три) координаты, а сортировка по одной из них не обеспечит приемлемую скорость поиска. Именно эти проблемы решают Kd-деревья.
Общая идея kd-деревьев заключается в разделении плоскости, содержащей объекты на части (прямоугольные области) таким образом, что в каждой области содержится один объект. При этом, между областями можно выстроить иерархические зависимости, за счет которых можно существенно повысить эффективность поиска. Существуют различные типы kd-деревьев, отличающиеся выбором секущей плоскости.
Задача: есть множество точек, находящихся на плоскости, нужно выстроить объекты в иерархическую структуру, исходя из их координат для обеспечения эффективного поиска. Описанные ниже подходы можно обобщить до более сложных геометрических объектов (не точек) и пространств больших размерностей.
- выберем произвольную точку на плоскости (желательно ближе к центру), поместим ее в корень дерева. Плоскость разобьем на 2 части — левую и правую (относительно точки);
- выделим в каждой области по точке, которую поместим в корень поддерева, разобьем каждое подпространство на два — нижнее и верхнее;
- описанный процесс повторяется до тех пор, пока в каждой области плоскости не окажется по одной точке. При разбиении чередуются измерения, на основе которых выполняется разделение пространства (верхнее-нижнее, левое-правое).
Пример построения такого дерева приведен на рисунке. Тут плоскость сначала разбита относительно точки А на левую и правую, правая в свою очередь разбита на нижнюю и верхнюю относительно точки С. Нижняя опять разбивается на левую и правую относительно точки D .
С такой структурой данных, алгоритм вывода всех точек, входящих в Прямоугольник может выглядеть так:
начало - функция "поиск(Дерево = Узел(Левый, Точка, Правый), Прямоугольник)" 1. если Точка входит в Прямоугольник - вывести ее; 2. если Примоугольник пересекается с Левой областью - то выполни поиск(Левый, Прямоугольник); 3. если Примоугольник пересекается с Правой областью - то выполни поиск(Правый, Прямоугольник); 4. конец.
Цветом на приведенной выше схеме обозначена область поиска. Она не пересекается с областью B (расположенной левее А ). Даже если бы в этой области были миллионы точек — мы «отсекли» бы их за одну итерацию алгоритма — то есть мы получили полноценный двоичный поиск на плоскости. Визуализация алгоритма:
При перемещении объектов может возникать необходимость перестроения дерева — если объект переместился из одной области «родительского» объекта в другую.
Описанный подход называется Kd-деревья с циклическим проходом по измерениям. Возможны и другие варианты выбора секущей плоскости — например каждый узел квадрадерева делит свою часть плоскости на 4 части (левая верхняя, левая нижняя, правая верхняя, права нижняя). Если в какой-то части оказывается более 1 объекта — то она делится дальше. Октадеревья адаптируют эту идею к трехмерному пространству.
Дополнительная литература
- Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.
- Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.
- Рекурсия в программировании. Анализ алгоритмов : https://pro-prof.com/archives/813
- Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект, 2001. – 352 с.
- Кормен Т. и др. Алгоритмы: построение и анализ, М.: МЦНМО, 2002.
- Вставская Е. Структуры данных: деревья, [Электронный ресурс] — режим доступа: https://prog-cpp.ru/data-tree/. Дата обращения: 25.05.2014.
Источник