Структуры данных. Деревья
Статья познакомит вас с понятием дерева как структуры данных, пояснит в каких случаях и для чего можно их применять:
- рассмотрены достоинства и недостатки деревьев относительно списков и массивов, исходя из которых вы сможете выбрать наиболее подходящую структуру данных для своей задачи;
- показаны основные проблемы реализации деревьев поиска, которые должны подтолкнуть вас использовать готовые библиотеки, а не пытаться сделать все самостоятельно;
- описаны Kd-деревья — решаемые проблемы и предлагаемые подходы.
1 Что такое деревья (в программировании)?
Математическое определение дерева — «граф без петель и циклов» вряд-ли пояснит рядовому человеку какие выгоды можно извлечь из такой структуры данных.
В некоторых книгах, посвященным разработке алгоритмов, деревья определяются рекурсивно. Дерево является либо пустым, либо состоит из узла (корня), являющегося родительским узлом для некоторого количества деревьев (это количество определяет арность дерева) [1, 2].
Рабочее определение (в рамках этой статьи): дерево — это способ организации данных в виде иерархической структуры.
Когда применяются древовидные структуры:
- иногда такая иерархия существует в предметной области вашей программы, например, она должна обрабатывать гениалогическое дерево или работать со структурой каталогов на жестком диске. В таких случаях инода имеет смысл сохранить между объектами вашей программы существующие отношения иерархии:
Дерево каталогов операционной системы UNIX - в других случаях между объектами, которые обрабатывает ваша программа отношения иерархии явно не заданы, однако, их можно задать и это сделает обработку данных в программе более удобной. Например, при разработке парсеров или трансляторов полезным может оказаться дерево синтаксического разбора (синтаксическое дерево) [4], хотя в выражениях типа «1+7*3» иерархия операций не так очевидна;
- не секрет, что поиск объектов наиболее эффективен если они упорядочены. В частности, поиск значения в неупорядоченном наборе из 1000 элементов в худшем случае потребует 1000 операций, а в упорядоченном — можно обойтись всего 10.
Дерево каталогов операционной системы UNIXДвоичный поиск [3] выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения — либо левая, либо правая части могут быть «отброшены».
Иерархия — способ упорядочивания объектов, соответственно применять ее можно для ускорения поиска. Именно этому посвящена остальная часть статьи.
2 Деревья и другие структуры данных
Итак, у нас есть много данных — возможно это информация о температуре за несколько лет, а может быть — данные о фирмах в вашем городе. Как хранить их внутри вашего приложения? — Правильный ответ зависит от того, как именно вы будете пользоваться этими данными.
В таблице приведены асимптотические оценки часто используемых операций над некоторыми структурами данных. На случай если вы еще не освоили асимптотический анализ, в таблице показано примерное значение количества действий, необходимых для выполнения операции над контейнером из 10 тысяч элементов.
| Операция | неупорядоченный массив | упорядоченный массив | неупорядоченный двусвязный список | сбалансированное дерево поиска | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 в дерево может выглядеть так:
Пример использования такого алгоритма приведен в таблице:
В качестве упражнения полезно попробовать вставить в дерево узел со значением 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-деревьев, отличающиеся выбором секущей плоскости. Задача: есть множество точек, находящихся на плоскости, нужно выстроить объекты в иерархическую структуру, исходя из их координат для обеспечения эффективного поиска. Описанные ниже подходы можно обобщить до более сложных геометрических объектов (не точек) и пространств больших размерностей. Первый вариант решения:
Пример построения такого дерева приведен на рисунке. Тут плоскость сначала разбита относительно точки А на левую и правую, правая в свою очередь разбита на нижнюю и верхнюю относительно точки С. Нижняя опять разбивается на левую и правую относительно точки D .
С такой структурой данных, алгоритм вывода всех точек, входящих в Прямоугольник может выглядеть так: Цветом на приведенной выше схеме обозначена область поиска. Она не пересекается с областью B (расположенной левее А ). Даже если бы в этой области были миллионы точек — мы «отсекли» бы их за одну итерацию алгоритма — то есть мы получили полноценный двоичный поиск на плоскости. Визуализация алгоритма: При перемещении объектов может возникать необходимость перестроения дерева — если объект переместился из одной области «родительского» объекта в другую. Описанный подход называется Kd-деревья с циклическим проходом по измерениям. Возможны и другие варианты выбора секущей плоскости — например каждый узел квадрадерева делит свою часть плоскости на 4 части (левая верхняя, левая нижняя, правая верхняя, права нижняя). Если в какой-то части оказывается более 1 объекта — то она делится дальше. Октадеревья адаптируют эту идею к трехмерному пространству. Источник |
