Двоичное дерево | это... Что такое Двоичное дерево? (original) (raw)

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

Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.

Рекурсивное определение

Существует следующее рекурсивное определение двоичного дерева (см. БНФ):

<дерево> ::= ( <данные> <дерево> <дерево> ) | 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. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.

Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины m=(data, left, right) есть два потомка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.

Применение

Многие полезные структуры данных основаны на двоичном дереве:

	Двоичное дерево на Викискладе?

Дерево (структура данных)
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура
Двоичные деревья	Двоичное дерево · T-дерево
Самобалансирующиеся двоичные деревья	АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи
B-деревья	B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево
Префиксные деревья	Суффиксное дерево · Radix tree · Ternary search tree
Двоичное разбиение пространства	k-мерное дерево · VP-дерево
Недвоичные деревья	Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево
Разбиение пространства	R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков
Другие деревья	Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree
Алгоритмы	Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева