# Board index » delphi » Binary Search Trees??

## Binary Search Trees??

Hi everybody!

I'm working at a simple LZSS algorithm at the moment, and my problem
is that my longest-match-routine, although 100% asm and well
optimized, simply isn't fast enough. But I've heard of a method called
'Binary Search Trees', which shall be quicker. So, can anyone give me
an _understandable_ description of these, how they work etc., or tell
me where to get such information?

Many thanks in advance!

Joachim Fenkes
j.fen...@public.ndh.com (my father's addr.)

P.S.: Don't ever forget: 42 is the answer!!!

## Re:Binary Search Trees??

In article <3vnpsr\$...@public.ndh.com>,

##### Quote
Joachim Fenkes <j.fen...@public.ndh.com> wrote:
>Hi everybody!

>I'm working at a simple LZSS algorithm at the moment, and my problem
>is that my longest-match-routine, although 100% asm and well
>optimized, simply isn't fast enough. But I've heard of a method called
>'Binary Search Trees', which shall be quicker. So, can anyone give me
>an _understandable_ description of these, how they work etc., or tell
>me where to get such information?

What does LZSS stand for?

A binary search: (Use on a sorted list of fixed size items.)
~~~~~~~~~~~~~~~
Start at the middle of the list.
If the search item is before that point, apply the search to the first
half of the list, otherwise apply the search to the latter half.
When there is a list with one item only, either you have found the
item or the item was not in the list.
At worst, you will retrieve items in log n operations.
2
A binary tree:
~~~~~~~~~~~~~

Each node in the tree has a value, and two pointers to nodes which I
shall call 'left' and 'right'.
The first item added to the tree is the root node.
To add a further item to the tree, compare its value with the root node. If
it is less than the value of that node, apply the same algorithm to
the tree based on the left node. If it is greater, do the same but for
the right node.
Example:             6
/ \
/   \
4    10
/ \     \
3   5    20
/
1

To add the number 2, compare it with 6.
2<6 so use the left branch.
Compare 2 with 4
2<4 so use the left branch.
Compare 2 with 3
2<3 so use the left branch.
Compare 2 with 1
2>1 so use the right branch.
There is no right branch so insert the new value there.
Example:             6
/ \
/   \
4    10
/ \     \
3   5    20
/ \
1   2

Searching the tree is simply:
Start at the root.
Check the current node (if it exists)
If the values are equal, you've found the item.
If the search value is less, go down the left branch
If the search value is more, go down the right branch

The problem with binary trees is that if you are unlucky with the
first node, it is possible for the tree to become heavily laden on one
side. If you want to use a tree and that turns out to be a problem,
look up B-trees in a good algorithms book.

Peter Benie

## Re:Binary Search Trees??

Funny you should ask -- I recently asked about k-d trees (which are k
dimensional binary search trees -- an extension of the ordinary one
dimensional type described in the last post), and got zero response.
After much work I now have a working Turbo Pascal program that implements
these.

The most useful references I found were:

Weiss, Mark Allen, 1995, Data Structures and Algorithm Analysis.
Benjamin/Cummings, Second Edition  (algorithms are in Pascal -- short
treatment of k-d trees in Chapter 12, lots on simpler trees)

Gonnet, G.H., 1984, Handbook of Algorithms and Data Structures.  Addison
Wesley  (I have seen only the first edition, which has code in both
Pascal and C -- there is a second edition, and I would be interested to
know how it differs?  For example, does it still have Pascal code?)

Both these books are good sources of further references.  The Weiss book
is well written for beginners (well, it assumes you already know about
pointers, etc.)

Another question: is there a good place to put Pascal source code in the
public domain -- i.e., an ftp site for Pascal users?
--
Gerry Middleton
Department of Geology, McMaster University
Tel: (905) 525-9140 ext 24187 FAX 522-3141

## Re:Binary Search Trees??

On 3 Aug 1995, Gerard Middleton wrote:

##### Quote
> is there a good place to put Pascal source code in the
> public domain -- i.e., an ftp site for Pascal users?

SWAG (SourceWare Archival Group) is a collection of source code and program
examples for the PASCAL programming language.

SWAG packets are available in 57 different catagories as follows :

ANSI         ARCHIVES     CHARS        CMDLINE      COLOR
COMM         COPYMOVE     CRC          CRT          CURSOR
DATATYPE     DATETIME     DESQVIEW     DIRS         DOS
DRIVES       EGAVGA       ENCRYPT      ENTRY        EXEC
FAQ          FILES        FINDREPL     GRAPHICS     HARDWARE
INTERRUP     ISR          JOYSTICK     KEYBOARD     MAIL
MATH         MEMORY       MENU         MISC         MOUSE
NETWORK      NUMBERS      OOP          PARSING      POINTERS
PRINTING     RECORDS      REDIRECT     SAVESCRN     SCREEN
SCROLL       SORTING      SOUND        STREAMS      STRINGS
TEXTEDIT     TEXTFILE     TEXTWNDW     TIMING       TSR
UNITINFO     WIN-OS2

SWAG Support Team:

Gayle Davis
GDSoft
72067.2...@compuserve.com

Kerry Sokalsky
FalconTech Consulting
kerry.sokal...@canrem.com

Jeff Fanjoy (Micky)
MatrixSoft(tm)
jeff.fan...@westonia.com

All support sites support 9600+ baud or above.

Available at :

Updates ONLY available on COMPUSERVE in the BPASCAL forum, EXEC-PC and CRS
in CANADA.

Available on the Swag-Area in Pascal-Net (2:285/228), the (PDN) Programmer's
Distribution network from various Anonymous-FTP sites.

FREQable  from  1:272/38  <<PRISM  BBS  (914)  344-0350  or 1:272/100 (914)
343-7540  V32BIS  or  The  Squirrel's  Nest  BBS  (909) 338-4748, 1:207/509
82:300/303 MAGIC : ALLSWAG or SWAG

REPORTED INTERNET FTP SITES :

Site              Directory                       IP Number
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garbo.uwasa.fi    pc/turbopas                     193.166.120.5
zeus.ieee.org     pub/fidonet/files/pdnpascl/

USA :  (by state)
-----
LEAPING LOUNGE BBS       Birmingham, AL       (205) 856-2521
MAJESTIC ROYALTY BBS     Phoenix, AZ          (602) 278-1651  1:114/68
SQUIRREL'S NEST BBS      Crestline, CA        (909) 338-4748
THE RALIN SOFTWARE BBS   Fremont, CA          (510) 226-7731
DIGITAL FOREST           Mission Viejo, CA    (714) 586-6142  1:103/985
THE METAL MINOTAUR BBS   Romoland, CA         (909) 928-1983
BOB'S BBS                Sacramento, CA       (916) 929-7511
WB3IKP BBS               Claymont, DE         (302) 798-8186  1:150/220
WINDRAKER INTERNATIONAL  Jacksonville, FL     (904) 388-5297
GREYBEARDS CASTLE        Jacksonville, FL     (904) 783-4549
DEBBIE'S COUCH EBBS #1   Orlando, FL          (407) 290-3211
DEBBIE'S COUCH EBBS #2   Orlando, FL          (407) 292-2528
MICHAEL'S LIAR           Jasper, GA           (404) 735-6454
DEEP SPACE NINE BBS      Smyrna, GA           (404) 432-1262
ANDROID II BBS #1        Snellville, GA       (404) 978-9636
ANDROID II BBS #2        Snellville, GA       (404) 978-6736
THE WORLD'S ADDRESS      Roswell,GA           (404) 992-3109
SAMMY'S LITTER BOX! #1   Waterloo, IA         (319) 232-5627
SAMMY'S LITTER BOX! #2   Waterloo, IA         (319) 234-2858
THE THABES BBS           Boise, ID            (208) 338-5145  1:347/21
THE VOYAGER BBS          Emmett, ID           (208) 365-3902
THE PALACE BBS           Rockford, IL         (815) 229-9873  1:2210/7068
MONOLITH SYSTEMS         Breman, IN           (219) 546-2788
BETACON BBS              Elkhart, IN          (219) 293-6465
GDSOFT BBS               Goshen, IN           (219) 875-8133  MASTER SITE
VISIONARY REALITY BBS    W. Lafayette, IN     (317) 583-1146
THE GUARDIAN BBS         Lebanon, IN          (317) 483-0818
BINARY JUNCTION BBS      Carbondale, KS       (913) 836-7829  1:281/180
PIXMAN BBS               Haverhill, MA        (508) 521-0283  1:324/140
THE NORTH SHORE BBS      Springfield, MA      (413) 783-2802
CITY SCAPE BBS           Westfield, MA        (413) 568-5241  1:321/328
FTB'S PASSPORT BBS       Frederick, MD        (301) 662-9134
HOME SWEET HOME BBS      Holland, MI          (616) 395-9436  1:228/135
THE ABOVE BOARD II #1    Minot AFB, ND        (701) 727-4979
THE ABOVE BOARD II #2    Minot AFB, ND        (701) 727-4842
KB0DSW's Amateur Radio   Minot, ND            (701) 839-2163 1:14/649
SPARKY BYTE'S BBS        Gretna, NE           (402) 332-4740
PSHQ BBS                 Garden City, NY      (718) 454-8564
MR. MACHINIST BBS        Lockport, NY         (716) 434-1448
PRISM BBS (PDN HQ)  #1   New York             (914) 344-0350 1I272/38
PRISM BBS (PDN HQ)  #2   New York             (914) 343-9540 1:272/100
FUNSOFT BBS              Carson, NV           (702) 887-0353
ICE PALACE BBS           Las Vegas, NV        (702) 452-3087 1:209/770
ORION'S BELT BBS         Las Vegas, NV        (702) 362-0963
THE DANGER ZONE          Sparks, NV           (702) 355-7499 1:213/720
BROTHERHOOD OF THE ROSE  Worthington, OH      (614) 431-3442 1:226/230
WILLIAMS COMPUTER SERV   Oregon City, OR      (503) 631-8439 1:105/278
BRAINY'S WORKSHOP        Dallas, OR           (503) 623-2644
ON-SITE PC SERVICES BBS  Portland, OR         (503) 287-6028 1:105/1010
OVER THE HILL BBS        Lancaster, PA        (717) 285-5385
THE NOVICE BBS           Paupack, PA          (717) 857-1381
BEYOND THE O-ZONE BBS    Pittston Twp, PA     (717) 654-4741 1:268/352
THE MONOLITH BBS         Wedgefield, SC       (803) 773-2980
VOYAGER 1 BBS            Memphis, TN          (901) 797-8358
BERMUDA ISLAND BBS       Memphis, TN          (901) 775-5056 1:123/13
SEVENTH HEAVEN BBS #1    Abilene, TX          (915) 698-9515 1:392/20
SEVENTH HEAVEN BBS #2    Abilene, TX          (915) 698-6611 1:392/20
ANYTHING GOES! BBS #1    Houston, TX          (713) 661-7833
ANYTHING GOES! BBS #2    Houston, TX          (713) 661-0917
ANYTHING GOES! BBS #3    Houston, TX          (713) 661-4677
MARTIN CREEK BBS         Tatum, TX            (903) 836-4654
EMERALD COAST BBS #1     Bremerton, WA        (206) 698-7508
EMERALD COAST BBS #2     Bremerton, WA        (206) 692-9905
ROCK ISLAND BBS #1       Friday Harbor, WA    (206) 378-5561
ROCK ISLAND BBS #2       Friday Harbor, WA    (206) 378-6028
THE POINTE BBS           Stevens Pointe, WI   (715) 345-1327

CANADA : ( by province )
--------
QUANTUM BBS HS NODE      Calgary, Alberta     (403) 252-5103
QUANTUM BBS NODE 1       Calgary, Alberta     (403) 252-5119
CRAZY TRAIN II BBS       Victoria, BC         (604) 383-2201  1:340/88
MAXiMUM ENCRYPTiON BBS   Prince Edward Island (902) 827-4353
RIVENDELL BBS            Dartmouth, NS        (902) 463-1988
ACCESS-PC BBS            Scarborough, Ontario (416) 494-9237  1:250/320
DEVELOPER'S BBS          Brampton, Ontario    (905) 457-4806  1:259/226
DIGITAL DATA BBS         Pickering, Ontario   (905) 837-2149
PASCAL PARADISE          Essex, Ontario       (519) 776-4719  1:246/35
JUNKYARD BBS             London, Ontario      (519) 657-1361
PROGRAMMERS SOURCE BBS   Ottawa, Ontario      (613) 837-0413  1:163/319
TREEHOUSE CLUB           Ottawa, Ontario      (613) 825-7666  1:163/416
TOTSE/2 BBS              Spencerville, Ont    (613) 658-5331  1:248/306
CANADA {*word*104}SPACE SYSTEM Toronto, Ontario     (416) 510-2290
BARBARIAN'S BBS          Rouyn-Noranda, PQ    (819) 762-0632

EUROPEAN AND ASIAN SITES : ( by country )
--------------------------
ALGORITHMS ANONYMOUS     Australia            (090) 93-3145
+61-90-93-3145 Int'l
ALWAYS THINKING CONFETTI Flanders, Belgium    +32-23-80-94-23/
+32-23-80-61-57 2:291/754
MAGIC BBS                Welle, Belgium       +32-53-67.19.11 2:291/1200
DANISH KEYBOARD BBS      Copenhagen, Denmark  (+45) 33 25 56 00
NIFLHEIM BBS #1          Mariehamn, Finland   +358-28/17924
NIFLHEIM BBS #2          Mariehamn, Finland   +358-28/17424
A.C.E BBS NODE #1        Paris, France        45.88.75.48
A.C.E BBS NODE #2        Paris, France        45.88.88.89
PROGRAMMER'S TOOLBOX     Reinheim, Germany    +49-6162-82459  2:244/3301
THE STAND BBS            Oberhausen, Germany  +49-208-201933
WORD BBS                 Hamburg, Germany     +49-40-2801230
QUANTUM TRAP (HK) BBS    Sha Tin, Hong Kong   +852-609-2048
EXTASY CITY              Somma Lombardo Italy +039-0331-740728
ANDREWS'S BBS            Riga, Latvia         +371-2-559777   2:5100/33
THE JUDGEMENT DAY BBS    Nuevo Leon, Mexico   52-8-357-8768   4:971/6

HACOM BBS                The Netherlands      +31-33-803610/801882
/806321
KNIGHT LIGHT PCB BBS     The Netherlands      +31-13-681825/678100
/678227/678475
LIONS & PITTAWAY BBS (1) The Netherlands      +31-13-674745   2:285/228
115:115/0
THE LIGHTHOUSE BBS       Almkerk, Netherlands +31-1834-2427
BIG BLUE BBS             Oslo, Norway         +47 22 46 51 27
+47 22 60 95 01 2:210/16
MULTIMEDIA BBS           Oslo, Norway         +47 22 68 49 76
NORWAY PRO PCBOARD       Oslo, Norway         +47 5154 4306
LYNKS BBS                Mem-Martins,Portugal +351-1-9214540  2:362/36
IMAGINE NET BBS          Lisbon, Portugal     +351-1-7786640
OOPS! BBS                Moscow, Russia       +7-095-956-1561 2:5020/269
ENIGMA ][ B.B.X.         Las Palmas G.C.Spain +34-28-648061   2:340/7.0
HOME OF THUNDER BBS      Las Palmas G.C.Spain +34-28-648057   2:340/17.0
ANTARES HUB              Valencia, Spain      +34-6-1994242
LGHQ BBS                 Stockholm, Sweden    (+46) 8 6122064 2:201/503 FREQ
LITTLEBIT MADDER BBS     Transvaal, South Afr +27-12-664-1885
WAR ON VIRUS BBS         Bangkok, Thailand    (66-2) 437-2085
PANDA PASCAL STUDIO      Taipei,Taiwan,R.O.C. +886-2-545-6091 6:720/518
THE POST BBS             Bolton Lancs, U.K.   +44+204-364319  2:250/170
...

read more »

## Re:Binary Search Trees??

##### Quote
In article <3vo31e\$...@lyra.csx.cam.ac.uk>, pjb1...@cam.ac.uk (Peter Benie) writes:

> The problem with binary trees is that if you are unlucky with the
> first node, it is possible for the tree to become heavily laden on one
> side. If you want to use a tree and that turns out to be a problem,
> look up B-trees in a good algorithms book.

If you are extremely unlucky with the first node, say you're sorting names
and the first name is Zzzztra, Zachary, and the rest of the tree is normal,
then the search path to any given node will only be 1 longer than if you
had a better first node.
On average the number of searches is the square root of the number of nodes
in the tree.

--Lars M.

## Re:Binary Search Trees??

I would recommend height-balanced binary trees, sometimes called AVL trees, which
use algorithms to check the balance of a tree after each insertion and deletion,
and so avoid the kind of binary trees that start to resemble linked lists.
On the other hand, the trees remain binary, and so don't demand anything too
sophisticated.

I've used height-balanced binary trees very successfully for a major statistical
software package, and the speed improvement over standard binary trees is dramatic.

The algorithms required are very straightforward for insertion, and can be
found in the text GONNET (and BAEZA-YATES?, I forget) mentioned by Gerard Middleton
in a previous reply; and also (I seem to remember) in one of Knuth's volumes.
However, the only place I've found the algorithms necessary for deletion of
nodes from a height-balanced binary tree is in WIRTH's book ALGORITHMS AND DATA
STRUCTURES, where several pages are devoted to the topic, complete with all
necessary code, including a deletion algorithm. (The deletion algorithm is rather
trickier; many authors seem to have left it as an execise.)

Incidentally, Wirth's deletion algorithm is easily amended if you want to maintain
a node's pointer address together with its contents (which I do). The algorithm in
the book overwrites the contents of the node to be deleted with information shifted
up from its branches, and eventually a redundant node at the bottom of the tree is
removed. In doing so, the correspondence between node address and contents becomes
lost. For most applications, this doesn't matter; for mine it did.

## Re:Binary Search Trees??

I recently coded an AVL tree (named for the inventors/describers --
Adel'son-Vel'skii and Landis, 1962), also known as a height balanced
binary tree.  Basically the same procedure as described by Peter Benie,
but after adding each node you check to see if the tree is balanced, and
if not, you shift pointers accordingly.

I used  Tenenbaum and Augenstein, Data Structures Using Pascal, as my
guide in building this.

The resulting balanced tree yields a search time that is always equal to
or less than the depth (or heigth) of the tree, and this is minimized
since all branches are kept in balance while building the tree.  Makes a
big difference when there is a lot of data.