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

Версия от 21:14, 19 ноября 2024

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

а) [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]);

б) [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]);

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

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

Литература

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

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

@@ Строка 1: / Строка 1: @@
-'''Деревом двоичного поиска''' (''[[Binary search tree]]'') для множества чисел &lt;nowiki&gt;<math>S</math> называется [[Помеченный граф|помеченное]] [[Бинарное дерево|бинарное]] дерево, в котором каждая [[вершина]] <\math>v<nowiki></math></nowiki> помечена числом <\math>l(v)\in S<nowiki></math></nowiki> и которое удовлетворяет следующим условиям:
+'''Деревом двоичного поиска''' (''[[Binary search tree]]'') для множества чисел <math>S</math> называется [[Помеченный граф|помеченное]] [[Бинарное дерево|бинарное]] дерево, в котором каждая [[вершина]] <math>v</math> помечена числом <math>l(v)\in S</math> и которое удовлетворяет следующим условиям:
-а) &lt;nowiki&gt;<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>);
-б) &lt;nowiki&gt;<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>);
-в) для всякого числа &lt;nowiki&gt;<math>a \in S</math> существует единственная вершина <math>v</math>, для которой <math>l(v)=a</math>.
+в) для всякого числа <math>a \in S</math> существует единственная вершина <math>v</math>, для которой <math>l(v)=a</math>.
 Другое название — ''Поисковое дерево''.
@@ Строка 14: / Строка 14: @@
 *Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.
-[[:Категория:Деревья|Деревья]] [[:Категория:Информационные деревья|Информационные деревья]] [[:Категория:Основные термины|Основные термины]]
+[[Категория:Деревья]] [[Категория:Информационные деревья]] [[Категория:Основные термины]]

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

Версия от 21:14, 19 ноября 2024

Литература

Навигация

Поиск