{-------------------------------------------------------------}
{	    routines operating on the binary trees	      }
{ Each tree node represents one index term.  The term itself  }
{ is stored two ways, as typed and all-caps.  The latter is   }
{ used for comparison of terms, so that "Apple" = "apple".    }
{ A node anchors a sorted chain of page-numbers, and may hold }
{ the root of an independent sub-tree of sub-terms.  The tree }
{ is ordered so that all terms off the .lson are less than,   }
{ and all terms off the .rson are greater, than this term.    }
{-------------------------------------------------------------}

function makenode(var a, ua : str) : pnode;
   { make a new tree node given term-strings }
   var tn : ^node;
   begin
       new(tn);
       tn^.lson := nil;
       tn^.rson := nil;
       tn^.subt := nil;
       stput(a,tn^.iref);
       stput(ua,tn^.uref);
       tn^.phead := nil;
       tn^.skip := false;
       makenode := tn
   end;

procedure startree(var t:pnode);
   { begin a tree with an artificial node whose term
      is "M" to encourage early balance }
   begin
      t := makenode(initerm,initerm);
      t^.skip := true
   end;

function insert(tree:pnode; var a:str) : pnode;
   { put a new term into a tree, or find it if it is there.
      either way, return the term's node's address.	    }
   var o,p,q : ^node;
       ua    : str;
       r     : relation;
   begin
       stucase(a,ua);
       p := tree;

       repeat
	   r := sbcomp(ua,p^.uref);
	   if r<>equal then
	       if r=less then q := p^.lson
	       else	      q := p^.rson
	   else q := p;
	   o := p;
	   p := q
       until (r=equal) or (p=nil);

       if r=equal then insert := p
       else begin { term doesn't exist in the tree }
	   q := makenode(a,ua);
	   if r=less then o^.lson := q
	   else 	  o^.rson := q;
	   insert := q
       end;
end;
e }
	   q := makenode(a,ua);
	   if r=less then o^.lson := q
	   else 	  o^.rson := q;
	   insert := q