Internal path reduction trees: insertion


procedure checkrots( var t : tree ); {*** check need for rotations ***} var wl, wll, wr, wrr : integer; begin if t <> nil then with t^ do begin wl := wt( left ); wr := wt( right ); if wr > wl then begin {*** left rotation needed ***} wrr := wt( right^.right ); if (wrr > wl) and (2*wrr >= wr) then begin lrot( t ); checkrots( left ) end else if wr-wrr > wl then begin rrot( right ); lrot( t ); Rots := Rots-1; checkrots( left ); checkrots( right ) end end else if wl > wr then begin {*** right rotation needed ***} wll := wt( left^.left ); if (wll > wr) and (2*wll >= wl) then begin rrot( t ); checkrots( right ) end else if wl-wll > wr then begin lrot( left ); rrot( t ); Rots := Rots-1; checkrots( left ); checkrots( right ) end end end end; procedure insert( key : typekey; var t : tree ); begin if t = nil then begin t := NewNode( key, nil, nil ); t^.weight := 2 end else if t^.k = key then i:=i-1 else with t^ do begin if k < key then insert( key, right ) else insert( key, left ); weight := wt( left ) + wt( right ); checkrots( t ) end end;

Pascal source (3415.ins.p)



© Addison-Wesley Publishing Co. Inc.