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.)

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.

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.)

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

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.)

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