chiark - git - mdw - xyla/blob - avltest.in

   1 :;;;-------------------------------------------------------------------------
   2 :;;; Insertion.
   3
   4 :
   5 :;; Starting point for the following tests.
   6 =                                       ((((_ 110 _)
   7                                 120
   8                                         (_ 130 _))
   9                 140
  10                         (_ 150 _))
  11         200
  12                         ((_ 310 _)
  13                 320
  14                                         ((_ 330 _)
  15                                 340
  16                                         (_ 350 _))))
  17 D!
  18
  19 :
  20 :;; Counter-biased parent.
  21 ;;      p - or + -> =
  22 ;;           ( )
  23 ;;       n  /   \
  24 ;;      h + 1   h + 1
  25 " 305k+ D! )
  26 " 155k+ D! )
  27
  28 :
  29 :;; Cobiased parent, outer descendant.
  30 ;;               p                            n
  31 ;;                (- -)                        (=)
  32 ;;          n    /     \                     /    \    p
  33 ;;           (-)          n     --->    h + 1       (=)
  34 ;;          /   \                                  /   \
  35 ;;      h + 1     h                              h       h
  36 " 105k+ D! )
  37 " 355k+ D! )
  38
  39 :
  40 :;; Cobiased parent, inner descendant.
  41 ;;               p
  42 ;;                (- -)                        c
  43 ;;          n    /     \                        (=)
  44 ;;           (+)         h             n   ,---'   `---,   p
  45 ;;          /   \   c           --->    (*)             (*)
  46 ;;        h      (*)                   /   \           /   \
  47 ;;              /   \                h       h       h       h
  48 ;;            h       h                    h - 1   h - 1
  49 ;;          h - 1   h - 1
  50
  51 " 125k+ D! )
  52 " 135k+ D! )
  53 " 110k- 130k- 150k- D! 135k+ D! )
  54
  55 " 335k+ D! )
  56 " 325k+ D! )
  57 " 350k- 330k- 310k- D! 325k+ D! )
  58
  59 :
  60 :;; Ascend tree.
  61 ;;        p = -> -              p = -> +
  62 ;;           ( )        or         ( )
  63 ;;       n  /   \                 /   \  n
  64 ;;      h + 1     h             h     h + 1
  65
  66 " 125k+ 135k+ D! 105k+ D! )
  67 " 325k+ 335k+ D! 355k+ D! )
  68
  69 :
  70 :;;;-------------------------------------------------------------------------
  71 :;;; Removal.
  72
  73 :
  74 :;; Starting point for the following tests.
  75 =                       (((_ 110
  76                                 (_ 120 _))
  77                 130
  78                                 ((_ 140 _)
  79                         150 _))
  80         200
  81                         ((_ 310
  82                                 (_ 320 _))
  83                 330
  84                                 ((_ 340 _)
  85                         350 _)))
  86 D!
  87
  88 :
  89 :;; Cobiased parent.
  90 ;;         p                                p
  91 ;;          (-)                              (=)
  92 ;;      n  /   \                --->     n  /   \
  93 ;;       h     h - 1                    h - 1   h - 1
  94 " 120k- D! 140k- D! )
  95 " 340k- D! 320k- D! )
  96
  97 :
  98 :;; Balanced parent.
  99 ;;         p                                p
 100 ;;          (=)                              (+)
 101 ;;      n  /   \                --->     n  /   \
 102 ;;       h       h                      h - 1     h
 103 " 120k- 140k- D! 110k- D! )
 104 " 320k- 340k- D! 350k- D! )
 105
 106 :
 107 :;; Counter-biased parent, balanced or counter-biased sibling.
 108 ;;           p                                    s
 109 ;;            (+ +)                                (*)
 110 ;;           /     \    s                   p    /     \
 111 ;;      h - 1        (*)        --->         (*)          h
 112 ;;                  /   \                   /   \
 113 ;;                h       h             h - 1     h
 114 ;;              h - 1                           h - 1
 115 " 120k- 155k+ D! 110k- D! )
 116 " 120k- 140k- 155k+ D! 110k- D! )
 117 " 310k- 330k- 320k- D! 340k- D! )
 118
 119 :
 120 :;; Counter-biased parent, cobiased sibling.
 121
 122 ;;           p
 123 ;;            (+ +)                          t
 124 ;;           /     \    s                     (=)
 125 ;;      h - 1        (-)             p   ,---'   `---,   s
 126 ;;              t   /   \       --->  (*)             (*)
 127 ;;               (*)    h - 1        /   \           /   \
 128 ;;              /   \            h - 1   h - 1   h - 1   h - 1
 129 ;;          h - 1   h - 1                h - 2   h - 2
 130 ;;          h - 2   h - 2
 131 " 120k- D! 110k- D! )
 132 " 155k+ 145k+ D! 120k- D! )
 133 " 155k+ 135k+ D! 120k- D! )
 134 " 340k- D! 350k- D! )
 135 " D! 305k+ 325k+ D! 340k- D! )
 136 " D! 305k+ 315k+ D! 340k- D! )
 137
 138 :
 139 :;;;-------------------------------------------------------------------------
 140 :;;; Joining.
 141
 142 :
 143 :;; Splice, short counter-biased node.
 144 ;;                                          n
 145 ;;        n                                  (+)
 146 ;;         (-)                             /     \    m
 147 ;;        /   \                 --->    h          (+)
 148 ;;      h     h - 1                               /   \
 149 ;;                                            h - 1     h
 150 =_ #14 14- D! ( #15-17 D! 14k ~ D!
 151 =_ #1-3 D! ( #17-4 4- D! 4k ~ D!
 152
 153 :
 154 :;; Splice, standard balanced or counter-biased node.
 155 ;;                                            n
 156 ;;          n                                  (*)
 157 ;;           (*)                             /     \    m
 158 ;;          /   \               --->       h         (=)
 159 ;;        h       h                      h + 1      /   \
 160 ;;        h + 1                                   h       h
 161 =_ #15 D! ( #17-19 D! 16k ~ D!
 162 =_ #14 14- D! ( 15+ D! 14k ~ D!
 163 =_ #1-3 D! ( #19-5 D! 4k ~ D!
 164 =_ 1+ D! ( #15-2 2- D! 2k ~ D!
 165
 166 :
 167 :;; Splice, cobiased node, balanced or counter-biased parent.
 168 ;;                                           p
 169 ;;            p                               (*)
 170 ;;             (*)                          /     \    m
 171 ;;           /     \    n              h + 1        (-)
 172 ;;      h + 1        (+)        --->   h + 2   n   /   \
 173 ;;      h + 2       /   \                       (+)      h
 174 ;;              h - 1     h                    /   \
 175 ;;                                         h - 1     h
 176 =_ #12 #14-17 13+ D! ( 19+ D! 18k ~ D!
 177 =_ #8 #10-16 14- 9+ D! ( 18+ D! 17k ~ D!
 178 =_ 1+ D! ( #19-7 #5-3 6+ D! 2k ~ D!
 179 =_ 1+ D! ( #18-11 #9-3 5- 10+ D! 2k ~ D!
 180
 181 :
 182 :;; Splice, cobiased node, cobiased parent.
 183 ;;         p                                    n
 184 ;;          (+)                                  (=)
 185 ;;        /     \    n                   p     /     \     m
 186 ;;      h        (+)            --->      (-)           (=)
 187 ;;              /   \                    /   \         /   \
 188 ;;          h - 1     h                h     h - 1   h       h
 189 =_ #12 D! ( 14+ D! 13k ~ D!
 190 =_ 1+ D! ( #14-3 D! 2k ~ D!
 191
 192 :
 193 :;; Ascent, cobiased node.
 194 ;;                                                c
 195 ;;          n                                      (=)
 196 ;;           (+)                            n    /     \
 197 ;;          /   \  c            --->         (=)          h
 198 ;;      h - 1     h                         /   \
 199 ;;                                      h - 1   h - 1
 200 =_ #13 D! ( 15+ D! 14k ~ D!
 201 =_ 1+ D! ( #15-3 D! 2k ~ D!
 202
 203 :
 204 :;; Ascent, counter-biased node.
 205 ;;                                            n
 206 ;;          n                                  (=)
 207 ;;           (-)                             /     \    c
 208 ;;          /   \  c            --->    h + 1        (+)
 209 ;;      h + 1     h                                 /   \
 210 ;;                                              h - 1     h
 211 =_ #8 #10-16 9+ D! ( 18+ D! 17k ~ D!
 212 =_ 1+ D! ( #18-11 #9-3 10+ D! 2k ~ D!
 213
 214 :
 215 :;; Ascent, balanced node.
 216 ;;                                          n
 217 ;;        n                                  (+)
 218 ;;         (=)                             /     \    c
 219 ;;        /   \  c              --->    h          (+)
 220 ;;      h       h                                 /   \
 221 ;;                                            h - 1     h
 222 =_ #15 D! ( 17+ D! 16k ~ D!
 223 =_ 1+ D! ( #3-17 D! 2k ~ D!