Дерево двоичного поиска
Деревом двоичного поиска (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>.
Другое название — Поисковое дерево.
Литература
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
* Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.