Осуществляется посредством процедуры rb_delete (см. таблицу 6).
Именно здесь приобретает силу замена nil на nul, которая позволяет обходить некоторые граничные случаи. Теперь «nil»-лист логически – вершина, у которой действителен указатель на предка p и цвет c.
Начинаем с обычного удаления вершины из дерева. После чего возникает два случая:
удаление красной вершины не противоречит ни одному условию RB; удаляемая вершина черная – для ее родителя черные высоты детей будут различны[4]. Требуется балансировка.
Второй случай приводит нас к процедуре rb_delete_fixup (Таблица 5). Основной цикл продолжает работу до тех пор, пока вершина, на которую указывает x, не станет черной или, корнем дерева. Однотипные случаи (симметричные) разделяются строчкой (1) кода.
После удаления в ветви дерева, на родителя которой указывает
x, не хватает единицы черноты – исправляем посредством ее брата или родителя. Для подробного разбора кода мы приводим рис. 3, который наглядно иллюстрирует динамику изменения структуры дерева после преобразований
Приложение
|
Индексация |
Код |
№ таблицы и комментарий |
|
Const red=true; black=false; Type t_el=integer; t_rb=^t_rb_rec; t_rb_rec=record el:t_el; l,r,p:t_rb; c:boolean; end; |
Таблица 1 |
|
|
function rb_new(el:t_el; nul:pointer; c:boolean):t_rb; var t:t_rb; begin new(t); t^.l:=nul; t^.r:=nul; t^.el:=el; t^.p:=nul; t^.c:=c; rb_new:=t; end; |
||
|
procedure tree_ins(var t:t_rb; z:t_rb); var y,x:t_rb; begin y:=nul; x:=t; while x<>nul do begin y:=x; if z^.el<x^.el then else x:=x^.r; end; z^.p:=y; if y=nul then t:=z else begin if z^.el<y^.el then else y^.r:=z; end; end; |
Таблица 2 t – корень дерева z – указатель на вставляемый элемент Здесь формируется вызовом функции rb_new. nul:=rb_new(0,nil,black), а <любой элемент дерева>:=rb_new(el,nul,red), что избавляет нас от написания дополнительного кода для инициализации самого nul. |
|
|
1 2 3 4 5 5.1 5.2 6 7 1 2 3 4 5 5.1 5.2 6 7 |
procedure rb_left_rotate(var t:t_rb; x:t_rb); var y:t_rb; begin y:=x^.r; x^.r:=y^.l; if y^.p:=x^.p; if else begin if x=x^.p^.l then else x^.p^.r:=y; end; y^.l:=x; x^.p:=y; end; procedure rb_right_rotate(var t:t_rb; x:t_rb); var y:t_rb; begin y:=x^.l; x^.l:=y^.r; if y^.r<>nil then y^.r^.p:=x; y^.p:=x^.p; if x^.p=nil then t:=y else begin if x=x^.p^.r then x^.p^.r:=y else x^.p^.l:=y; end; y^.r:=x; x^.p:=y; end; |
Таблица 3
Рис. 4
Рис. 5 |
|
1 2 C1-C1’ С2-C2’ С3 С3-C3’ |
Procedure rb_ins(var var y:t_rb; b:boolean; begin tree_ins(t,x); x^.c:=red; while (x<>t)and(x^.p^.c=red) do begin b:=(x^.p=x^.p^.p^.l); if b then else y:=x^.p^.p^.l; if (y<>nul)and(y^.c=red) then begin x^.p^.c:=black; y^.c:=black; x^.p^.p^.c:=red; x:=x^.p^.p; end else begin if b then begin if x=x^.p^.r then begin x:=x^.p; rb_left_rotate(t,x) end; end else begin if x=x^.p^.l then begin x:=x^.p; rb_right_rotate(t,x); end; end; x^.p^.c:=black; x^.p^.p^.c:=red; if b then rb_right_rotate(t,x^.p^.p) else rb_left_rotate(t,x^.p^.p); end; end; t^.c:=black; end; |
Таблица 4 |
|
(1) С1 С2 С3 С4 С1’ С2’ С3’ С4’ |
procedure rb_delete_fixup (var t:trb; x:trb); var w:t_rb; begin while (x<>t)and(x^.c=black) do begin if x=x^.p^.l then begin w:=x^.p^.r; if (w^.c=red) then begin w^.c:=black; x^.p^.c:=red; rb_left_rotate(t,x^.p); w:=x^.p^.r; end; if (w^.l^.c=black)and(w^.r^.c=black) then begin w^.c:=red; x:=x^.p; end else begin if (w^.r^.c=black) then begin w^.l^.c:=black; w^.c:=red; rb_right_rotate(t,w); w:=x^.p^.r; end; w^.c:=x^.p^.c; x^.p^.c:=black; w^.r^.c:=black; rb_left_rotate(t,x^.p); x:=t; end; end else begin w:=x^.p^.l; if (w^.c=red) then begin w^.c:=black; x^.p^.c:=red; rb_right_rotate(t,x^.p); w:=x^.p^.l; end; if (w^.l^.c=black)and(w^.r^.c=black) then begin w^.c:=red; x:=x^.p; end else begin if (w^.l^.c=black) then begin w^.r^.c:=black; w^.c:=red; rb_left_rotate(t,w); w:=x^.p^.l; end; w^.c:=x^.p^.c; x^.p^.c:=black; w^.l^.c:=black; rb_right_rotate(t,x^.p); x:=t; end; end; end; x^.c:=black; end; |
Таблица 5 |
|
function tree_next(x:t_rb):t_rb; var y:t_rb; begin if x^.r<>nul then x:=x^.r; while x^.l<>nul do tree_next:=x; end else begin y:=x^.p; while (y<>nul)and(x=y^.r) do begin x:=y; y:=x^.p; end; tree_next:=y; end; end; |
||
|
function rb_delete(var t:t_rb; z:t_rb):t_rb; var y,x:t_rb; begin if z<>nul then begin if (z^.l=nul)or(z^.r=nul) then y:=z else y:=tree_next(z); if y^.l<>nul then else x:=y^.r; x^.p:=y^.p; if y^.p=nul then t:=x else begin if y=y^.p^.l then y^.p^.l:=x else y^.p^.r:=x; end; if y<>z then if y^.c=black then rb_delete:=y; end else rb_delete:=z; end; |
Таблица 6 |
Loading ...