
 { bsts
Tue Sep  7 07:44:44 PDT 2004
 }

  function bstFind(root:bst; var key:idType):bst;
   begin
    if root = nil then bstFind := nil
    else if root^.item = key then bstFind := root
    else if key < root^.item then bstFind := bstFind(root^.left,key)
    else bstFind := bstFind(root^.right,key);
   end;

  procedure bstInsert(var root:bst; key:idType);
   begin
    if root = nil then
     begin
      new(root);
      root^.item := key;
      root^.left := nil;
      root^.right := nil;
     end
    else if root^.item = key then writeln('Duplicate item not inserted.')
    else if key < root^.item then bstInsert(root^.left,key)
    else bstInsert(root^.right,key);
   end;

  procedure bstRotateLeft(var root:bst);
    {input conditions: root <> nil, root^.right <> nil}
   var
    r,s:bst;
   begin
    if root = nil then writeln('Cannot left rotate')
    else if root^.right = nil then writeln('Cannot left rotate')
    else
     begin
      r := root;
      s := root^.right;
      r^.right := s^.left;
      s^.left := r; 
      root := s;
     end
   end;

  {procedure bstRotate(var root:bst);}

  procedure bstWrite(root:bst;level:integer);
   var
    i:integer;
   begin
    if root <> nil then
     begin
      bstWrite(root^.right,level+1);
      write('':level);writeln(root^.item);
      bstWrite(root^.left,level+1);
     end;
   end;

  procedure itemLoadBst(var root:bst);
   var
    x:idType;
   begin
    root := nil;
    while not eof do
     begin
      readln(x);
      bstInsert(root, x);
     end;
   end;

  function bstCount(root:bst):integer;
   begin
    if root = nil then bstCount := 0
    else bstCount := 1 + bstCount(root^.left)+bstCount(root^.right);
   end;

  function bstTotalPathLength(root:bst; level:integer):integer;
   begin
    if root = nil then bstTotalPathLength := 0
    else bstTotalPathLength := level
                         + bstTotalPathLength(root^.left,level+1)  
                         + bstTotalPathLength(root^.right,level+1);
   end;

  function bstAveragePathLength(root:bst):double;
   begin
    if root = nil then
     bstAveragePathLength := 0
    else
     bstAveragePathLength := bstTotalPathLength(root,0)/bstCount(root);
   end;

  procedure bstDelete(var root:bst; x:idType);
   begin
{writeln('Deleting ',x);}
    if root <> nil then
     if root^.item = x then
      if root^.right = nil then
{begin}
{writeln('root^.right = nil');}
       root := root^.left
{;end}
      else if root^.left = nil then
{begin}
{writeln('root^.left = nil');}
       root := root^.right
{;end}
      else
       begin
{writeln('Start bstRotateLeft');}
        bstRotateLeft(root);
{writeln('Finish bstRotateLeft');}
        bstDelete(root^.left,x);
       end
    else if x < root^.item then bstDelete(root^.left,x)
    else bstDelete(root^.right,x);
{writeln('Deleted ',x);}
   end;
       
