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

Следующий алгоритм вставляет в дерево сортировки узел с указанным ключом. Если узел с указанным ключом уже есть в дереве, то ничего не делается. Вспо­могательная функция 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

обоснование

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