Древовидные структуры данных реферат

Обновлено: 25.06.2024

Целью данной курсовой работы является исследование одной из важных разновидностей деревьев – пирамиды.

Для достижения данной цели нужно выполнить следующие задачи:

1.раскрыть понятие дерева;
2.охарактеризовать бинарные (двоичные) деревья;
3.ввести понятие пирамиды;
4.изучить способы реализации пирамиды;
5.реализовать сортировку на основе пирамиды.
Объектом являются нелинейные структуры данных. Предметом исследования курсовой работы выступает одна из разновидностей двоичных деревьев – пирамида.

Содержание работы
Содержимое работы - 1 файл

КУРСОВАЯ ГОТОВАЯ.doc

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Факультет информационных технологий

Кафедра управления и информатики в технических системах

Задание на курсовую работу

Реализация прикладной задачи с использованием пирамиды

Исходные данные: Массив, нелинейные структуры данных, пирамида.

Перечень подлежащих разработке вопросов:

а) раскрыть понятие дерева;

б) охарактеризовать бинарные (двоичные) деревья;

в) ввести понятие пирамиды;

г) изучить способы реализации пирамиды;

д) реализовать сортировку на основе пирамиды.

Перечень графического материала:

Рис унки, характеризующие структуру дерева.

Курсовая работа содержит 25 страниц, в том числе 3 рисунка, 1 таблица, 7 источников и 2 приложения. В данной курсовой работе изложена теория, связанная с понятием дерева, бинарных деревьев, двоичных деревьев поиска. Вводится понятие пирамиды, а так же программная реализация, основные операции (создание, удаление, добавление, обход и сортировки).

В курсовой работе изложены основные понятия деревьев и представлены способы реализации пирамиды на практике.

Как известно, деревья появились уже на третий день сотворения мира и на протяжении веков древовидные структуры (особенно генеалогические деревья) очень широко применяются. Как математический объект понятие дерева было впервые формально определено в работе Г.Р. Кирхгофа. Он использовал свободные деревья для поиска набора фундаментальных циклов и электрической цепи, которые теперь носят его имя. Спустя десятки лет термин дерево появился в работах Артура Кэли. Он не знал о работах Кирхгофа, и свои исследования начал, изучив структуру алгебраических формул. Позднее Кэли продолжил их в основном для изучения задач. Древовидные структуры так же независимо изучались М.Э. Жорданом и К.И. Боркарелом.

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

Целью данной курсовой работы является исследование одной из важных разновидностей деревьев – пирамиды.

Для достижения данной цели нужно выполнить следующие задачи:

  1. раскрыть понятие дерева;
  2. охарактеризовать бинарные (двоичные) деревья;
  3. ввести понятие пирамиды;
  4. изучить способы реализации пирамиды;
  5. реализовать сортировку на основе пирамиды.

Объектом являются нелинейные структуры данных. Предметом исследования курсовой работы выступает одна из разновидностей двоичных деревьев – пирамида.

1.1.1 Определение. Основные понятия

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

Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья 'растут' вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.

Узлы самого нижнего уровня дерева называются листовыми узлами или листьями. Так как они находятся на самом нижнем уровне, они не имеют никаких потомков.

Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом.

Высотой поддерева будем считать максимальную длину цепи y1, …,его вершин такую, что yi+1 – потомок yi для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.

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

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

Классификацию деревьев можно провести по разным признакам.

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

Двоичное дерево: каждая вершина может иметь не более двух потомков.

Недвоичное дерево: вершины могут иметь любое число потомков.

На рисунке 1 представлены двоичное и недвоичное деревья.

Рисунок 1 – Двоичное и недвоичное деревья

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

На рисунке 2 представлены 2 простейших упорядоченных дерева.

[2] Дональд Э. Кнут, Глава 2.3. Деревья. – Искусство программирования. — М.: Вильямс, 2000 — 832 с.

Рисунок 2 – Упорядоченные деревья

1.2 Двоичные деревья

1.2.1 Определение. Основные понятия

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

- Каждая вершина имеет не более двух детей и не более одного родителя.

- Одна вершина, не имеющая ни детей, ни родителей, является двоичным деревом.

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

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

1.2.2 Программная реализация

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

Left, Right: PTree;

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

Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Важное свойство такого дерева: все элементы его различны. Название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n)=C*log 2 n (в худшем случае O(n)=n).

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

В настоящее время разработаны и употребляются на персональных компьютерах около двадцати систем управления базами данных.

Начиная с 60-х годов для работы с данными, стали употреблять особенные программные комплексы, называемые системами управления базами данных (СУБД). Системы управления базами данных отвечают за:

физическое размещение данных и их описаний;

поддержание баз данных в актуальном состоянии;

защиту данных от некорректных обновлений и несанкционированного доступа;

В зависимости от способа организации (модели) данных в базах данных (БД) их разделяют на а) иерархические, б) сетевые модели, в) реляционные модели и г) объектно-ориентированные модели СУБД. Однако в большинстве учебных материалов обычно различают три класса СУБД, обеспечивающих работу:

2) сетевых и 3) реляционных моделей.

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

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

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


К каждой записи базы данных существует только один (иерархический) путь от корневой записи. Например, как видно из рис.2, для записей С4 путь проходит через записи А и В3.

Основными информационными единицами в иерархической модели данных являются сегмент и поле.

Поле данных определяется как наименьшая неделимая единица данных, доступная пользователю.

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

Иерархическая модель представляет собой связный неориентированный гpaф древовидной структуры, объединяющий сегменты. Иерархическая база данных состоит из упорядоченного набора деревьев.

Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных.

Атрибут (элемент данных) - наименьшая единица структуры данных. Обычно каждому элементу при описании базы данных присваивается уникальное имя. По этому имени к нему обращаются при обработке. Элемент данных также часто называют полем.

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

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

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

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

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

ДОБАВИТЬ в базу данных новую запись. Для корневой записи обязательно формирование значения ключа.

ИЗМЕНИТЬ значение данных предварительно извлеченной записи. Ключевые данные не должны подвергаться изменениям.

УДАЛИТЬ некоторую запись и все подчиненные ей записи.

ИЗВЛЕЧЬ корневую запись по ключевому значению, допускается также последовательный просмотр корневых записей

извлечь следующую запись (следующая запись извлекается в порядке левостороннего обхода дерева)

В операции ИЗВЛЕЧЬ допускается задание условий выборки (например, извлечь сотрудников с окладом более 1 тысячи руб.)

Все операции изменения применяются только к одной "текущей" записи (которая предварительно извлечена из базы данных). Такой подход к манипулированию данных получил название "навигационного".

иерархическая модель база связь

В рамках иерархической модели выделяют языковые средства описания данных (ЯОД) и средства манипулирования данными (ЯМД). Каждая физическая база описывается набором операторов, обусловливающих как ее логическую структуру, так и структуру хранения БД. При этом способ доступа устанавливает способ организации взаимосвязи физических записей.

Определены следующие способы доступа:

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

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

К достоинствам иерархической модели данных относятся эффективное использование памяти ЭВМ и неплохие показатели времени выполнения основных операций над данными. Иерархическая модель данных удобна для работы с иерархически упорядоченной информацией.

Недостатком иерархической модели является ее громоздкость для обработки информации с достаточно сложными логическими связями, а также сложность понимания для обычного пользователя.

Типичным представителем (наиболее известным и распространенным) является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г.

Time-Shared Date Management System (TDMS) компании Development Corporation;

Mark IV Multi - Access Retrieval System компании Control Data Corporation;

System - 2000 разработки SAS-Institute;

Серверы каталогов, такие, как LDAP и Active Directory (допускают чёткое представление в виде дерева).

По принципу иерархической БД построены иерархические файловые системы и Реестр Windows.

С ростом популярности СУБД в 70-80-х годах появилось множество различных моделей данных. У каждой из них имелись свои достоинства и недостатки, которые сыграли ключевую роль в развитии реляционной модели данных, появившейся во многом благодаря стремлению упростить и упорядочить первые модели данных.

Современные БД основываются на использовании моделей данных, позволяющих описывать объекты предметных областей и взаимосвязи между ними. Модели данных используются, как для концептуального, так и для логического и физического представления данных.

Основное различие между этими моделями данных состоит в способах описания взаимодействий между объектами и атрибутами.

1. Зеленков Ю.А. "Введение в базы данных". Учебный курс.

2. Bachman C. W. The Programmer as Navigator, CACM 16.11, Nov. 1973.

3. Журнал "СУБД" № 1, 1995. Реляционная модель данных для больших совместно используемых банков данных

Древовидной структурой данных называется конечное множество элементов-узлов, между которыми существуют отношения — связь исходного и порожденного. Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева — его корень. Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении. Далее… Читать ещё >

Древовидные структуры данных ( реферат , курсовая , диплом , контрольная )

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

Если использовать рекурсивное определение, предложенное Н. Виртом, то древовидная структура данных с базовым типом t — это либо пустая структура, либо узел типа t, с которым связано конечное множество древовидных структур с базовым типом t, называемых поддеревьями.

Далее дадим определения, используемые при оперировании древовидными структурами.

Если узел y находится непосредственно под узлом х, то узел y называется непосредственным потомком узла х, а х — непосредственным предком узла у, т. е. , если узел хнаходится на i-ом уровне, то соответственно узел y находится на (i + 1) — ом уровне.

Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева — его корень.

Узлы дерева, у которых не имеется потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева [5, "https://nanayna.ru"].

Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении.

Если пройти от корня дерева к некоторому конкретному узлу, то количество ветвей дерева, которое при этом будет пройдено, называется длиной пути для этого узла. Если все ветви (узлы) у дерева упорядочены, то дерево называется упорядоченным.

Частным случаем древовидных структур являются бинарные деревья. Это деревья, в которых каждый потомок имеет не более двух потомков, называемых левым и правым поддеревьями. Таким образом, бинарное дерево — это древовидная структура, степень которой равна двум.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

4 Kd-деревья

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


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

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

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

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

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

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

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


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

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

Читайте также: