[Home]
[Chapter]
[Contents]
[Previous Algorithm]
[Next Algorithm]


Height-balanced tree (AVL) insertion


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;

C source (3413.ins.c) Pascal source (3413.ins.p)



© Addison-Wesley Publishing Co. Inc.