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

'''Деревом двоичного поиска''' (Binary search tree) для множества чисел <nowiki><math>S<\math> называется </nowiki>[[Помеченный граф|помеченное]] [[Бинарное дерево|бинарное]] дерево, в котором каждая [[вершина]] <\math>v<\math> помечена числом <\math>l(v)\in S<\math> и которое удовлетворяет следующим условиям:

а) <nowiki><math>l(u)<l(v)<\math> для всех вершин <math>u,v<\math>, если вершина <math>u<\math> находится в левом поддереве вершины  <math>v<\math> (т.~е. в поддереве, корень которого --- левый сын <math>v<\math>);</nowiki>

б) <nowiki><math>l(u)>l(v)<\math> для всех вершин <math>u,v<\math>, если вершина <math>u<\math> находится в правом поддереве вершины  <math>v<\math> (т.~е. в поддереве, корень которого --- правый сын <math>v<\math>);</nowiki>

в) для всякого числа <nowiki><math>a \in S<\math> существует единственная вершина <math>v<\math>, для которой <math>l(v)=a<\math>.</nowiki>

== Литература ==

<nowiki>*</nowiki> Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

<nowiki>*</nowiki> Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.