Двоичное дерево (структура данных)
- Двоичное дерево (структура данных)
-
Двои́чное де́рево — структура данных, являющаяся программной реализацией двоичного дерева (графа). Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные привязанные к узлу, left, right — ссылки на узлы, являющиеся детьми данного узла. Узел left называется левым ребёнком (сыном), а узел right — правым.
Существует следующее рекурсивное определение двоичного дерева (см. БНФ):
<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .
То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной).
Например, показанное справа на рис. 1 дерево, согласно этой грамматике можно было бы записать так:
(m
(e
(c
(a nil nil)
nil
)
(g
nil
(k nil nil)
)
)
(s
(p (o nil nil) (s nil nil) )
(y nil nil)
)
)
|
Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.
|
Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, left, right) есть два ребёнка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.
Многие полезные структуры данных основаны на двоичном дереве:
Есть и другие способы представления двоичного дерева в памяти компьютера, в том числе не основанные на ссылочных типах данных. Например, в структуре данных Двоичная куча используется обыкновенный массив, и считается, что у элемента с индексом K левым и правым ребёнком являются элементы с индексами 2K+1 и 2K+2 соответственно (индексирование начинается с 0).
Wikimedia Foundation.
2010.
Полезное
Смотреть что такое "Двоичное дерево (структура данных)" в других словарях:
Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево одна из наиболее широко распространённых структу … Википедия
Двоичное дерево поиска — Тип Дерево Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(h) O(n) Вставка O(h) O(n) Удаление O(h) O(n) где h высота дерева … Википедия
Двоичное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Для практических целей обычно используют два подвида… … Википедия
Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
Дерево (граф) — В теории графов, дерево связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура тип организации, в котором каждый… … Википедия
Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году … Википедия
Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти … Википедия
Дерево Фибоначчи — АВЛ дерево с наименьшим числом вершин при заданной высоте (глубине). Если для какой либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и … Википедия
Куча (структура данных) — Эта статья о структуре данных в программировании. О динамической области распределения памяти см. Динамически распределяемая память. Пример полной бинарной кучи … Википедия
Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере … Википедия
