![]()
Двоичное дерево
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево является упорядоченным ориентированным деревом[1].
Для практических целей обычно используют два подвида двоичных деревьев — двоичное дерево поиска и двоичная куча.
![]()
![]()
Рекурсивное определение![]()
Править
Существует следующее рекурсивное определение двоичного дерева (см. БНФ):
<двоичное дерево> ::= ( <данные> <двоичное дерево> <двоичное дерево> ) | null .
То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или конечным (терминальным) узлом[2].
Например, показанное справа на рис. 1 дерево согласно этой грамматике можно было бы записать так:
(m
(e
(c
(a null null)
null
)
(g
null
(k null null)
)
)
(s
(p (o null null) (s null null) )
(y null null)
)
)
|
 Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту. |
Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины m = (data, left, right) есть два потомка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right[3].
![]()
![]()
Применение![]()
Править
Многие полезные структуры данных основаны на двоичном дереве:
![]()
![]()
Примечания![]()
Править
↑
Двоичное дерево. (неопр.) kvodo.ru. Дата обращения: 1 марта 2019. Архивировано 2 марта 2019 года.
↑
Дерево (неопр.). Дата обращения: 1 марта 2019. Архивировано 2 марта 2019 года.
↑
Двоичные деревья поиска: начальные сведения (неопр.). algolist.manual.ru. Дата обращения: 1 марта 2019. Архивировано 14 июля 2019 года.
