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

   1 ;;; Manually constructed tests for AVL trees.
   2
   3 :;;;-------------------------------------------------------------------------
   4 :;;; Insertion.
   5
   6 :
   7 :;; Starting point for the following tests.
   8 =                                       ((((_ 110 _)
   9                                 120
  10                                         (_ 130 _))
  11                 140
  12                         (_ 150 _))
  13         200
  14                         ((_ 310 _)
  15                 320
  16                                         ((_ 330 _)
  17                                 340
  18                                         (_ 350 _))))
  19 D
  20
  21 :
  22 :;; Counter-biased parent.
  23 ;;      p - or + -> =
  24 ;;           ( )
  25 ;;       n  /   \
  26 ;;      h + 1   h + 1
  27 " V+ 305k+
  28         V:XYLA-AVL INSERT parent = (left child): ascend tree
  29         V:XYLA-AVL INSERT parent + (left child)
  30   D V )
  31 " V+ 155k+
  32         V:XYLA-AVL INSERT parent = (right child): ascend tree
  33         V:XYLA-AVL INSERT parent - (right child)
  34   D V )
  35
  36 :
  37 :;; Cobiased parent, outer descendant.
  38 ;;               p                            n
  39 ;;                (- -)                        (=)
  40 ;;          n    /     \                     /    \    p
  41 ;;           (-)          n     --->    h + 1       (=)
  42 ;;          /   \                                  /   \
  43 ;;      h + 1     h                              h       h
  44 " V+ 105k+
  45         V:XYLA-AVL INSERT parent = (left child): ascend tree
  46         V:XYLA-AVL INSERT parent = (left child): ascend tree
  47         V:XYLA-AVL INSERT parent -, node - (left child)
  48   D V )
  49 " V+ 355k+
  50         V:XYLA-AVL INSERT parent = (right child): ascend tree
  51         V:XYLA-AVL INSERT parent = (right child): ascend tree
  52         V:XYLA-AVL INSERT parent +, node + (right child)
  53   D V )
  54
  55 :
  56 :;; Cobiased parent, inner descendant.
  57 ;;               p
  58 ;;                (- -)                        c
  59 ;;          n    /     \                        (=)
  60 ;;           (+)         h             n   ,---'   `---,   p
  61 ;;          /   \   c           --->    (*)             (*)
  62 ;;        h      (*)                   /   \           /   \
  63 ;;              /   \                h       h       h       h
  64 ;;            h       h                    h - 1   h - 1
  65 ;;          h - 1   h - 1
  66
  67 " V+ 125k+
  68         V:XYLA-AVL INSERT parent = (left child): ascend tree
  69         V:XYLA-AVL INSERT parent = (right child): ascend tree
  70         V:XYLA-AVL INSERT parent -, node +, child - (left child)
  71   D V )
  72 " V+ 135k+
  73         V:XYLA-AVL INSERT parent = (right child): ascend tree
  74         V:XYLA-AVL INSERT parent = (right child): ascend tree
  75         V:XYLA-AVL INSERT parent -, node +, child + (left child)
  76   D V )
  77 " 110k- 130k- 150k- D V+ 135k+
  78         V:XYLA-AVL INSERT parent = (right child): ascend tree
  79         V:XYLA-AVL INSERT parent -, node +, child = (left child)
  80   D V )
  81
  82 " V+ 335k+
  83         V:XYLA-AVL INSERT parent = (right child): ascend tree
  84         V:XYLA-AVL INSERT parent = (left child): ascend tree
  85         V:XYLA-AVL INSERT parent +, node -, child + (right child)
  86   D V )
  87 " V+ 325k+
  88         V:XYLA-AVL INSERT parent = (left child): ascend tree
  89         V:XYLA-AVL INSERT parent = (left child): ascend tree
  90         V:XYLA-AVL INSERT parent +, node -, child - (right child)
  91   D V )
  92 " 350k- 330k- 310k- D V+ 325k+
  93         V:XYLA-AVL INSERT parent = (left child): ascend tree
  94         V:XYLA-AVL INSERT parent +, node -, child = (right child)
  95   D V )
  96
  97 :
  98 :;; Ascend tree.
  99 ;;        p = -> -              p = -> +
 100 ;;           ( )        or         ( )
 101 ;;       n  /   \                 /   \  n
 102 ;;      h + 1     h             h     h + 1
 103
 104 " 125k+ 135k+ D V+ 105k+
 105         V:XYLA-AVL INSERT parent = (left child): ascend tree
 106         V:XYLA-AVL INSERT parent = (left child): ascend tree
 107         V:XYLA-AVL INSERT parent = (left child): ascend tree
 108         V:XYLA-AVL INSERT parent = (left child): extend tree
 109   D V )
 110 " 325k+ 335k+ D V+ 355k+
 111         V:XYLA-AVL INSERT parent = (right child): ascend tree
 112         V:XYLA-AVL INSERT parent = (right child): ascend tree
 113         V:XYLA-AVL INSERT parent = (right child): ascend tree
 114         V:XYLA-AVL INSERT parent = (right child): extend tree
 115   D V )
 116
 117 :
 118 :;;;-------------------------------------------------------------------------
 119 :;;; Removal.
 120
 121 :
 122 :;; Starting point for the following tests.
 123 =                       (((_ 110
 124                                 (_ 120 _))
 125                 130
 126                                 ((_ 140 _)
 127                         150 _))
 128         200
 129                         ((_ 310
 130                                 (_ 320 _))
 131                 330
 132                                 ((_ 340 _)
 133                         350 _)))
 134 D
 135
 136 :
 137 :;; Cobiased parent.
 138 ;;         p                                p
 139 ;;          (-)                              (=)
 140 ;;      n  /   \                --->     n  /   \
 141 ;;       h     h - 1                    h - 1   h - 1
 142 " 120k- D V- 140k-
 143         V:XYLA-AVL REMOVE parent - (left child)
 144         V:XYLA-AVL REMOVE parent + (right child)
 145         V:XYLA-AVL REMOVE parent = (left child)
 146   D V )
 147 " 340k- D V- 320k-
 148         V:XYLA-AVL REMOVE parent + (right child)
 149         V:XYLA-AVL REMOVE parent - (left child)
 150         V:XYLA-AVL REMOVE parent = (right child)
 151   D V )
 152
 153 :
 154 :;; Balanced parent.
 155 ;;         p                                p
 156 ;;          (=)                              (+)
 157 ;;      n  /   \                --->     n  /   \
 158 ;;       h       h                      h - 1     h
 159 " 120k- 140k- D V- 110k-
 160         V:XYLA-AVL REMOVE parent = (left child)
 161   D V )
 162 " 320k- 340k- D V- 350k-
 163         V:XYLA-AVL REMOVE parent = (right child)
 164   D V )
 165
 166 :
 167 :;; Counter-biased parent, balanced or counter-biased sibling.
 168 ;;           p                                    s
 169 ;;            (+ +)                                (*)
 170 ;;           /     \    s                   p    /     \
 171 ;;      h - 1        (*)        --->         (*)          h
 172 ;;                  /   \                   /   \
 173 ;;                h       h             h - 1     h
 174 ;;              h - 1                           h - 1
 175 " 120k- 155k+ D V- 110k-
 176         V:XYLA-AVL REMOVE parent +, sibling = (left child)
 177   D V )
 178 " 120k- 140k- 155k+ D V- 110k-
 179         V:XYLA-AVL REMOVE parent +, sibling + (left child)
 180         V:XYLA-AVL REMOVE parent = (left child)
 181   D V )
 182 " 310k- 330k- 320k- D V- 340k-
 183         V:XYLA-AVL REMOVE parent -, sibling = (right child)
 184   D V )
 185
 186 :
 187 :;; Counter-biased parent, cobiased sibling.
 188
 189 ;;           p
 190 ;;            (+ +)                          t
 191 ;;           /     \    s                     (=)
 192 ;;      h - 1        (-)             p   ,---'   `---,   s
 193 ;;              t   /   \       --->  (*)             (*)
 194 ;;               (*)    h - 1        /   \           /   \
 195 ;;              /   \            h - 1   h - 1   h - 1   h - 1
 196 ;;          h - 1   h - 1                h - 2   h - 2
 197 ;;          h - 2   h - 2
 198 " 120k- D V- 110k-
 199         V:XYLA-AVL REMOVE parent +, sibling -, nibling = (left child)
 200         V:XYLA-AVL REMOVE parent = (left child)
 201   D V )
 202 " 155k+ 145k+ D V- 120k-
 203         V:XYLA-AVL REMOVE parent + (right child)
 204         V:XYLA-AVL REMOVE parent +, sibling -, nibling + (left child)
 205         V:XYLA-AVL REMOVE parent - (left child)
 206         V:XYLA-AVL REMOVE shorten tree
 207   D V )
 208 " 155k+ 135k+ D V- 120k-
 209         V:XYLA-AVL REMOVE parent + (right child)
 210         V:XYLA-AVL REMOVE parent +, sibling -, nibling - (left child)
 211         V:XYLA-AVL REMOVE parent - (left child)
 212         V:XYLA-AVL REMOVE shorten tree
 213   D V )
 214 " 340k- D V- 350k-
 215         V:XYLA-AVL REMOVE parent -, sibling +, nibling = (right child)
 216         V:XYLA-AVL REMOVE parent = (right child)
 217   D V )
 218 " D 305k+ 325k+ D V- 340k-
 219         V:XYLA-AVL REMOVE parent - (left child)
 220         V:XYLA-AVL REMOVE parent -, sibling +, nibling + (right child)
 221         V:XYLA-AVL REMOVE parent + (right child)
 222         V:XYLA-AVL REMOVE shorten tree
 223   D V )
 224 " D 305k+ 315k+ D V- 340k-
 225         V:XYLA-AVL REMOVE parent - (left child)
 226         V:XYLA-AVL REMOVE parent -, sibling +, nibling - (right child)
 227         V:XYLA-AVL REMOVE parent + (right child)
 228         V:XYLA-AVL REMOVE shorten tree
 229   D V )
 230
 231 :
 232 :;;;-------------------------------------------------------------------------
 233 :;;; Joining.
 234
 235 :
 236 :;; Splice, short counter-biased node.
 237 ;;                                          n
 238 ;;        n                                  (+)
 239 ;;         (-)                             /     \    m
 240 ;;        /   \                 --->    h          (+)
 241 ;;      h     h - 1                               /   \
 242 ;;                                            h - 1     h
 243 =_ #14 14- D ( #15-17 D V~ 14k~
 244         V:XYLA-AVL JOIN short subtree (right child)
 245         V:XYLA-AVL JOIN ascent, node = (right child)
 246         V:XYLA-AVL JOIN extend tree (right child)
 247    D V
 248 =_ #1-3 D ( #17-4 4- D V~ 4k~
 249         V:XYLA-AVL JOIN short subtree (left child)
 250         V:XYLA-AVL JOIN ascent, node = (left child)
 251         V:XYLA-AVL JOIN extend tree (left child)
 252    D V
 253
 254 :
 255 :;; Splice, standard balanced or counter-biased node.
 256 ;;                                            n
 257 ;;          n                                  (*)
 258 ;;           (*)                             /     \    m
 259 ;;          /   \               --->       h         (=)
 260 ;;        h       h                      h + 1      /   \
 261 ;;        h + 1                                   h       h
 262 =_ #15 D ( #17-19 D V~ 16k~
 263         V:XYLA-AVL JOIN splice, node = (right child)
 264         V:XYLA-AVL JOIN ascent, node = (right child)
 265         V:XYLA-AVL JOIN extend tree (right child)
 266    D V
 267 =_ #14 14- D ( 15+ D V~ 14k~
 268         V:XYLA-AVL JOIN splice, node - (right child)
 269    D V
 270 =_ #1-3 D ( #19-5 D V~ 4k~
 271         V:XYLA-AVL JOIN splice, node = (left child)
 272         V:XYLA-AVL JOIN ascent, node = (left child)
 273         V:XYLA-AVL JOIN extend tree (left child)
 274    D V
 275 =_ 1+ D ( #15-2 2- D V~ 2k~
 276         V:XYLA-AVL JOIN splice, node + (left child)
 277    D V
 278
 279 :
 280 :;; Splice, cobiased node, balanced or counter-biased parent.
 281 ;;                                           p
 282 ;;            p                               (*)
 283 ;;             (*)                          /     \    m
 284 ;;           /     \    n              h + 1        (-)
 285 ;;      h + 1        (+)        --->   h + 2   n   /   \
 286 ;;      h + 2       /   \                       (+)      h
 287 ;;              h - 1     h                    /   \
 288 ;;                                         h - 1     h
 289 =_ #12 #14-17 13+ D ( 19+ D V~ 18k~
 290         V:XYLA-AVL JOIN splice, node +, parent = (right child)
 291         V:XYLA-AVL JOIN ascent, node + (right child)
 292    D V
 293 =_ #8 #10-16 14- 9+ D ( 18+ D V~ 17k~
 294         V:XYLA-AVL JOIN splice, node +, parent - (right child)
 295    D V
 296 =_ 1+ D ( #19-7 #5-3 6+ D V~ 2k~
 297         V:XYLA-AVL JOIN splice, node -, parent = (left child)
 298         V:XYLA-AVL JOIN ascent, node - (left child)
 299    D V
 300 =_ 1+ D ( #18-11 #9-3 5- 10+ D V~ 2k~
 301         V:XYLA-AVL JOIN splice, node -, parent + (left child)
 302    D V
 303
 304 :
 305 :;; Splice, cobiased node, cobiased parent.
 306 ;;         p                                    n
 307 ;;          (+)                                  (=)
 308 ;;        /     \    n                   p     /     \     m
 309 ;;      h        (+)            --->      (-)           (=)
 310 ;;              /   \                    /   \         /   \
 311 ;;          h - 1     h                h     h - 1   h       h
 312 =_ #12 D ( 14+ D V~ 13k~
 313         V:XYLA-AVL JOIN splice, node +, parent + (right child)
 314    D V
 315 =_ 1+ D ( #14-3 D V~ 2k~
 316         V:XYLA-AVL JOIN splice, node -, parent - (left child)
 317    D V
 318
 319 :
 320 :;; Ascent, cobiased node.
 321 ;;                                                c
 322 ;;          n                                      (=)
 323 ;;           (+)                            n    /     \
 324 ;;          /   \  c            --->         (=)          h
 325 ;;      h - 1     h                         /   \
 326 ;;                                      h - 1   h - 1
 327 =_ #13 D ( 15+ D V~ 14k~
 328         V:XYLA-AVL JOIN splice, node = (right child)
 329         V:XYLA-AVL JOIN ascent, node + (right child)
 330    D V
 331 =_ 1+ D ( #15-3 D V~ 2k~
 332         V:XYLA-AVL JOIN splice, node = (left child)
 333         V:XYLA-AVL JOIN ascent, node - (left child)
 334    D V
 335
 336 :
 337 :;; Ascent, counter-biased node.
 338 ;;                                            n
 339 ;;          n                                  (=)
 340 ;;           (-)                             /     \    c
 341 ;;          /   \  c            --->    h + 1        (+)
 342 ;;      h + 1     h                                 /   \
 343 ;;                                              h - 1     h
 344 =_ #8 #10-16 9+ D ( 18+ D V~ 17k~
 345         V:XYLA-AVL JOIN splice, node = (right child)
 346         V:XYLA-AVL JOIN ascent, node - (right child)
 347    D V
 348 =_ 1+ D ( #18-11 #9-3 10+ D V~ 2k~
 349         V:XYLA-AVL JOIN splice, node = (left child)
 350         V:XYLA-AVL JOIN ascent, node + (left child)
 351    D V
 352
 353 :
 354 :;; Ascent, balanced node.
 355 ;;                                          n
 356 ;;        n                                  (+)
 357 ;;         (=)                             /     \    c
 358 ;;        /   \  c              --->    h          (+)
 359 ;;      h       h                                 /   \
 360 ;;                                            h - 1     h
 361 =_ #15 D ( 17+ D V~ 16k~
 362         V:XYLA-AVL JOIN splice, node = (right child)
 363         V:XYLA-AVL JOIN ascent, node = (right child)
 364         V:XYLA-AVL JOIN ascent, node = (right child)
 365         V:XYLA-AVL JOIN extend tree (right child)
 366    D V
 367 =_ 1+ D ( #3-17 D V~ 2k~
 368         V:XYLA-AVL JOIN splice, node = (left child)
 369         V:XYLA-AVL JOIN ascent, node = (left child)
 370         V:XYLA-AVL JOIN ascent, node = (left child)
 371         V:XYLA-AVL JOIN extend tree (left child)
 372    D V
 373
 374 :
 375 :;;;----- That's all, folks -------------------------------------------------