Дерево двоичного поиска: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Деревом двоичного поиска''' (''[[Binary search tree]]'') для множества чисел | '''Деревом двоичного поиска''' (''[[Binary search tree]]'') для множества чисел <math>S</math> называется [[Помеченный граф|помеченное]] [[Бинарное дерево|бинарное]] дерево, в котором каждая [[вершина]] <math>v</math> помечена числом <math>l(v)\in S</math> и которое удовлетворяет следующим условиям: | ||
а) | а) <math>l(u)<l(v)</math> для всех вершин <math>u,v</math>, если вершина <math>u</math> находится в левом поддереве вершины <math>v</math> (т.е. в поддереве, корень которого --- левый сын <math>v</math>); | ||
б) | б) <math>l(u)>l(v)</math> для всех вершин <math>u,v</math>, если вершина <math>u</math> находится в правом поддереве вершины <math>v</math> (т.е. в поддереве, корень которого --- правый сын <math>v</math>); | ||
в) для всякого числа | в) для всякого числа <math>a \in S</math> существует единственная вершина <math>v</math>, для которой <math>l(v)=a</math>. | ||
Другое название — ''Поисковое дерево''. | Другое название — ''Поисковое дерево''. | ||
[[Файл: Binary_search_tree.png|275px]] | |||
==Литература== | ==Литература== | ||
| Строка 14: | Строка 16: | ||
*Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. | *Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. | ||
[[ | |||
[[Категория:Деревья]] | |||
[[Категория:Информационные деревья]] | |||
[[Категория:Основные термины]] | |||
Текущая версия от 21:35, 19 ноября 2024
Деревом двоичного поиска (Binary search tree) для множества чисел [math]\displaystyle{ S }[/math] называется помеченное бинарное дерево, в котором каждая вершина [math]\displaystyle{ v }[/math] помечена числом [math]\displaystyle{ l(v)\in S }[/math] и которое удовлетворяет следующим условиям:
а) [math]\displaystyle{ l(u)\lt l(v) }[/math] для всех вершин [math]\displaystyle{ u,v }[/math], если вершина [math]\displaystyle{ u }[/math] находится в левом поддереве вершины [math]\displaystyle{ v }[/math] (т.е. в поддереве, корень которого --- левый сын [math]\displaystyle{ v }[/math]);
б) [math]\displaystyle{ l(u)\gt l(v) }[/math] для всех вершин [math]\displaystyle{ u,v }[/math], если вершина [math]\displaystyle{ u }[/math] находится в правом поддереве вершины [math]\displaystyle{ v }[/math] (т.е. в поддереве, корень которого --- правый сын [math]\displaystyle{ v }[/math]);
в) для всякого числа [math]\displaystyle{ a \in S }[/math] существует единственная вершина [math]\displaystyle{ v }[/math], для которой [math]\displaystyle{ l(v)=a }[/math].
Другое название — Поисковое дерево.
Литература
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
- Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.