Алгоритм поиска в дереве сортировки.

вход: массив а : 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 > a then

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

else if a[c].k < a then

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

else

return с { нашли искомый ключ }

end if

end while

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

обоснование

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

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

алгоритм 9.3. поиск узла в дереве сортировки

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

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

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

while р  nil do

if a < p.i then

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

else if a > p.i then

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

else

return р { нашли узел }

end if

end while

обоснование

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

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

алгоритм  9.4. вставка узла в дерево сортировки

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

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

if t = nil then

т: = newnode(o) { первый узел в дереве }

return т

end if

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

while true do

if a < 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 > p.i then

if p.i = nil then

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

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

return т

else

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

end if

end if

return т { сюда попали, если уже есть такой ключ! }

end while

обоснование

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

Пошаговое объяснение:

3,14=3,1

l=2πR=2*3,1*10 см=62 см