orz

orz

orz一下

orz

orzAVL神牛

rt

AVL的删除

其实AVL可以来锻炼代码能力和信心，毅力等。。。

VJ上有1081喂狮子，郁闷的出纳员等都可用平衡树。

我的AVL删除代码，大致思想是用这个节点的右子树的最小节点来代替此节点（如果存在的话）

CODE：（x为要删除的节点地址，采用非递归编写，通过1081测试）

procedure del ( x : link );

var

sld, srd, ld, rd : longint;

lp, lv : link;

begin

lv := x;

if lv^.r nil then begin

lp := lv;

lv := lv^.r;

while lv^.l nil do lv := lv^.l;

lp^.v := lv^.v;

lp := lv^.p;

if lv^.r = nil then

if lp^.l = lv then lp^.l := nil else lp^.r := nil

else begin

lv^.r^.p := lp;

if lp^.l = lv then lp^.l := lv^.r else lp^.r := lv^.r;

end;

end

else if lv^.l nil then begin

lp := lv^.p;

if lp^.l = lv then lp^.l := lv^.l else lp^.r := lv^.l;

lv^.l^.p := lp;

end

else begin

lp := lv^.p;

if lp^.l = lv then lp^.l := nil else lp^.r := nil;

end;

lp := lv^.p;

dispose ( lv );

if lp = avl then exit;

while lp avl^.r do begin

if lp^.l = nil then ld := 0 else ld := lp^.l^.dep;

if lp^.r = nil then rd := 0 else rd := lp^.r^.dep;

if ld > rd then lp^.dep := ld else lp^.dep := rd;

inc ( lp^.dep );

if abs ( ld - rd ) < 2 then begin

lp := lp^.p;

continue;

end;

if ld > rd then begin

lv := lp^.l;

if lv^.l = nil then sld := 0 else sld := lv^.l^.dep;

if lv^.r = nil then srd := 0 else srd := lv^.r^.dep;

if sld < srd then l_turn ( lv, lv^.r );

lv := lp^.l;

r_turn ( lp, lv );

end

else begin

lv := lp^.r;

if lv^.l = nil then sld := 0 else sld := lv^.l^.dep;

if lv^.r = nil then srd := 0 else srd := lv^.r^.dep;

if sld > srd then r_turn ( lv, lv^.l );

lv := lp^.r;

l_turn ( lp, lv );

end;

end;

end;

关于L_TURN和R_TURN，就是左右旋转，希望对你有帮助。

SBT好方便,程序不比Treap长多少,请问一下VOJ上有那些题目要用到平衡树?

.

主观的说

AVL不适合竞赛

据说AVL的删除其烦无比，建议你去学SBT，高度也是严格logn，并且可以简单地删除结点。