home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / CONTRIB / MBASE / MBASE51.TAR / mbase51 / tech / chapter.2 < prev    next >
Encoding:
Text File  |  1993-09-04  |  5.4 KB  |  148 lines
  1. Tech Chapter 2 - Binary tree pseudocode                           MetalBase 5.1
  2. -------------------------------------------------------------------------------
  3.  
  4. MetalBase 3.2 used straight, unbalanced binary-trees to keep track of data.
  5.    4.0 to 5.0 migrated to weight-limited AVL-balancing; the routines for
  6.    keeping a tree in balance, and rebalancing it when needed, are below.  5.1
  7.    uses a less restrictive version of 5.0's algorithm; the compile-time
  8.    definition MAX_FRAG allows for a choice of a tradeoff between speed of
  9.    updates and queries.
  10.  
  11. I developed these algorithms by hand, just from common sense; if there's a
  12.    flaw (other than rebalancing speed), it hasn't shown up after hundreds of
  13.    thousands of uses, so I'm happy.  I am, however, interested in a faster
  14.    rebalancing algorithm (as long as it can be used with existing relations)...
  15.    please lemme know if something strikes you.
  16.  
  17. The balancing algorithm used for 5.0 (and for 5.1 if MAX_FRAG==1) requires
  18.    that, at any node in a tree, the number of records to the left of a node
  19.    is almost exactly equal to the number on the right; to make it work, they
  20.    can be off by 1 (MAX_FRAG).  So the following are balanced:
  21.  
  22.                      ___5___           ___4___
  23.                    _2_     _8_       _2_     _6_
  24.                   1   4   7         1   3   5   7
  25.  
  26. And the following aren't (the first is too heavy to the left at 5, the second
  27. is too heavy to the right at 4):
  28.  
  29.                      ___5___           ___4___
  30.                    _2_      8                 6_
  31.                   1   4                          7
  32.  
  33. This kind of balancing ensures, in effect, that only the last two levels of
  34.    the tree can ever have any empty nodes... so a tree will always stay as
  35.    shallow as possible, providing the following speeds for algorithms:
  36.  
  37.                           Worst-Case      Average-Case    Best-Case
  38.                           ------------    ------------    ---------
  39.          SEARCH...........O(ln(n))........O(ln (ln(n)))...O(1)
  40.          ADD..............O(n * ln (n))...O(n * ln (n))...O(ln (n))
  41.          UPDATE...........O(n * ln (n))...O(n * ln (n))...O(ln (n))
  42.          DELETE...........O(n * ln (n))...O(n * ln (n))...O(ln (n))
  43.  
  44. MetalBase 5.1 is shipped with MAX_FRAG set to five; this provides the following
  45.    timings:
  46.  
  47.                           Worst-Case      Average-Case    Best-Case
  48.                           ------------    ------------    ---------
  49.          SEARCH...........O(ln(n))........O(ln (n)).......O(1)
  50.          ADD..............O(n * ln (n))...O(n)............O(ln (n))
  51.          UPDATE...........O(n * ln (n))...O(n)............O(ln (n))
  52.          DELETE...........O(n * ln (n))...O(n)............O(ln (n))
  53.  
  54. I've never really liked O() notation; in the real world, the constants that
  55.    drop out can make a big difference.  In essence, searching is almost
  56.    instantaneous for thousands of records; with MAX_FRAG at one, adds and
  57.    updates are a painfully slow exponentially-increasing curve... with
  58.    MAX_FRAG at five, average-case adds and updates are a fast-constant
  59.    linear slope.
  60.  
  61.  
  62. PSEUDOCODE --------------------------------------------------------------------
  63.  
  64.           (*) indicates a procedure must be called once for each index
  65.  
  66. -------------------------------------------------------------------------------
  67.  
  68. mb_upd (rcd) :
  69. *  _delete (rcd, <index>)
  70.    change records instance on disk
  71. *  _link (rcd, <index>)
  72.  
  73. mb_del (rcd) :
  74. *  _delete (rcd, <index>)
  75.    _remove (rcd)
  76.  
  77. mb_add (data) :
  78.    rcd = _append (data)
  79. *  _link (rcd, <index>)
  80.  
  81. _link (rcd) :
  82. *| _drop (rcd, <index>)            (these are called, one after the other,
  83. *| _check (rcd, top, <index>)       for each index in the relation)
  84.  
  85. _drop (pos, index) :
  86.    for (loc = top; ; )
  87.     { dir = _compare (rec (loc), rec(pos), index)  -- (-1,0,1)
  88.       loc->balance += dir;
  89.       if ( loc->child[dir] == 0 )
  90.        { loc->child[dir] = rec
  91.          rec->parent = loc
  92.          break
  93.        }
  94.     }
  95.  
  96. _check (st, ed, index) :
  97.    for (loc = st; ; loc=loc->parent)
  98.     { if ( rec (loc) ->unbalanced(index) )
  99.          _balance (loc, index)
  100.       if (loc == ed)  break;
  101.     };
  102.  
  103. _dislink (loc, index) :
  104.    ch=loc->left || loc->right
  105.    if (loc->pardir)  loc->parent->right = ch;
  106.    else              loc->parent->left  = ch;
  107.    if (ch)  ch->parent = loc->parent, ch->pardir = loc->pardir;
  108.                      /* DO NOT re-read loc */
  109.    for (dir=loc->pardir,tmp=loc->parent;tmp!=0;dir=tmp->pardir,tmp=tmp->parent)
  110.       tmp->balance -= (dir == 1) ? 1 : -1;
  111.  
  112. _balance (loc, index) :
  113.    if (! rep = find_seq (loc, rec(loc)->balance) )->ERROR!!! -- bal>0?Next:Prev
  114.    rp=rep->parent
  115.    _dislink (rep, index)
  116.    _replace (loc, rep, index) -- Replace LOC with REP
  117.    _drop (loc, index)
  118.    if (rp != loc)  _check (rp, rep)
  119.                     /* re-read loc */
  120.    _check (loc->parent, rep)
  121.  
  122. _delete (bad) :
  123.    bp = bad->parent
  124.    if (bad->balance != 0)
  125.       rep = find_seq (bad, bad->balance)  --bal>0?Next:Prev
  126.    else
  127.       if (! rep = find_seq (bad, toggle (lastmove)))
  128.          rep = find_seq (bad, toggle (lastmove))
  129.    if (! rep)
  130.       _dislink (bad)
  131.    else
  132.     { rp= rep->parent;
  133.       _dislink (rep)
  134.       _replace (bad, rep)
  135.       if (rp != bad)  _check (rp, bp)
  136.     }
  137.    _check (bp, top)
  138.  
  139. _replace (old, new) :
  140.    new->left_c = old->left_c;
  141.    new->right_ = old->right_;
  142.    new->parent = old->parent;  par=new->parent;
  143.    new->pardir = old->pardir;
  144.    par->[pardir]_c = new;
  145.    new->left_c->parent = new;
  146.    new->right_c->parent = new;
  147.  
  148.