home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / lisp / mcl / 1066 / btree-decl.lisp
Encoding:
Text File  |  1992-07-23  |  1.9 KB  |  64 lines
  1. ;; declarations for btrees
  2. (in-package avl-tree)
  3. (provide 'btree-decl)
  4. (export '(*before* *after* *equal*
  5.           *left* *right* *done*
  6.           *left-taller* *right-taller* *balanced*
  7.           make-btree
  8.           btree-left
  9.           btree-right
  10.           btree-min
  11.           btree-max
  12.           btree-key
  13.           btree-val
  14.           btree-balance
  15.           make-btrail
  16.           btrail-dir
  17.           btrail-node
  18.           btrail-prev))
  19.  
  20. (defconstant *before* -1 "first key is before second")
  21. (defconstant *after* 1 "first key is after second")
  22. (defconstant *equal* 0 "first key equals second")
  23.  
  24. (defconstant *left* *before* "turn left")
  25. (defconstant *right* *after* "turn right")
  26. (defconstant *done* -2 "node already visited")
  27.  
  28.  
  29. (defconstant *balanced* 0 "tree is balanced")
  30. (defconstant *left-taller* -1 "left branches are taller")
  31. (defconstant *right-taller* +1 "right branches are taller")
  32.  
  33. ;; standard btree structure
  34. ;;   left       pointer to the left branch of the rooted subtree
  35. ;;   right      pointer to the right branch of the rooted subtree
  36. ;;   key        a pointer to the key of the rooted subtree
  37. ;;   val        value associated with the key
  38. ;;   min        if left then pointer to the leftmost node
  39. ;;              else nil
  40. ;;   min        if right then pointer to the right-most node
  41. ;;              else nil
  42. ;;   balance    one of *left-taller* *right-taller* *balanced*
  43. ;;              which satistfy *left-taller* + *right-taller* = *balanced* = 0
  44.  
  45. (defstruct (btree (:type list))
  46.   min left key val right max (balance *balanced*))
  47.  
  48. ;; a path is a list of any number of btrail structures
  49. ;;  ((dir-1 node-1) ... (dir-n node-n))
  50. ;;  if node with key is not found
  51. ;;        dir  = nil 
  52. ;;        node = key
  53. ;;  otherwise 
  54. ;;        dir = one of *equal* *right* *left*
  55. ;;              indicating no turn, or a right or left turn to the previous node
  56. ;;        node = a btree structure
  57.  
  58. (defstruct (btrail (:type list)) dir node prev)
  59.  
  60.  
  61.  
  62.  
  63.  
  64.