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

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

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

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

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

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

[[:Категория:Деревья|Деревья]] [[:Категория:Информационные деревья|Информационные деревья]] [[:Категория:Основные термины|Основные термины]]