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

   1 ;;; Manually constructed tests for red-black trees.
   2
   3 :;;;-------------------------------------------------------------------------
   4 :;;; Insertion.
   5
   6 :
   7 :;; Starting point for the following tests.
   8 =                               ((((_ 10 _)
   9                         *20
  10                                 (_ 30 _))
  11                 40
  12                                 ((_ 50 _)
  13                         *60 _))
  14         *70
  15                         (_ *80
  16                                 (_ 90 _)))
  17 D
  18
  19 :
  20 :;; Children of a black node.
  21 " V+ 65k+ D V )
  22 " V+ 75k+ D V )
  23
  24 :
  25 :;; Ascend tree.
  26 ;;                p                               p
  27 ;;                 (*)                             ( )
  28 ;;          n    /     \    s               n    /     \    s
  29 ;;           ( )         ( )    --->         (*)         (*)
  30 ;;      c   /   \       /   \           c   /   \       /   \
  31 ;;       ( )                             ( )
  32 ;;      /   \                           /   \
  33 " 5k+ 15k+ V+ 0k+
  34         V:XYLA-RB INSERT red sibling: ascend
  35         V:XYLA-RB INSERT red sibling: extend tree
  36   D V )
  37
  38 :
  39 :;; Zig-zig.
  40 ;;                p
  41 ;;                 (*)                        n
  42 ;;          n    /     \                       (*)
  43 ;;           ( )                --->    c    /     \    p
  44 ;;      c   /   \                        ( )         ( )
  45 ;;       ( )                            /   \       /   \
  46 ;;      /   \
  47 " V+ 45k+
  48         V:XYLA-RB INSERT zig-zig (left child)
  49   D V )
  50 " V+ 95k+
  51         V:XYLA-RB INSERT zig-zig (right child)
  52   D V )
  53
  54 :
  55 :;; Zig-zag.
  56 ;;                p
  57 ;;                 (*)                        c
  58 ;;          n    /     \                       (*)
  59 ;;           ( )                --->    n    /     \    p
  60 ;;          /   \   c                    ( )         ( )
  61 ;;               ( )                    /   \       /   \
  62 ;;              /   \
  63 " V+ 55k+
  64         V:XYLA-RB INSERT zig-zag (left child)
  65   D V )
  66 " V+ 85k+
  67         V:XYLA-RB INSERT zig-zag (right child)
  68   D V )
  69
  70 :
  71 :;;;-------------------------------------------------------------------------
  72 :;;; Removal.
  73
  74 ;; There are too many cases here.
  75
  76 :
  77 :;; Initial state.
  78 =                                       ((((_ *0 _)
  79                                 2
  80                                                 ((_ 4 _)
  81                                         *6
  82                                                 (_ 8 _)))
  83                         *10
  84                                         (_ *12 _))
  85         *14
  86                                         ((_ *16 _)
  87                         *18
  88                                                 (((_ 20 _)
  89                                         *22
  90                                                 (_ 24 _))
  91                                 26
  92                                         (_ *28 _))))
  93 D
  94
  95 :
  96 :;; Red node.
  97 " V- 2k- D V )
  98 " V- 4k- D V )
  99 " V- 8k- D V )
 100 " V- 18k- D V )
 101
 102 :
 103 :;; Red sibling, outer red great-nibling.
 104 ;;            p                                       s
 105 ;;             (*)                                     (*)
 106 ;;     n     /     \    s                       t    /     \
 107 ;;      (* *)        ( )        --->             ( )
 108 ;;      /   \   t   /   \                   p   /   \   r
 109 ;;               (*)                         (*)     (*)
 110 ;;              /   \   r               n   /   \   /   \
 111 ;;                   ( )                 (*)
 112 ;;                  /   \               /   \
 113 " 8k- D V- 12k-
 114         V:XYLA-RB REMOVE red sibling, outer red great-nibling (right child)
 115   D V )
 116 " 20k- D V- 16k-
 117         V:XYLA-RB REMOVE red sibling, outer red great-nibling (left child)
 118   D V )
 119
 120 :
 121 :;; Red sibling, inner red great-nibling.
 122 ;;            p                                       s
 123 ;;             (*)                                     (*)
 124 ;;     n     /     \    s                       l    /     \
 125 ;;      (* *)        ( )        --->             ( )
 126 ;;      /   \   t   /   \                   p   /   \   t
 127 ;;               (*)                         (*)     (*)
 128 ;;          l   /   \                   n   /   \   /   \
 129 ;;           ( )                         (*)
 130 ;;          /   \                       /   \
 131 " 4k- D V- 12k-
 132         V:XYLA-RB REMOVE red sibling, inner red great-nibling (right child)
 133   D V )
 134 " 24k- D V- 16k-
 135         V:XYLA-RB REMOVE red sibling, inner red great-nibling (left child)
 136   D V )
 137
 138 :
 139 :;; Red sibling, no red great-nibling.
 140 ;;            p                                   s
 141 ;;             (*)                                 (*)
 142 ;;     n     /     \    s                   p    /     \
 143 ;;      (* *)        ( )        --->         (*)
 144 ;;      /   \   t   /   \               n   /   \   t
 145 ;;               (*)                     (*)     ( )
 146 ;;              /   \                   /   \   /   \
 147 " 4k- 8k- D V- 12k-
 148         V:XYLA-RB REMOVE red sibling, no red great-nibling (right child)
 149   D V )
 150 " 20k- 24k- D V- 16k-
 151         V:XYLA-RB REMOVE red sibling, no red great-nibling (left child)
 152   D V )
 153
 154 :
 155 :;; Black sibling, outer red nibling.
 156 ;;            p                                    s
 157 ;;             (?)                                  (?)
 158 ;;     n     /     \   s                     p    /     \   r
 159 ;;      (* *)       (*)         --->          (*)        (*)
 160 ;;      /   \      /   \   r            n    /   \      /   \
 161 ;;                      ( )              (*)
 162 ;;                     /   \            /   \
 163 " 4k- D V- 0k-
 164         V:XYLA-RB REMOVE black sibling, outer red nibling (left child)
 165   D V )
 166 " 24k- D V- 28k-
 167         V:XYLA-RB REMOVE black sibling, outer red nibling (right child)
 168   D V )
 169
 170 :
 171 :;; Black sibling, inner red nibling.
 172 ;;            p                                    l
 173 ;;             (?)                                  (?)
 174 ;;     n     /     \   s                     p    /     \   s
 175 ;;      (* *)       (*)         --->          (*)        (*)
 176 ;;      /   \  l   /   \                n    /   \      /   \
 177 ;;              ( )                      (*)
 178 ;;             /   \                    /   \
 179 " 8k- D V- 0k-
 180         V:XYLA-RB REMOVE black sibling, inner red nibling (left child)
 181   D V )
 182 " 20k- D V- 28k-
 183         V:XYLA-RB REMOVE black sibling, inner red nibling (right child)
 184   D V )
 185
 186 :
 187 :;; Black sibling, red parent, no red nibling.
 188 ;;            p                                    p
 189 ;;             ( )                                  (*)
 190 ;;     n     /     \   s                     n    /     \   s
 191 ;;      (* *)       (*)         --->          (*)        ( )
 192 ;;      /   \      /   \                     /   \      /   \
 193 " 4k- 8k- D V- 0k-
 194         V:XYLA-RB REMOVE black sibling, red parent, no red nibling (left child)
 195   D V )
 196 " 20k- 24k- D V- 28k-
 197         V:XYLA-RB REMOVE black sibling, red parent, no red nibling (right child)
 198   D V )
 199
 200 :
 201 :;; Black sibling, black parent, no red nibling.
 202 ;;            p                                    p
 203 ;;             (*)                                 (* *)
 204 ;;     n     /     \   s                     n    /     \   s
 205 ;;      (* *)       (*)         --->          (*)        ( )
 206 ;;      /   \      /   \                     /   \      /   \
 207 " 4k- 8k- 0k- 6k- 20k- 24k- 16k- 28k- D
 208 " V- 12k-
 209         V:XYLA-RB REMOVE black sibling, black parent, no red nibling (right child)
 210         V:XYLA-RB REMOVE black sibling, black parent, no red nibling (left child)
 211         V:XYLA-RB REMOVE shorten tree
 212   D V )
 213 " V- 18k-
 214         V:XYLA-RB REMOVE black sibling, black parent, no red nibling (left child)
 215         V:XYLA-RB REMOVE black sibling, black parent, no red nibling (right child)
 216         V:XYLA-RB REMOVE shorten tree
 217   D V )
 218 )
 219
 220 :;;;-------------------------------------------------------------------------
 221 :;;; Joining.
 222
 223 :
 224 :;; Equal heights.
 225 =_ #6 D ( #13-8 D V~ 7k~
 226         V:XYLA-RB JOIN equal heights
 227    D V
 228
 229 :
 230 :;; Red sibling.
 231 =_ #8 D ( 10+ D V~ 9k~
 232         V:XYLA-RB JOIN red sibling (right child): extend tree
 233    D V
 234 =_ 1+ D ( #10-3 D V~ 2k~
 235         V:XYLA-RB JOIN red sibling (left child): extend tree
 236    D V
 237
 238 =_ #12 D ( 14+ D V~ 13k~
 239         V:XYLA-RB JOIN red sibling (right child): ascend
 240    D V
 241 =_ 1+ D ( #12-3 D V~ 2k~
 242         V:XYLA-RB JOIN no red sibling (left child)
 243    D V
 244
 245 :
 246 :;; No red sibling.
 247 =_ # 7 D ( 9+ D V~ 8k~
 248         V:XYLA-RB JOIN no red sibling (right child)
 249    D V
 250 =_ 1+ D ( #9-3 D V~ 2k~
 251         V:XYLA-RB JOIN no red sibling (left child)
 252    D V
 253
 254 :
 255 :;;;----- That's all, folks -------------------------------------------------