Линейная алгебра и мат. Статистика
Бинарное (двоичное) дерево
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Бинарное (двоичное) дерево поиска
- BSP-дерево
| Бинарное (двоичное) дерево – это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков. Таким образом, бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья. На каждый элемент дерева имеется ровно одна ссылка. В общем случае у бинарного дерева на -ом уровне может быть до вершин.
Бинарное (двоичное) дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. B-дерево — это особый тип сбалансированного дерева поиска, в котором каждый узел может содержать более одного ключа и иметь более двух дочерних элементов. Из-за этого свойства B-дерево называют сильноветвящимся. Оно позволяет хранить много ключей в одном узле и при этом может ссылаться на несколько дочерних узлов. Это значительно уменьшает высоту дерева и, соответственно, обеспечивает более быстрый доступ. BSP-дерево — это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition — двоичное разбиение пространства. BSP-дерево используется для эффективного выполнения следующих операций: Сортировки визуальных объектов в порядке удаления от наблюдателя; Обнаружение столкновений. Основные операции, осуществляемые с бинарными деревьями: создание бинарного дерева; обход бинарного дерева; вставка элемента в бинарное дерево; удаление элемента из бинарного дерева; проверка пустоты бинарного дерева; удаление бинарного дерева; поиск вершины по заданному ключу и т.д. Принципиальное отличие недвоичных деревьев от двоичных состоит в том, что число потомков у вершин может изменяться в достаточно широких пределах. Это не позволяет объявить в каждой вершине какое-то разумное количество ссылочных полей. Недвоичные деревья используются реже двоичных, но, тем не менее, есть круг задач, где они необходимы. Пожалуй, наиболее известным примером недвоичного дерева является хорошо всем знакомая структура каталогов в файловых подсистемах операционных систем. Существуют разные способы описания недвоичных деревьев, среди которых наиболее известны следующие два: сведение недвоичного дерева к двоичному (двоичная модель недвоичного дерева) и описание недвоичного дерева с помощью комбинированной структуры типа «Список списков» (списковая модель недвоичного дерева). Структура данных: ассоциативный массив (словари, хеш-таблицы, основные операции, применение). Ассоциативные массивы можно использовать в качестве более универсальной альтернативы вектору. Однако индексация в этом случае возможна не только по целочисленным индексам, а по любому типу, который удовлетворяет некоторым условиям. Сами эти условия зависят от реализации ассоциативного массива, а индекс называется ключом. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|