program splay (input, output);
{splaying, straightforward but not fastest possible}
  type
    ref = ^node;
    node = record
        key: integer;
        count: integer;
        left, right: ref;
      end;
  var
    root: ref;
    probes: longint;
    sp: integer;
    stack: array[1..100] of record
        node: ref;
        direct: (none, left, right)
      end;

  procedure access (x: integer; var p: ref; var found: boolean);
    var
      p1, p2: ref;

  begin
    if p = nil then
      begin
        sp := sp - 1;
        found := false
      end
    else if x < p^.key then
      begin
        stack[sp].node := p;
        sp := sp + 1;
        stack[sp].direct := left;
        access(x, p^.left, found);
      end
    else if x > p^.key then
      begin
        stack[sp].node := p;
        sp := sp + 1;
        stack[sp].direct := right;
        access(x, p^.right, found);
      end
    else
      begin
        stack[sp].node := p;
        p^.count := p^.count + 1;
        found := true
      end
  end; {access}

  procedure ll_rotation (var p: ref);
    var
      p1: ref;
  begin
    p1 := p^.left;
     {single LL rotation}
    p^.left := p1^.right;
    p1^.right := p;
    p := p1
  end;

  procedure rr_rotation (var p: ref);
    var
      p1: ref;
  begin
    p1 := p^.right;
     {single RR rotation}
    p^.right := p1^.left;
    p1^.left := p;
    p := p1
  end;

  procedure lr_rotation (var p: ref);
    var
      p1, p2: ref;
  begin
    p1 := p^.left;
   {double LR rotation}
    p2 := p1^.right;
    p1^.right := p2^.left;
    p2^.left := p1;
    p^.left := p2^.right;
    p2^.right := p;
    p := p2
  end;

  procedure rl_rotation (var p: ref);
    var
      p1, p2: ref;
  begin
    p1 := p^.right;
  {double rl rotation}
    p2 := p1^.left;
    p1^.left := p2^.right;
    p2^.right := p1;
    p^.right := p2^.left;
    p2^.left := p;
    p := p2
  end;

  procedure splay;
  begin
    while sp > 1 do
      if sp = 2 then
        if stack[sp].direct = left then
          begin
             {ll rotate for zig}
            ll_rotation(root);
            sp := 0
          end
        else
          begin
             {rr rotate for zig}
            rr_rotation(root);
            sp := 0
          end
      else if stack[sp].direct = left then
        if stack[sp - 1].direct = left then
          begin
             {two ll rotations for zig-zig}
            if stack[sp - 2].direct = left then
              begin
                ll_rotation(stack[sp - 3].node^.left);
                ll_rotation(stack[sp - 3].node^.left);
              end
            else if stack[sp - 2].direct = right then
              begin
                ll_rotation(stack[sp - 3].node^.right);
                ll_rotation(stack[sp - 3].node^.right)
              end
            else
              begin
                ll_rotation(root);
                ll_rotation(root)
              end;
            stack[sp - 2].node := stack[sp].node;
            sp := sp - 2
          end
        else
          begin
             {rl rotation for zig-zag}
            if stack[sp - 2].direct = left then
              rl_rotation(stack[sp - 3].node^.left)
            else if stack[sp - 2].direct = right then
              rl_rotation(stack[sp - 3].node^.right)
            else
              rl_rotation(root);
            stack[sp - 2].node := stack[sp].node;
            sp := sp - 2
          end
      else if stack[sp - 1].direct = right then
        begin
           {two rr rotations for zig-zig}
          if stack[sp - 2].direct = left then
            begin
              rr_rotation(stack[sp - 3].node^.left);
              rr_rotation(stack[sp - 3].node^.left);
            end
          else if stack[sp - 2].direct = right then
            begin
              rr_rotation(stack[sp - 3].node^.right);
              rr_rotation(stack[sp - 3].node^.right)
            end
          else
            begin
              rr_rotation(root);
              rr_rotation(root)
            end;
          stack[sp - 2].node := stack[sp].node;
          sp := sp - 2
        end
      else
        begin
           {lr rotation for zig-zag}
          if stack[sp - 2].direct = left then
            lr_rotation(stack[sp - 3].node^.left)
          else if stack[sp - 2].direct = right then
            lr_rotation(stack[sp - 3].node^.right)
          else
            lr_rotation(root);
          stack[sp - 2].node := stack[sp].node;
          sp := sp - 2
        end
  end;

  function check (var x: ref; depth: integer): integer;
    var
      l, r: integer;
  begin
    if x = nil then
      check := 0
    else
      begin
        probes := probes + depth * x^.count;
        l := check(x^.left, depth + 1);
        writeln(x^.key);
        r := check(x^.right, depth + 1)
      end
  end;

  procedure main;
    var
      left, right, newkey: ref;
      i, key, dumint: integer;
      num: integer;
      start, stop: longint;
      found: boolean;

    procedure insert;
    begin
      sp := 1;
      stack[sp].direct := none;

      access(key, root, found);
      splay;
      if not found then
        begin
          new(newkey);
          newkey^.key := key;
          newkey^.count := 1;
          if root = nil then
            begin
              left := nil;
              right := nil
            end
          else if root^.key < key then
            begin
              left := root;
              right := root^.right;
              left^.right := nil
            end
          else
            begin
              left := root^.left;
              right := root;
              right^.left := nil
            end;
          root := newkey;
          root^.left := left;
          root^.right := right
        end
    end;

  begin
    writeln('enter number of keys');
    readln(num);
    start := TickCount;
    root := nil;
    for i := 1 to num do
      begin
        key := random;
        insert
      end;
    stop := TickCount;

    probes := 0;
    dumint := check(root, 1);
    writeln('average_probes=', probes / num : 10 : 4);
    writeln('nodes per second=', num * 60.0 / (stop - start) : 10 : 4)
  end;

begin
  main;
end.