Двоичное дерево: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м косметика
удалена реклама
 
(не показано 48 промежуточных версий 36 участников)
Строка 1: Строка 1:
'''Двои́чное де́рево''' (Бинарное дерево) — иерархическая [[структура данных]], в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево является упорядоченным [[Дерево (теория графов)|ориентированным деревом]].
[[Image:Binary search tree.svg|right|200px|thumb| Пример двоичного дерева]]
'''Двои́чное де́рево''' — [[структура данных]], являющаяся одной из программных реализаций [[Дерево (теория графов)#Двоичное дерево|двоичного дерева теории графов]] и построена по следующим правилам:
: 1. Двоичное дерево состоит из узлов (вершин) — записей вида (parent, data, left, right), где parent - ссылка на родительский элемент, data — некоторые данные привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Поле parent для корневого элемента является пустым или неопределённым в зависимости от реализации.
: 2. Для любой вершины x выполняется условие: data[left[x]] ≤ data[x] ≤ data[right[x]], т. е. данные родительского узла больше или равны данным левого сына и меньше или равны значению правого.


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


== Рекурсивное определение ==
== Рекурсивное определение ==
Существует следующее рекурсивное определение двоичного дерева (см. [[Форма Бэкуса — Наура|БНФ]]):
Существует следующее рекурсивное определение двоичного дерева (см. [[Форма Бэкуса — Наура|БНФ]]):


<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .
<двоичное дерево> ::= ( <данные> <двоичное дерево> <двоичное дерево> ) | null .


То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом.
То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом.
Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной).
Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или конечным (терминальным) узлом<ref>{{Cite web|url=https://prog-cpp.ru/data-tree/|title=Дерево|accessdate=2019-03-01|archive-date=2019-03-02|archive-url=https://web.archive.org/web/20190302090632/https://prog-cpp.ru/data-tree/|deadlink=no}}</ref>.


Например, показанное справа на рис. 1 дерево, согласно этой грамматике можно было бы записать так:
Например, показанное справа на рис. 1 дерево согласно этой грамматике можно было бы записать так:


{|
{|
Строка 22: Строка 19:
(e
(e
(c
(c
(a nil nil)
(a null null)
nil
null
)
)
(g
(g
nil
null
(k nil nil)
(k null null)
)
)
)
)
(s
(s
(p (o nil nil) (s nil nil) )
(p (o null null) (s null null) )
(y nil nil)
(y null null)
)
)
)
)
Строка 40: Строка 37:
|}
|}


Каждый узел в дереве задаёт ''поддерево'', корнем которого он является. У вершины <tt>n=(data, left, right)</tt> есть два ребёнка (левый и правый) <tt>left</tt> и <tt>right</tt> и, соответственно, два поддерева (левое и правое) с корнями <tt>left</tt> и <tt>right</tt>.
Каждый узел в дереве задаёт ''поддерево'', корнем которого он является. У вершины <tt>m = (data, left, right)</tt> есть два потомка (левый и правый) <tt>left</tt> и <tt>right</tt> и, соответственно, два поддерева (левое и правое) с корнями <tt>left</tt> и <tt>right</tt><ref>{{Cite web|url=http://algolist.manual.ru/ds/btree.php|title=Двоичные деревья поиска: начальные сведения|publisher=algolist.manual.ru|accessdate=2019-03-01|archive-date=2019-07-14|archive-url=https://web.archive.org/web/20190714145450/http://algolist.manual.ru/ds/btree.php|deadlink=no}}</ref>.


== Применение ==
== Применение ==
Многие полезные структуры данных основаны на двоичном дереве:
Многие полезные структуры данных основаны на двоичном дереве:
* [[Двоичное дерево поиска]]
* [[Двоичное дерево поиска]]
* [[Двоичная куча]]
* [[АВЛ-дерево]]
* [[АВЛ-дерево]]
* [[Красно-чёрное дерево]]
* [[Красно-чёрное дерево]]
⚫
* [[Матричное дерево]]
* [[Дерево Фибоначчи]]
* [[Дерево Фибоначчи]]
* [[Суффиксное дерево]]
* [[Суффиксное дерево]]


== Примечания ==
Двоичное дерево применяется в [[Сортировка с помощью двоичного дерева|соответствующем алгоритме сортировки]].
{{примечания}}


== Ссылки ==
⚫
[[Категория:Деревья (структуры данных)]]
{{Навигация}}
[[Категория:Теория графов]]


{{Деревья (структуры данных)}}
{{Link FA|pt}}


⚫
[[Категория:Деревья (структуры данных)]]
[[bg:Двоично дърво]]
[[cs:Binární strom]]
[[de:Binärbaum]]
[[en:Binary tree]]
[[eo:Duuma arbo]]
[[es:Árbol binario]]
[[fi:Binääripuu]]
[[fr:Arbre binaire]]
[[he:עץ בינארי]]
[[id:Pohon biner]]
[[is:Tvíundartré]]
[[it:Albero binario]]
[[ja:二分木]]
[[ko:이진 트리]]
[[pl:Drzewo binarne]]
[[pt:Árvore binária]]
[[ro:Arbore binar]]
[[sk:Binárny strom (teória grafov)]]
[[sl:Dvojiško drevo]]
[[sr:Бинарно стабло]]
[[sv:Binärträd]]
⚫
[[uk:Бінарне дерево]]
[[zh:二叉树]]

Текущая версия от 20:30, 26 февраля 2024

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

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

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

[править | править код]

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

<двоичное дерево> ::= ( <данные> <двоичное дерево> <двоичное дерево> ) | null .

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или конечным (терминальным) узлом[1].

Например, показанное справа на рис. 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[2].

Применение

[править | править код]

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

Примечания

[править | править код]
  1. ↑ Дерево. Дата обращения: 1 марта 2019. Архивировано 2 марта 2019 года.
  2. ↑ Двоичные деревья поиска: начальные сведения. algolist.manual.ru. Дата обращения: 1 марта 2019. Архивировано 14 июля 2019 года.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Двоичное_дерево&oldid=136381987