9.4.6. Алгоритм удаления из дерева сортировки

Следующий алгоритм удаляет из дерева сортировки узел с указанным ключом. Если узла с указанным ключом нет в дереве, то ничего не делается. Вспомога­тельные процедуры Find и Delete описаны в следующем подразделе.

Алгоритм 9.5. Удаление узла из дерева сортировки

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

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

Find(T, a,p, q, s) { поиск удаляемого узла }

if p = nil then

return Т { нет такого узла — ничего делать не нужно }

end if

if p.r = nil then

Delete(p, q,p.l,s) { случай 1, см. рис. 9.11 слева } else

u:=p.r

if u.l = nil then

u.l: =p.l

Delete(p,q,u,s) { случай 2, см. рис. 9.11 в центре }

else

w : = u;v : = u.l

while v.l  nil do

w : = v; v : =v.l

end while

p.i: = v.i

Delete(v, w, v.r,-1) { случай 3, см. рис. 9.11 справа }

end if

end if

return Т

обоснование

Удаление узла производится перестройкой дерева сортировки. При этом воз­можны три случая (не считая тривиального случая, когда удаляемого узла нет в дереве и ничего делать не нужно).

1. Правая связь удаляемого узла р пуста (см. рис. 9.11 слева). В этом случае левое поддерево 1 узла р подцепляется к родительскому узлу q с той же сто­роны, с которой был подцеплен узел р. Условие дерева сортировки, очевидно, выполняется.

2. Правая связь удаляемого узла р не пуста и ведет в узел и, левая связь кото рого пуста (см. рис. 9.11 в центре). В этом случае левое поддерево 1 узла в подцепляется к узлу и слева, а сам узел и подцепляется к родительскому узлу q с той же стороны, с которой был подцеплен узел р. Нетрудно проверить что условие дерева сортировки выполняется и в этом случае.

Рис. 9.11. Иллюстрация к алгоритму удаления узла из дерева сортировки

3. Правая связь удаляемого узла р не пуста и ведет в узел и, левая связь кото­рого не пуста. Поскольку дерево сортировки конечно, можно спуститься от узла и до узла v, левая связь которого пуста (см. рис. 9.11 справа). В этом случае выполняются два преобразования дерева. Сначала информация в узле р заменяется на информацию узла v. Поскольку узел v находится в правом поддереве узла р к в левом поддереве узла и, имеем p.i < v.i < u.i. Таким образом, после этого преобразования условие дерева сортировки выполняет­ся. Далее правое поддерево 4 узла v подцепляется слева к узлу w, а сам узел v удаляется. Поскольку поддерево 4 входило в левое поддерево узла w, условие дерева сортировки также сохраняется. 

ЗАМЕЧАНИЕ

В книге [11], из которой заимствован данный алгоритм, показано, что хотя алгоритм «вы­глядит несимметричным» (правые и левые связи обрабатываются по-разному), на самом деле в среднем характеристики дерева сортировки не искажаются.