Дерево двоичного поиска
Деревом двоичного поиска (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.