einarwh/bst-insert.ps

## bst-insert.ps
/bst-insert {                               % T x
    exch dup                                % x T T
    null eq                                 % x T ?
    {                                       % x T (T is null)
        pop pop                             %
    }
    {                                       % x T
        exch                                % T x
        1 index bst-get-value               % T x v
        2 copy eq                           % T x v x=v?
        {                                   % T x v (v=x, already present!)
            pop pop pop                     %
        }
        {                                   % T x v (v!=x, insert x)
            2 copy                          % T x v x v
            gt                              % T x v (x>v?)
            {                               % T x v (x>v: x -> right)
                2 index                     % T x v T
                bst-get-right-child         % T x v R
                null eq                     % T x v R=null?
                {                           % T x v (R is null, insert directly at R)
                    pop                     % T x
                    bst-create-node         % T N
                    bst-put-right-child     %
                }
                {                           % T x v (R is not null, recurse)
                    pop                     % T x
                    exch                    % x T
                    bst-get-right-child     % x R
                    exch                    % R x
                    bst-insert              %
                } ifelse                    %
            }
            {                               % T x v (x<v: x -> left)
                2 index                     % T x v T
                bst-get-left-child          % T x v L
                null eq                     % T x v L=null?
                {                           % T x v (L is null, insert directly at L)
                    pop                     % T x
                    bst-create-node         % T N
                    bst-put-left-child      %
                }
                {                           % T x v (L is not null, recurse)
                    pop                     % T x
                    exch                    % x T
                    bst-get-left-child      % x L
                    exch                    % L x
                    bst-insert              %
                } ifelse                    %
            } ifelse                        %
        } ifelse                            %
    } ifelse                                %
} def