[comp.lang.pascal] help - binary search tree

fsbrn@BRL.MIL (Pascal Postman) (12/01/89)

Hi,

I don't keep formal archives of the info-pascal mailing list, just an
automatic copy of every piece of mail.  There haven't been many
programs posted anyway.  Can anyone help Bill?

                                        dsw, fferd
                                        Fred S. Brundick
                                        aka Pascal Postman
                                        USABRL, APG, MD.
                                        <info-pascal-request@brl.mil>

----- Forwarded message # 1:

Received: from smoke.brl.mil by VIM.BRL.MIL id aa04878; 30 Nov 89 12:58 EST
Received: from caviar.nosc.mil by SMOKE.BRL.MIL id aa08849; 30 Nov 89 12:50 EST
Date: 30 Nov 89 09:42:00 PDT
From: William Sweetman <sweetman@caviar.nosc.mil>
Subject: help - binary search tree
To: info-pascal-request <info-pascal-request@BRL.MIL>
Message-ID:  <8911301250.aa08849@SMOKE.BRL.MIL>

help.
looking for a recursive binary search tree procedure written in pascal.
is there one in your archive files??  
i'm at a loss with pascal.
thank you,
-bill sweetman     <sweetman@caviar.nosc.mil>


----- End of forwarded messages

reino@cs.eur.nl (Reino de Boer) (12/01/89)

fsbrn@BRL.MIL (Pascal Postman) writes:

>[...text deleted...] Can anyone help Bill?

>----- Forwarded message # 1:
>looking for a recursive binary search tree procedure written in pascal.

There are several algorithms in Pascal in:
Niklaus Wirth -- Algorithms + Data Structures = Programs
  Prentice Hall (1976)

I think particularly Program 4.4 on pages 203--204 is what you're
looking for.

Hope this helps -- Reino

-- 
Reino R. A. de Boer
Erasmus University Rotterdam ( Informatica )
e-mail: reino@cs.eur.nl

bigelow@hpfcso.HP.COM (Jim Bigelow) (12/02/89)

I suggest that you look at the algorithms and programs in "Algorithms +
Data Structurs = Programs" by N. Wirth.  Chapter 4, Section 4.4 is titled
"Tree Structures"  and subsection 4.4.10 is "Optimal Search Trees."  

From the same book, Page 204, I've paraphrased the following search routine:

procedure search(x:integer; var p:ref);
begin
    if p = nil then
    begin
        { x not in tree, insert or inform user as you wish}
    end else 
    if x < p^.key then search(x,p^.left) else
    if x > p^.key then search*x,p^.right) else
        p^.count := p^.count + 1
end {search};

You'll have to modify the defintion and uses of "ref" which is a pointer to a 
tree node.

Best Regards,

Jim Bigelow
S300 Pascal
Hewlett Packard.