Удаление элемента из бинарного дерева поиска

Удаление элемента из множества.

Удаление – несколько более сложная процедура, чем вставка. Пусть нам надо удалить элемент x. Найдём узел r, который его содержит. Если такого узла найти не удалось, то и делать ничего не надо.

Если у узла r нет сыновей, то всё хорошо: уничтожаем узел и пишем NIL в указатель, который на него ссылался.

Если у узла только один сын, то тоже всё понятно: уничтожаем узел, а в указатель, который на него ссылался, заносим адрес сына.

Наконец, что делать, если у удаляемого узла r два сына? В этом случае нам надо найти в его правом поддереве узел с самым маленьким элементом. Это несложно: берём правого сына и идём от него влево, пока не найдём узел q, у которого левого сына нет. Он и будет искомым. Теперь значение из q запишем в узел r, а удалять будем уже не r, а q. Как это делается, см. выше.

Приведём пример реализации (для удобства он сделан в виде рекурсивной процедуры. Для экономии места в стеке внутренняя рекурсивная процедура вложена во внешнюю и пользуется её параметром x и локальными переменными):

procedure del(var root: PNode; x: Integer);

var

p,q: PNode;

procedure del_rec(var r: PNode);

begin

if r=NIL then exit;

if x<r^.v then begin del_rec(r^.left); exit; end;

if x>r^.v then begin del_rec(r^.right); exit; end;

if (r^.left=NIL) or (r^.right=NIL) then

begin

p:=r;

if r^.left=NIL then r:=r^.right else r:=r^.left;

dispose(p);

exit;

end;

p:=r^.right;

if p^.left=nil then

begin

r^.v:=p^.v;

r^.right:=p^.right;

dispose(p);

exit;

end;

//идём влево, пока есть куда

q:=p^.left;

while q^.left<>NIL do begin

p:=q; q:=q^.left;

end;

//значение из q^ кинем в r^, и удалять будем уже не r^, а q^

r^.v:=q^.v;

p^.left:=q^.right;

dispose(q);

end;

begin

del_rec(root);

end;

 

Рандомизированные деревья. Вставка элемента в рандомизированное бинарное дерево поиска.

· В идеально

сбалансированном дереве трудоемкость поиска составляет О(log₂ n), а построение дерева по трудоемкости пропорционально О(n*log₂ n). Но поддержание идеально сбалансированного дерева при включении новых элементов требует больших затрат, поэтому при балансировке используются более мягкие критерии. Если внешние узлы дерева расположены на одном, в крайнем случае, двух нижних уровнях, то обеспечивается достаточно высокая производительность.

Существует много BST-деревьев, высота которых ограничена величиной 2*log₂ n.

Один из методов балансировки – построение рандомизированных BST-деревьев [4].