
 { treaps
Tue Sep  7 12:46:27 PDT 2004
Mon Apr  4 04:40:58 PDT 2005
 }

  function treapFind(root:treap; var key:idType):treap; {X}
   begin
    if root = nil then treapFind := nil
    else if root^.item = key then treapFind := root
    else if key < root^.item then treapFind := treapFind(root^.left,key)
    else treapFind := treapFind(root^.right,key);
   end;

  procedure treapRotateLeft(var root:treap); {X}
    {input conditions: root <> nil, root^.right <> nil}
   var
    r,s:treap;
   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 treapRotateRight(var root:treap); {X}
    {input conditions: root <> nil, root^.left <> nil}
   var
    r,s:treap;
   begin
    if root = nil then writeln('Cannot right rotate')
    else if root^.left = nil then writeln('Cannot right rotate')
    else
     begin
      r := root;
      s := root^.left;
      r^.left := s^.right;
      s^.right := r; 
      root := s;
     end
   end;

  procedure treapWrite(root:treap;level:integer);
   var
    i:integer;
   begin
    if root <> nil then
     begin
      treapWrite(root^.right,level+1);
      write('':level);writeln(root^.item,'':27-level,root^.priority:17:14);
      treapWrite(root^.left,level+1);
     end;
   end;

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

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

  function treapAveragePathLength(root:treap):double;
   begin
    if root = nil then
     treapAveragePathLength := 0
    else
     treapAveragePathLength := treapTotalPathLength(root,0)/treapCount(root);
   end;

  procedure treapDelete(var root:treap; x:idType); {X}
   begin
    if root <> nil then
     if root^.item = x then
      if root^.right = nil then
       root := root^.left
      else if root^.left = nil then
       root := root^.right
      else if root^.left^.priority > root^.right^.priority then
       begin
        treapRotateLeft(root);
        treapDelete(root^.left,x);
       end
      else
       begin
        treapRotateRight(root);
        treapDelete(root^.right,x);
       end
    else if x < root^.item then treapDelete(root^.left,x)
    else treapDelete(root^.right,x);
   end;
       
  procedure treapInsert(var root:treap; key:idType); {X}
   begin
    if root = nil then
     begin
      new(root);
      root^.item := key;
      root^.priority := random;
      root^.left := nil;
      root^.right := nil;
     end
    else if root^.item = key then writeln('Duplicate item not inserted.')
    else if key < root^.item then
     begin
      treapInsert(root^.left,key);
      if root^.priority > root^.left^.priority then treapRotateRight(root);
     end
    else
     begin
      treapInsert(root^.right,key);
      if root^.priority > root^.right^.priority then treapRotateLeft(root);
     end
   end;

  procedure itemLoadTreap(var root:treap); {X}
   var
    x:idType;
   begin
    root := nil;
    while not eof do
     begin
      readln(x);
      treapInsert(root, x);
     end;
   end;

