|
<![CDATA[
function insert( key : typekey; var t : tree ) : integer;
var incr : integer;
begin
insert := 0;
if t = nil then begin
t := NewNode( key, nil, nil );
t^.bal := 0;
insert := 1
end
else if t^.k = key then
Error {*** Key already in table ***}
else with t^ do begin
if k < key then incr := insert( key, right )
else incr := -insert( key, left );
bal := bal + incr;
if (incr <> 0) and (bal <> 0) then
if bal < -1 then
{*** left subtree too tall: right rotation needed ***}
if left^.bal < 0 then rrot( t )
else begin lrot( left ); rrot( t ) end
else if bal > 1 then
{*** right subtree too tall: left rotation needed ***}
if right^.bal > 0 then lrot( t )
else begin rrot( right ); lrot( t ) end
else insert := 1;
end
end;
]]> |
![[Home]](../../images/home_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (3413.ins.c) 