home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / btree / binhelp / binary.doc next >
Encoding:
Text File  |  1992-02-13  |  3.9 KB  |  94 lines
  1.  -------------------------------------------------------------------------
  2.   This code is released as public domain to anyone who wishes to use it
  3.  for learning purposes.  This was a building block in a project that is
  4.  under construction, and may be able to help your understanding of Binary
  5.  Trees.  I hope this program can help you out.
  6.  
  7.                                       Sinerely in Jesus Christ!
  8.  
  9.                                       Romans 10:9-17
  10.  
  11.  
  12.  -------------------------------------------------------------------------
  13.  
  14.  The object of binary trees is to lesson search time for a load of records.
  15.  If you have 3000 records of information for sorting, you know that it
  16.  can take a long time to search through all of these records.  If you
  17.  can sort by position (i.e. This is less, or greater then another element)
  18.  then you probably can find a better way of storing the information.
  19.  
  20.  For example: If you wanted to search for phone numbers then you could use
  21.              a binary tree, because the computer can interpret 555-5555 as
  22.              being greater then 000-0000.
  23.  
  24.               If you have a list of states, the computer can interpret
  25.              Arkansas as being before Hawaii.
  26.  
  27.               Trying to get the computer to sort for parts of words, or
  28.              other things, will take some more thinking out.  And you may
  29.              find that sorting through that information takes a much more
  30.              time consuming process.  There are some possible routes to
  31.              follow, but this program does not deal with those.
  32.  
  33.  
  34.  Say you needed to sort these fruits as they came in:
  35.  
  36.   Apple
  37.   Orange
  38.   Banana
  39.   Kiwi
  40.   Pear
  41.   Grapes
  42.  
  43.   In a binary tree it would look like this:
  44.  
  45.                             Apple(1)
  46.       (No left node) ─────────┴─────────┐
  47.                                       Orange(2)
  48.                               ┌─────────┴─────────┐
  49.                            Banana(3)             Pear(5)
  50.       (No left node) ─────────┴─────────┐
  51.                                        Kiwi(4)
  52.                               ┌─────────┴───────── ( No right node )
  53.                             Grapes(6)
  54.  
  55.   Since orange is higher alphabetically in order, it goes to the right
  56.  of apple which is placed first.  Then Banana, it is greater then Apple,
  57.  but less then orange so it goes to the left of orange. Kiwi is greater then
  58.  apple, less then orange, and greater then banana; hence, it goes to the
  59.  right of banana.  Pear is greater then apple, and orange it moves to the
  60.  next slot (right node).  Grapes is greater then apple, less then orange,
  61.  greater then banana, and less then Kiwi; hence, it goes to the left of
  62.  Kiwi.
  63.  
  64.  Confusing?  Try figuring out how you would place a few more names on the
  65.  table and where they would go.  When the tree is looked at in a number
  66.  sense you end up like this:
  67.  
  68.  Node  Left   Parent   Right    Word
  69.  -------------------------------------
  70.   1     0       0        2      Apple
  71.   2     3       1        5      Orange
  72.   3     0       2        4      Banana
  73.   4     6       3        0      Kiwi
  74.   5     0       2        0      Pear
  75.   6     0       4        0      Grapes
  76.  
  77.  
  78.   A parent node is the node that the word branches from.  0's mark empty
  79.   paths.  Try running the program a few times, and diagram the nodes, and
  80.   see what you come up with.
  81.  
  82.  -------------------------------------------------------------------------
  83.   This code is released as public domain to anyone who wishes to use it
  84.  for learning purposes.  This was a building block in a project that is
  85.  under construction, and may be able to help your understanding of Binary
  86.  Trees.  I hope this program can help you out.
  87.  
  88.                                       Sinerely in Jesus Christ!
  89.  
  90.                                       Romans 10:9-17
  91.  
  92.  
  93.  -------------------------------------------------------------------------
  94.