Дерево двоичного поиска

Деревом двоичного поиска (Binary search tree) для множества чисел $S$ называется помеченное бинарное дерево, в котором каждая вершина $v$ помечена числом $l(v)\in S$ и которое удовлетворяет следующим условиям:

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

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

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

Другое название — Поисковое дерево.

Литература

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

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