function merge( a, b : tree ) : tree;
var bota, botb, r, temp : tree;
begin
if a=nil then merge := b
else if b=nil then merge := a
else begin
{*** find bottom of a's rightmost edge ***}
bota := a^.right; a^.right := nil;
{*** bottom of b's leftmost edge ***}
botb := b^.left; b^.left := nil;
r := nil;
{*** merging loop ***}
while (bota<>nil) and (botb<>nil) do
if bota^.k < botb^.k then begin
temp := bota^.right;
if r=nil then bota^.right := bota
else begin
bota^.right := r^.right;
r^.right := bota
end;
r := bota;
bota := temp
end
else begin
temp := botb^.left;
if r=nil then botb^.left := botb
else begin
botb^.left := r^.left;
r^.left := botb
end;
r := botb;
botb := temp
end;
{*** one edge is exhausted, finish merge ***}
if botb=nil then begin
a^.right := r^.right;
r^.right := bota;
merge := a
end
else begin
b^.left := r^.left;
r^.left := botb;
merge := b
end
end
end;
|