Двоичное дерево: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Переписал определение, вставил более удачный рисунок, но дальше нужно править. |
м косметика |
||
| Строка 1: | Строка 1: | ||
[[Image:Binary search tree.svg|right|200px|thumb| Пример двоичного дерева]] |
[[Image:Binary search tree.svg|right|200px|thumb| Пример двоичного дерева]] |
||
'''Двои́чное де́рево''' — [[структура данных]], являющаяся одной из программных реализаций [[Дерево (теория графов)#Двоичное дерево|двоичного дерева теории графов]] и построена по следующим правилам: |
'''Двои́чное де́рево''' — [[структура данных]], являющаяся одной из программных реализаций [[Дерево (теория графов)#Двоичное дерево|двоичного дерева теории графов]] и построена по следующим правилам: |
||
: 1. Двоичное дерево состоит из узлов (вершин) — записей вида (parent, data, left, right), где parent - ссылка на родительский элемент, data — некоторые данные привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый |
: 1. Двоичное дерево состоит из узлов (вершин) — записей вида (parent, data, left, right), где parent - ссылка на родительский элемент, data — некоторые данные привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Поле parent для корневого элемента является пустым или неопределённым в зависимости от реализации. |
||
: 2. Для любой вершины x выполняется условие: data[left[x]] ≤ data[x] ≤ data[right[x]], т. е. данные родительского узла больше или равны данным левого сына и меньше или равны значению правого. |
: 2. Для любой вершины x выполняется условие: data[left[x]] ≤ data[x] ≤ data[right[x]], т. е. данные родительского узла больше или равны данным левого сына и меньше или равны значению правого. |
||
Версия от 15:32, 23 сентября 2009
Двои́чное де́рево — структура данных, являющаяся одной из программных реализаций двоичного дерева теории графов и построена по следующим правилам:
- 1. Двоичное дерево состоит из узлов (вершин) — записей вида (parent, data, left, right), где parent - ссылка на родительский элемент, data — некоторые данные привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Поле parent для корневого элемента является пустым или неопределённым в зависимости от реализации.
- 2. Для любой вершины x выполняется условие: data[left[x]] ≤ data[x] ≤ data[right[x]], т. е. данные родительского узла больше или равны данным левого сына и меньше или равны значению правого.
Не следует путать двоичное дерево с кучей.
Рекурсивное определение
Существует следующее рекурсивное определение двоичного дерева (см. БНФ):
<дерево> ::= ( <данные> <дерево> <дерево> ) | 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)
)
)
|
 |
Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, left, right) есть два ребёнка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.
Применение
Многие полезные структуры данных основаны на двоичном дереве:
Двоичное дерево применяется в соответствующем алгоритме сортировки.