Дерево двоичного поиска: различия между версиями
KVN (обсуждение | вклад) (Новая страница: «'''Деревом двоичного поиска''' (Binary search tree) для множества чисел <nowiki><math>S<\math> называется </nowiki>помеченное бинарное дерево, в котором каждая вершина <\math>v<\math> помечена числом <\math>l(v)\in S<\math> и которое удовлетворяет следую...») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Деревом двоичного поиска''' (Binary search tree) для множества чисел | '''Деревом двоичного поиска''' (''[[Binary search tree]]'') для множества чисел <nowiki><math>S</math> называется [[Помеченный граф|помеченное]] [[Бинарное дерево|бинарное]] дерево, в котором каждая [[вершина]] <\math>v<nowiki></math></nowiki> помечена числом <\math>l(v)\in S<nowiki></math></nowiki> и которое удовлетворяет следующим условиям: | ||
а) | а) <nowiki><math>l(u)<l(v)</math> для всех вершин <math>u,v</math>, если вершина <math>u</math> находится в левом поддереве вершины <math>v</math> (т.е. в поддереве, корень которого --- левый сын <math>v</math>); | ||
б) | б) <nowiki><math>l(u)>l(v)</math> для всех вершин <math>u,v</math>, если вершина <math>u</math> находится в правом поддереве вершины <math>v</math> (т.е. в поддереве, корень которого --- правый сын <math>v</math>); | ||
в) для всякого числа | в) для всякого числа <nowiki><math>a \in S</math> существует единственная вершина <math>v</math>, для которой <math>l(v)=a</math>. | ||
Другое название — ''Поисковое дерево''. | Другое название — ''Поисковое дерево''. | ||
== Литература == | ==Литература== | ||
*Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
*Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. | |||
[[:Категория:Деревья|Деревья]] [[:Категория:Информационные деревья|Информационные деревья]] [[:Категория:Основные термины|Основные термины]] | [[:Категория:Деревья|Деревья]] [[:Категория:Информационные деревья|Информационные деревья]] [[:Категория:Основные термины|Основные термины]] | ||
Версия от 21:06, 19 ноября 2024
Деревом двоичного поиска (Binary search tree) для множества чисел <nowiki>[math]\displaystyle{ S }[/math] называется помеченное бинарное дерево, в котором каждая вершина <\math>v</math> помечена числом <\math>l(v)\in S</math> и которое удовлетворяет следующим условиям:
а) <nowiki>[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]);
б) <nowiki>[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]);
в) для всякого числа <nowiki>[math]\displaystyle{ a \in S }[/math] существует единственная вершина [math]\displaystyle{ v }[/math], для которой [math]\displaystyle{ l(v)=a }[/math].
Другое название — Поисковое дерево.
Литература
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
- Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.