Note that your text includes full C++ code for a lot of data structures (page numbers are given below under specific structures): binary search trees, skip lists, randomized binary search trees, splay tres, and hash tables (chaining, linear probing, and simple double hashing), all complete, plus tries (both regular and Patricia) and red-black trees (insertion and search only). These routines are likely to be as good as anything you can download, so use them.

For downloading software: some software is archived and compressed into a .zip file (the standard tool in the Windows world) or into a .tar.gz file (the standard tool in the Unix world). In either case, create a new subdirectory and place the archive file there. If the file is a .zip file, type

unzip file.zip
If the file is a .tar.gz file, type
tar xfz file.tar.gz
Be sure to use the tar program in the directory /usr/local/gnu/bin; this is also where you can find the gunzip program to uncompress a .gz file: typing gunzip file.gz will produce file (and also remove the compressed version); if the file is an archive, you can then type tar xf file.tar to extract its content. If you simply type tar on an AIX machine, you will not get the gnu version, but a much older version that does not support the z (compression/decompression) flag. To make sure all of the gnu tools are available to you, put in your path environment the path /usr/local/gnu/bin.
  • Plain binary search trees:
    Text, pp. 520, 531, 532, and 538 (complete).
  • AVL trees:
    www.enteract.com/~bradapp/ftp/src/libs/C++/AvlTrees.html
    www.uwsg.iu.edu/hypermail/linux/kernel/9912.2/0026.html
    hpux.dsi.unimi.it/hppd/hpux/Languages/avl-1.4.0/readme.html
    phil.ipal.org/freeware/avlmap
    www.enteract.com/~cosine/project/AVLTree/
  • Red-black trees:
    hpux.dsi.unimi.it/hppd/hpux/Languages/avl-1.4.0/readme.html
    www.cs.jhu.edu/~kumar/software.html
    www.enteract.com/~bradapp/ftp/src/libs/C++/RedBlack.tar.gz
    Textbook, p. 568 (insertion only).
  • 2-3 trees (almost the same as red-black):
    www.enteract.com/~bradapp/ftp/src/libs/C++/TwoThree.tar.gz
  • Splay trees:
    sources.isc.org/devel/func/splay-tree.txt
    www.leo.org/pub/comp/usenet/comp.sources.unix/splay-tree/
    www.cs.jhu.edu/~kumar/software.html
    Text, pp. 556 (splay and insert; delete is also based on splay); the rotation programs are from p. 531.
  • Skip lists:
    Text, p. 577, 578, 579, 581 (complete).
  • Tries (AKA digital search trees):
    Text, pp. 630 and 631 (insertion and search, regular tries), pp. 639 and 641 (insertion and search, Patricia tries)
  • Fibonacci heaps:
    resnet.uoregon.edu/~gurney_j/jmpc/fib.html
  • Binomial heaps:
    www.sqrl.org/sqrl/news.html (in libstash)
  • Randomized binary search trees (treaps):
    Textbook, pp. 548 and 551 (complete).
    www.ddj.com/ftp/1997/1997.07/treaps.zip/
  • Hash tables:
    www.ddj.com/ftp/1996/1996.04/hash.zip/
    Text, pp. 592 and 593 (hash functions), p. 598 (chaining), p. 604 (linear probing), p. 609 (double hashing)
  • Ternary search trees (a variation on binary ones!):
    www.ddj.com/ftp/1998/1998_04/ternary.zip/
  • Just about everything (trees, heaps, hash tables, etc.):
    the great LEDA library (C++)
    the much more modest LINK library (C++)
    the graph-oriented Stanford GraphBase of Don Knuth, very good for getting interesting data