Метод поиска в дереве сортировки.

Вход: упорядоченный массив А : array [l..n] of record k: key;i: info end record; ключ a: key.

Выход: индекс записи с искомым ключом а в массиве А или 0, если записи с таким ключом нет.

b: = 1 исходный индекс части массива для поиска

е: = n окончательный индекс доли массива для поиска

while b e do

с: =(b + е)/2 индекс проверяемого элемента (округлый до целого)

if A[c].k gt; a then

е:=с1 продолжаем поиск в первой половине

else if A[c].k lt; a then

b: = с + 1 продолжаем поиск во 2-ой половине

else

return с отыскали искомый ключ

end if

end while

return 0 искомого ключа нет в массиве

обоснование

Для обоснования этого метода достаточно увидеть, что на каждом шаге главного цикла разыскиваемый элемент массива (если он есть) находится меж (включительно) элементами с индексами b и е. Так как спектр поиска на каждом шаге убавляется в два раза, общая трудоемкость не превосходит log2 n.

9.4.4. Метод поиска в дереве сортировки

Последующий метод находит в дереве сортировки узел с обозначенным ключом, если он там есть.

Метод 9.3. Поиск узла в дереве сортировки

Вход: дерево сортировки Т, данное указателем на корень; ключ а.

Выход: указатель р на найденный узел либо nil, если в дереве нет такового ключа.

р: = Т указатель на проверяемый узел

while р nil do

if a lt; p.i then

p:=p.l продолжаем поиск слева

else if a gt; p.i then

p : = p.r продолжаем поиск справа

else

return р отыскали узел

end if

end while

обоснование

Этот алгоритм работает в четком согласовании с определением дерева сортировки: если текущий узел не разыскиваемый, то в зависимости от того, меньше либо больше разыскиваемый ключ по сопоставленью с текущим, нужно продолжать поиск слева или справа, соответственно.

9.4.5. Метод вставки в дерево сортировки

Последующий алгоритм вставляет в дерево сортировки узел с указанным ключом. Если узел с указанным ключом уже есть в дереве, то ничего не делается. Вспомогательная функция NewNode описана в подразделе 9.4.7.

Метод 9.4. Вставка узла в дерево сортировки

Вход: дерево сортировки Т, данное указателем на корень; ключ а.

Выход: модифицированное дерево сортировки Т.

if T = nil then

Т: = NewNode(o) первый узел в дереве

return Т

end if

p: = Т указатель на текущий узел

while true do

if a lt; p.i then

if p.l = nil then

q: = NewNode(a) создаем новый узел

p.l: = q и подцепляем его к р слева

return Т

else

p:=p.l продолжаем поиск места для вставки слева

end if

end if

if a gt; p.i then

if p.i = nil then

q : = NewNode(a) создаем новый узел

p.r:=q и подцепляем его к р справа

return Т

else

р: = р.г продолжаем поиск места для вставки справа

end if

end if

return Т сюда попали, если теснее есть таковой ключ!

end while

обоснование

Алгоритм вставки, в сути, подобен методу поиска: в дереве ищется таковой узел, имеющий свободную связь для подцепления нового узла, чтоб не нарушалось условие дерева сортировки. А конкретно, если новый ключ меньше текущего, то или его можно подцепить слева (если левая связь свободна), или нужно отыскать слева подходящее место. Подобно, если новый ключ больше текущего.