home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource5 / 347_01 / read.me < prev    next >
Text File  |  1991-10-21  |  6KB  |  149 lines
  1.                  Threaded-Height-Balanced Trees Library
  2.                         TAVL-trees for short
  3.  
  4.                   Copyright (c) 1991  Bert C. Hughes
  5.  
  6. The source files on this disk are an implementation of a hybrid data
  7. structure, the "threaded height-balanced" tree, or tavl-tree.  The AVL
  8. in "tavl" stands for Adelson-Velskii-Landis, inventors of the height-balanced
  9. tree in 1962.  A.J.Perlis and C.Thornton developed the idea of threaded
  10. binary trees as early as 1960.  I simply combined these two well-known
  11. concepts to develop the TAVLtree library.
  12.  
  13. The height-balanced tree, or AVL-tree, is an improvement on the traditional
  14. binary tree (not to be confused with B-trees).  As items are inserted into
  15. the traditional binary tree, the structure of the tree may degrade into some-
  16. thing resembling a linked list, so that retrieval performance suffers.  AVL
  17. trees right this wrong by rebalancing the tree as necessary whenever items are
  18. inserted or deleted.
  19.  
  20. With traditional binary trees and AVL trees it is not efficient to move from
  21. any given node to its successor or predecessor. To find the successor of a
  22. given node in a binary or AVL tree, you must walk through the entire tree
  23. "in-order" until you arrive at the node whose successor you wish to find,
  24. then the next "in-order" node is the desired successor.  Finding the
  25. predecessor is done similarly.  Threaded binary trees solve this problem
  26. by replacing the nil links in leaf & half-leaf nodes with links to the
  27. node's "inorder" successor (or predecessor or both). "Threads" are
  28. distinguished from links with an additional 2 bit field in each node; one
  29. bit for each child link.  With this additional information, the procedure
  30. for moving to a successor node becomes simple, and does not require a stack
  31. or recursion:
  32.  
  33.         function node_succ(P: node_ptr): node_ptr;
  34.            variable Q: node_ptr;
  35.            begin
  36.       1:     Q := RightChild(P);  /* if P's right ptr is a thread all done */
  37.       2:     if (Is_A_Link(RightChild(P)))
  38.       3:        while (Is_A_Link(LeftChild(Q))) /* get leftmost most of */
  39.       4:           Q := LeftChild(Q);           /* P's right subtree - */
  40.       5:     node_succ := Q;                    /* that is P's successor */
  41.            end;
  42.  
  43. A rough order analysis is as follows:
  44.  
  45.     First, assume the tree is perfectly balanced, so that 1/2 of all
  46.     nodes are "leaf" nodes, 1/4 are at the next level up, 1/8 in the
  47.     next level, etc. This is approximately true with height balanced
  48.     trees.  Statement (2) is always executed, and 1/2 the time state-
  49.     ment (2) is false so we are finished. If not, the "while" loop
  50.     is entered, and 1/4 the time it is tested once before success,
  51.     1/8 the time twice, etc.  So the order (big O) is:
  52.  
  53.     Sum = (1 * (1/2)) + (2 * (1/4)) + (3 * (1/8)) + ... + (n * (1/2)power(n))
  54.  
  55.     or Sum = 2,  for O(1), which is same order as an ordinary linked list.
  56.  
  57.  
  58. FILES ON THIS DISK:
  59. -------------------
  60.  
  61.         documentation
  62.         -------------
  63.  
  64.     TAVLTREE.DOC    Reference for TAVL library functions
  65.     READ.ME         This file! General info
  66.     HISTORY.TXT     History of revisions.
  67.     TAVL_TCC.MAK    Sample "make" file for compiling libraries with Turbo C
  68.     TAVL_BCC.MAK    Sample "make" file for compiling libraries with Borland C++
  69.  
  70.         sample programs
  71.         ---------------
  72.  
  73.     EXAMPLE1.C
  74.     EXAMPLE2.C
  75.     EXAMPLE3.C
  76.     EXAMPLE4.C
  77.     EXAMPLE5.C
  78.     SORTX.C         A working replacement for MS-DOS "Sort". Much faster,
  79.                     and it won't bomb on large input files.
  80.  
  81.            data files for the examples:
  82.  
  83.     WORDLIST    |   word list data file for example1, example2
  84.     SHORTLST    |   word list data file for example3
  85.     EMPLDATA    |   employee data file for example4, example5
  86.  
  87.  
  88.         TAVL library:  all library files are named TAVL*.C or TAVL*.H
  89.         -------------
  90.  
  91. public:
  92.  
  93.     TAVLTREE.H      Include this header file in all your applications;
  94.                     contains prototypes for all TAVL library functions.
  95.  
  96.     TAVLINIT.C      "tavl_init"
  97.     TAVL_INS.C      "tavl_insert"
  98.     TAVL_DEL.C      "tavl_delete"
  99.     TAVLFIND.C      "tavl_find"
  100.     TAVL_RST.C      "tavl_reset"
  101.     TAVLSUCC.C      "tavl_succ"
  102.     TAVLPRED.C      "tavl_pred"
  103.     TAVLFREE.C      "tavl_destroy"
  104.     TAVLDALL.C      "tavl_delete_all"
  105.     TAVL_SDT.C      "tavl_setdata"
  106.     TAVL_GDT.C      "tavl_getdata"
  107.  
  108. private:
  109.  
  110.     TAVLPRIV.H      Private header for compiling the library; do NOT
  111.                     include this in your application.
  112.  
  113.     TAVLREBL.C      "rebalance_tavl"  - private routine used by
  114.                                         "tavl_insert" and "tavl_delete"
  115.  
  116.  
  117. REGISTRATION:
  118. -------------
  119.  
  120. No registration is required for any use whatsoever of the
  121. TAVLTREE library.  I, Bert C. Hughes, have donated this
  122. package to the PUBLIC DOMAIN.
  123.  
  124. However, I invite and welcome comments and critisms. Send same to:
  125.  
  126.             Bert Hughes
  127.             J&B Consulting Services
  128.             200 N. Saratoga
  129.             St. Paul, MN 55104
  130.  
  131. I may also be contacted via Compuserve Mail.  My ID is 71211,577.
  132.  
  133.  
  134. References & Bibliography
  135. -------------------------
  136. Holub, Allen      "An AVL Tree Database Package",
  137.                         C Chest Column
  138.                         Aug. 86, Dr.Dobbs Journal
  139.  
  140. Horowitz & Sahni   Fundamentals of Data Structures,   see Chap. 5, Sec. 6:
  141.                         Computer Science Press          Threaded Binary Trees
  142.                                                       and Chap. 9, Sec. 2:
  143.                                                         Dynamic Tree Tables
  144. Jarvis, Bob        "Balanced Binary Trees in C++",
  145.                         Jan. 91, C User's Journal
  146.  
  147. Mathews, James     "Threaded Binary Trees"
  148.                         Mar. 88, Dr.Dobbs Journal
  149.