chiark - git - mdw - xyla/blob - t/rb-rbtest.ref

   1 ;;;-------------------------------------------------------------------------
   2 ;;; Insertion.
   3
   4 ;; Starting point for the following tests.
   5 tree dump, ht = 2
   6         #0x00000000 (n =   1)               ( ) 10
   7         #0x00000002 (n =   3)           (*) 20
   8         #0x00000001 (n =   1)               ( ) 30
   9         #0x00000005 (n =   6)       ( ) 40
  10         #0x00000003 (n =   1)               ( ) 50
  11         #0x00000004 (n =   2)           (*) 60
  12         #0x00000008 (n =   9)   (*) 70
  13         #0x00000007 (n =   2)           (*) 80
  14         #0x00000006 (n =   1)               ( ) 90
  15
  16 ;; Children of a black node.
  17 65
  18 tree dump, ht = 2
  19         #0x00000009 (n =   1)               ( ) 10
  20         #0x0000000b (n =   3)           (*) 20
  21         #0x0000000a (n =   1)               ( ) 30
  22         #0x0000000e (n =   7)       ( ) 40
  23         #0x0000000c (n =   1)               ( ) 50
  24         #0x0000000d (n =   3)           (*) 60
  25         #0x00000012 (n =   1)               ( ) 65
  26         #0x00000011 (n =  10)   (*) 70
  27         #0x00000010 (n =   2)           (*) 80
  28         #0x0000000f (n =   1)               ( ) 90
  29 75
  30 tree dump, ht = 2
  31         #0x00000013 (n =   1)               ( ) 10
  32         #0x00000015 (n =   3)           (*) 20
  33         #0x00000014 (n =   1)               ( ) 30
  34         #0x00000018 (n =   6)       ( ) 40
  35         #0x00000016 (n =   1)               ( ) 50
  36         #0x00000017 (n =   2)           (*) 60
  37         #0x0000001b (n =  10)   (*) 70
  38         #0x0000001c (n =   1)               ( ) 75
  39         #0x0000001a (n =   3)           (*) 80
  40         #0x00000019 (n =   1)               ( ) 90
  41
  42 ;; Ascend tree.
  43 5
  44 15
  45 0
  46 XYLA-RB INSERT red sibling: ascend
  47 XYLA-RB INSERT red sibling: extend tree
  48 tree dump, ht = 3
  49         #0x00000028 (n =   1)                       ( ) 0
  50         #0x00000026 (n =   2)                   (*) 5
  51         #0x0000001d (n =   4)               ( ) 10
  52         #0x00000027 (n =   1)                   (*) 15
  53         #0x0000001f (n =   6)           (*) 20
  54         #0x0000001e (n =   1)                   (*) 30
  55         #0x00000022 (n =  12)   (*) 40
  56         #0x00000020 (n =   1)                       ( ) 50
  57         #0x00000021 (n =   2)                   (*) 60
  58         #0x00000025 (n =   5)           (*) 70
  59         #0x00000024 (n =   2)                   (*) 80
  60         #0x00000023 (n =   1)                       ( ) 90
  61
  62 ;; Zig-zig.
  63 45
  64 XYLA-RB INSERT zig-zig (left child)
  65 tree dump, ht = 2
  66         #0x00000029 (n =   1)               ( ) 10
  67         #0x0000002b (n =   3)           (*) 20
  68         #0x0000002a (n =   1)               ( ) 30
  69         #0x0000002e (n =   7)       ( ) 40
  70         #0x00000032 (n =   1)               ( ) 45
  71         #0x0000002c (n =   3)           (*) 50
  72         #0x0000002d (n =   1)               ( ) 60
  73         #0x00000031 (n =  10)   (*) 70
  74         #0x00000030 (n =   2)           (*) 80
  75         #0x0000002f (n =   1)               ( ) 90
  76 95
  77 XYLA-RB INSERT zig-zig (right child)
  78 tree dump, ht = 2
  79         #0x00000033 (n =   1)               ( ) 10
  80         #0x00000035 (n =   3)           (*) 20
  81         #0x00000034 (n =   1)               ( ) 30
  82         #0x00000038 (n =   6)       ( ) 40
  83         #0x00000036 (n =   1)               ( ) 50
  84         #0x00000037 (n =   2)           (*) 60
  85         #0x0000003b (n =  10)   (*) 70
  86         #0x0000003a (n =   1)               ( ) 80
  87         #0x00000039 (n =   3)           (*) 90
  88         #0x0000003c (n =   1)               ( ) 95
  89
  90 ;; Zig-zag.
  91 55
  92 XYLA-RB INSERT zig-zag (left child)
  93 tree dump, ht = 2
  94         #0x0000003d (n =   1)               ( ) 10
  95         #0x0000003f (n =   3)           (*) 20
  96         #0x0000003e (n =   1)               ( ) 30
  97         #0x00000042 (n =   7)       ( ) 40
  98         #0x00000040 (n =   1)               ( ) 50
  99         #0x00000046 (n =   3)           (*) 55
 100         #0x00000041 (n =   1)               ( ) 60
 101         #0x00000045 (n =  10)   (*) 70
 102         #0x00000044 (n =   2)           (*) 80
 103         #0x00000043 (n =   1)               ( ) 90
 104 85
 105 XYLA-RB INSERT zig-zag (right child)
 106 tree dump, ht = 2
 107         #0x00000047 (n =   1)               ( ) 10
 108         #0x00000049 (n =   3)           (*) 20
 109         #0x00000048 (n =   1)               ( ) 30
 110         #0x0000004c (n =   6)       ( ) 40
 111         #0x0000004a (n =   1)               ( ) 50
 112         #0x0000004b (n =   2)           (*) 60
 113         #0x0000004f (n =  10)   (*) 70
 114         #0x0000004e (n =   1)               ( ) 80
 115         #0x00000050 (n =   3)           (*) 85
 116         #0x0000004d (n =   1)               ( ) 90
 117
 118 ;;;-------------------------------------------------------------------------
 119 ;;; Removal.
 120
 121 ;; Initial state.
 122 tree dump, ht = 3
 123         #0x00000051 (n =   1)                   (*) 0
 124         #0x00000055 (n =   5)               ( ) 2
 125         #0x00000052 (n =   1)                       ( ) 4
 126         #0x00000054 (n =   3)                   (*) 6
 127         #0x00000053 (n =   1)                       ( ) 8
 128         #0x00000057 (n =   7)           (*) 10
 129         #0x00000056 (n =   1)                   (*) 12
 130         #0x0000005f (n =  15)   (*) 14
 131         #0x00000058 (n =   1)                   (*) 16
 132         #0x0000005e (n =   7)           (*) 18
 133         #0x00000059 (n =   1)                       ( ) 20
 134         #0x0000005b (n =   3)                   (*) 22
 135         #0x0000005a (n =   1)                       ( ) 24
 136         #0x0000005d (n =   5)               ( ) 26
 137         #0x0000005c (n =   1)                   (*) 28
 138
 139 ;; Red node.
 140 2
 141 tree dump, ht = 3
 142         #0x00000060 (n =   1)                   (*) 0
 143         #0x00000061 (n =   4)               ( ) 4
 144         #0x00000063 (n =   2)                   (*) 6
 145         #0x00000062 (n =   1)                       ( ) 8
 146         #0x00000066 (n =   6)           (*) 10
 147         #0x00000065 (n =   1)                   (*) 12
 148         #0x0000006e (n =  14)   (*) 14
 149         #0x00000067 (n =   1)                   (*) 16
 150         #0x0000006d (n =   7)           (*) 18
 151         #0x00000068 (n =   1)                       ( ) 20
 152         #0x0000006a (n =   3)                   (*) 22
 153         #0x00000069 (n =   1)                       ( ) 24
 154         #0x0000006c (n =   5)               ( ) 26
 155         #0x0000006b (n =   1)                   (*) 28
 156 4
 157 tree dump, ht = 3
 158         #0x0000006f (n =   1)                   (*) 0
 159         #0x00000073 (n =   4)               ( ) 2
 160         #0x00000072 (n =   2)                   (*) 6
 161         #0x00000071 (n =   1)                       ( ) 8
 162         #0x00000075 (n =   6)           (*) 10
 163         #0x00000074 (n =   1)                   (*) 12
 164         #0x0000007d (n =  14)   (*) 14
 165         #0x00000076 (n =   1)                   (*) 16
 166         #0x0000007c (n =   7)           (*) 18
 167         #0x00000077 (n =   1)                       ( ) 20
 168         #0x00000079 (n =   3)                   (*) 22
 169         #0x00000078 (n =   1)                       ( ) 24
 170         #0x0000007b (n =   5)               ( ) 26
 171         #0x0000007a (n =   1)                   (*) 28
 172 8
 173 tree dump, ht = 3
 174         #0x0000007e (n =   1)                   (*) 0
 175         #0x00000082 (n =   4)               ( ) 2
 176         #0x0000007f (n =   1)                       ( ) 4
 177         #0x00000081 (n =   2)                   (*) 6
 178         #0x00000084 (n =   6)           (*) 10
 179         #0x00000083 (n =   1)                   (*) 12
 180         #0x0000008c (n =  14)   (*) 14
 181         #0x00000085 (n =   1)                   (*) 16
 182         #0x0000008b (n =   7)           (*) 18
 183         #0x00000086 (n =   1)                       ( ) 20
 184         #0x00000088 (n =   3)                   (*) 22
 185         #0x00000087 (n =   1)                       ( ) 24
 186         #0x0000008a (n =   5)               ( ) 26
 187         #0x00000089 (n =   1)                   (*) 28
 188 18
 189 tree dump, ht = 3
 190         #0x0000008d (n =   1)                   (*) 0
 191         #0x00000091 (n =   5)               ( ) 2
 192         #0x0000008e (n =   1)                       ( ) 4
 193         #0x00000090 (n =   3)                   (*) 6
 194         #0x0000008f (n =   1)                       ( ) 8
 195         #0x00000093 (n =   7)           (*) 10
 196         #0x00000092 (n =   1)                   (*) 12
 197         #0x0000009b (n =  14)   (*) 14
 198         #0x00000094 (n =   1)                   (*) 16
 199         #0x00000095 (n =   6)           (*) 20
 200         #0x00000097 (n =   2)                   (*) 22
 201         #0x00000096 (n =   1)                       ( ) 24
 202         #0x00000099 (n =   4)               ( ) 26
 203         #0x00000098 (n =   1)                   (*) 28
 204
 205 ;; Red sibling, outer red great-nibling.
 206 8
 207 tree dump, ht = 3
 208         #0x0000009c (n =   1)                   (*) 0
 209         #0x000000a0 (n =   4)               ( ) 2
 210         #0x0000009d (n =   1)                       ( ) 4
 211         #0x0000009f (n =   2)                   (*) 6
 212         #0x000000a2 (n =   6)           (*) 10
 213         #0x000000a1 (n =   1)                   (*) 12
 214         #0x000000aa (n =  14)   (*) 14
 215         #0x000000a3 (n =   1)                   (*) 16
 216         #0x000000a9 (n =   7)           (*) 18
 217         #0x000000a4 (n =   1)                       ( ) 20
 218         #0x000000a6 (n =   3)                   (*) 22
 219         #0x000000a5 (n =   1)                       ( ) 24
 220         #0x000000a8 (n =   5)               ( ) 26
 221         #0x000000a7 (n =   1)                   (*) 28
 222 12
 223 XYLA-RB REMOVE red sibling, outer red great-nibling (right child)
 224 tree dump, ht = 3
 225         #0x0000009c (n =   1)                   (*) 0
 226         #0x000000a0 (n =   5)           (*) 2
 227         #0x0000009d (n =   1)                   (*) 4
 228         #0x0000009f (n =   3)               ( ) 6
 229         #0x000000a2 (n =   1)                   (*) 10
 230         #0x000000aa (n =  13)   (*) 14
 231         #0x000000a3 (n =   1)                   (*) 16
 232         #0x000000a9 (n =   7)           (*) 18
 233         #0x000000a4 (n =   1)                       ( ) 20
 234         #0x000000a6 (n =   3)                   (*) 22
 235         #0x000000a5 (n =   1)                       ( ) 24
 236         #0x000000a8 (n =   5)               ( ) 26
 237         #0x000000a7 (n =   1)                   (*) 28
 238 20
 239 tree dump, ht = 3
 240         #0x000000ab (n =   1)                   (*) 0
 241         #0x000000af (n =   5)               ( ) 2
 242         #0x000000ac (n =   1)                       ( ) 4
 243         #0x000000ae (n =   3)                   (*) 6
 244         #0x000000ad (n =   1)                       ( ) 8
 245         #0x000000b1 (n =   7)           (*) 10
 246         #0x000000b0 (n =   1)                   (*) 12
 247         #0x000000b9 (n =  14)   (*) 14
 248         #0x000000b2 (n =   1)                   (*) 16
 249         #0x000000b8 (n =   6)           (*) 18
 250         #0x000000b5 (n =   2)                   (*) 22
 251         #0x000000b4 (n =   1)                       ( ) 24
 252         #0x000000b7 (n =   4)               ( ) 26
 253         #0x000000b6 (n =   1)                   (*) 28
 254 16
 255 XYLA-RB REMOVE red sibling, outer red great-nibling (left child)
 256 tree dump, ht = 3
 257         #0x000000ab (n =   1)                   (*) 0
 258         #0x000000af (n =   5)               ( ) 2
 259         #0x000000ac (n =   1)                       ( ) 4
 260         #0x000000ae (n =   3)                   (*) 6
 261         #0x000000ad (n =   1)                       ( ) 8
 262         #0x000000b1 (n =   7)           (*) 10
 263         #0x000000b0 (n =   1)                   (*) 12
 264         #0x000000b9 (n =  13)   (*) 14
 265         #0x000000b8 (n =   1)                   (*) 18
 266         #0x000000b5 (n =   3)               ( ) 22
 267         #0x000000b4 (n =   1)                   (*) 24
 268         #0x000000b7 (n =   5)           (*) 26
 269         #0x000000b6 (n =   1)                   (*) 28
 270
 271 ;; Red sibling, inner red great-nibling.
 272 4
 273 tree dump, ht = 3
 274         #0x000000ba (n =   1)                   (*) 0
 275         #0x000000be (n =   4)               ( ) 2
 276         #0x000000bd (n =   2)                   (*) 6
 277         #0x000000bc (n =   1)                       ( ) 8
 278         #0x000000c0 (n =   6)           (*) 10
 279         #0x000000bf (n =   1)                   (*) 12
 280         #0x000000c8 (n =  14)   (*) 14
 281         #0x000000c1 (n =   1)                   (*) 16
 282         #0x000000c7 (n =   7)           (*) 18
 283         #0x000000c2 (n =   1)                       ( ) 20
 284         #0x000000c4 (n =   3)                   (*) 22
 285         #0x000000c3 (n =   1)                       ( ) 24
 286         #0x000000c6 (n =   5)               ( ) 26
 287         #0x000000c5 (n =   1)                   (*) 28
 288 12
 289 XYLA-RB REMOVE red sibling, inner red great-nibling (right child)
 290 tree dump, ht = 3
 291         #0x000000ba (n =   1)                   (*) 0
 292         #0x000000be (n =   5)           (*) 2
 293         #0x000000bd (n =   1)                   (*) 6
 294         #0x000000bc (n =   3)               ( ) 8
 295         #0x000000c0 (n =   1)                   (*) 10
 296         #0x000000c8 (n =  13)   (*) 14
 297         #0x000000c1 (n =   1)                   (*) 16
 298         #0x000000c7 (n =   7)           (*) 18
 299         #0x000000c2 (n =   1)                       ( ) 20
 300         #0x000000c4 (n =   3)                   (*) 22
 301         #0x000000c3 (n =   1)                       ( ) 24
 302         #0x000000c6 (n =   5)               ( ) 26
 303         #0x000000c5 (n =   1)                   (*) 28
 304 24
 305 tree dump, ht = 3
 306         #0x000000c9 (n =   1)                   (*) 0
 307         #0x000000cd (n =   5)               ( ) 2
 308         #0x000000ca (n =   1)                       ( ) 4
 309         #0x000000cc (n =   3)                   (*) 6
 310         #0x000000cb (n =   1)                       ( ) 8
 311         #0x000000cf (n =   7)           (*) 10
 312         #0x000000ce (n =   1)                   (*) 12
 313         #0x000000d7 (n =  14)   (*) 14
 314         #0x000000d0 (n =   1)                   (*) 16
 315         #0x000000d6 (n =   6)           (*) 18
 316         #0x000000d1 (n =   1)                       ( ) 20
 317         #0x000000d3 (n =   2)                   (*) 22
 318         #0x000000d5 (n =   4)               ( ) 26
 319         #0x000000d4 (n =   1)                   (*) 28
 320 16
 321 XYLA-RB REMOVE red sibling, inner red great-nibling (left child)
 322 tree dump, ht = 3
 323         #0x000000c9 (n =   1)                   (*) 0
 324         #0x000000cd (n =   5)               ( ) 2
 325         #0x000000ca (n =   1)                       ( ) 4
 326         #0x000000cc (n =   3)                   (*) 6
 327         #0x000000cb (n =   1)                       ( ) 8
 328         #0x000000cf (n =   7)           (*) 10
 329         #0x000000ce (n =   1)                   (*) 12
 330         #0x000000d7 (n =  13)   (*) 14
 331         #0x000000d6 (n =   1)                   (*) 18
 332         #0x000000d1 (n =   3)               ( ) 20
 333         #0x000000d3 (n =   1)                   (*) 22
 334         #0x000000d5 (n =   5)           (*) 26
 335         #0x000000d4 (n =   1)                   (*) 28
 336
 337 ;; Red sibling, no red great-nibling.
 338 4
 339 8
 340 tree dump, ht = 3
 341         #0x000000d8 (n =   1)                   (*) 0
 342         #0x000000dc (n =   3)               ( ) 2
 343         #0x000000db (n =   1)                   (*) 6
 344         #0x000000de (n =   5)           (*) 10
 345         #0x000000dd (n =   1)                   (*) 12
 346         #0x000000e6 (n =  13)   (*) 14
 347         #0x000000df (n =   1)                   (*) 16
 348         #0x000000e5 (n =   7)           (*) 18
 349         #0x000000e0 (n =   1)                       ( ) 20
 350         #0x000000e2 (n =   3)                   (*) 22
 351         #0x000000e1 (n =   1)                       ( ) 24
 352         #0x000000e4 (n =   5)               ( ) 26
 353         #0x000000e3 (n =   1)                   (*) 28
 354 12
 355 XYLA-RB REMOVE red sibling, no red great-nibling (right child)
 356 tree dump, ht = 3
 357         #0x000000d8 (n =   1)                   (*) 0
 358         #0x000000dc (n =   4)           (*) 2
 359         #0x000000db (n =   1)                       ( ) 6
 360         #0x000000de (n =   2)                   (*) 10
 361         #0x000000e6 (n =  12)   (*) 14
 362         #0x000000df (n =   1)                   (*) 16
 363         #0x000000e5 (n =   7)           (*) 18
 364         #0x000000e0 (n =   1)                       ( ) 20
 365         #0x000000e2 (n =   3)                   (*) 22
 366         #0x000000e1 (n =   1)                       ( ) 24
 367         #0x000000e4 (n =   5)               ( ) 26
 368         #0x000000e3 (n =   1)                   (*) 28
 369 20
 370 24
 371 tree dump, ht = 3
 372         #0x000000e7 (n =   1)                   (*) 0
 373         #0x000000eb (n =   5)               ( ) 2
 374         #0x000000e8 (n =   1)                       ( ) 4
 375         #0x000000ea (n =   3)                   (*) 6
 376         #0x000000e9 (n =   1)                       ( ) 8
 377         #0x000000ed (n =   7)           (*) 10
 378         #0x000000ec (n =   1)                   (*) 12
 379         #0x000000f5 (n =  13)   (*) 14
 380         #0x000000ee (n =   1)                   (*) 16
 381         #0x000000f4 (n =   5)           (*) 18
 382         #0x000000f1 (n =   1)                   (*) 22
 383         #0x000000f3 (n =   3)               ( ) 26
 384         #0x000000f2 (n =   1)                   (*) 28
 385 16
 386 XYLA-RB REMOVE red sibling, no red great-nibling (left child)
 387 tree dump, ht = 3
 388         #0x000000e7 (n =   1)                   (*) 0
 389         #0x000000eb (n =   5)               ( ) 2
 390         #0x000000e8 (n =   1)                       ( ) 4
 391         #0x000000ea (n =   3)                   (*) 6
 392         #0x000000e9 (n =   1)                       ( ) 8
 393         #0x000000ed (n =   7)           (*) 10
 394         #0x000000ec (n =   1)                   (*) 12
 395         #0x000000f5 (n =  12)   (*) 14
 396         #0x000000f4 (n =   2)                   (*) 18
 397         #0x000000f1 (n =   1)                       ( ) 22
 398         #0x000000f3 (n =   4)           (*) 26
 399         #0x000000f2 (n =   1)                   (*) 28
 400
 401 ;; Black sibling, outer red nibling.
 402 4
 403 tree dump, ht = 3
 404         #0x000000f6 (n =   1)                   (*) 0
 405         #0x000000fa (n =   4)               ( ) 2
 406         #0x000000f9 (n =   2)                   (*) 6
 407         #0x000000f8 (n =   1)                       ( ) 8
 408         #0x000000fc (n =   6)           (*) 10
 409         #0x000000fb (n =   1)                   (*) 12
 410         #0x00000104 (n =  14)   (*) 14
 411         #0x000000fd (n =   1)                   (*) 16
 412         #0x00000103 (n =   7)           (*) 18
 413         #0x000000fe (n =   1)                       ( ) 20
 414         #0x00000100 (n =   3)                   (*) 22
 415         #0x000000ff (n =   1)                       ( ) 24
 416         #0x00000102 (n =   5)               ( ) 26
 417         #0x00000101 (n =   1)                   (*) 28
 418 0
 419 XYLA-RB REMOVE black sibling, outer red nibling (left child)
 420 tree dump, ht = 3
 421         #0x000000fa (n =   1)                   (*) 2
 422         #0x000000f9 (n =   3)               ( ) 6
 423         #0x000000f8 (n =   1)                   (*) 8
 424         #0x000000fc (n =   5)           (*) 10
 425         #0x000000fb (n =   1)                   (*) 12
 426         #0x00000104 (n =  13)   (*) 14
 427         #0x000000fd (n =   1)                   (*) 16
 428         #0x00000103 (n =   7)           (*) 18
 429         #0x000000fe (n =   1)                       ( ) 20
 430         #0x00000100 (n =   3)                   (*) 22
 431         #0x000000ff (n =   1)                       ( ) 24
 432         #0x00000102 (n =   5)               ( ) 26
 433         #0x00000101 (n =   1)                   (*) 28
 434 24
 435 tree dump, ht = 3
 436         #0x00000105 (n =   1)                   (*) 0
 437         #0x00000109 (n =   5)               ( ) 2
 438         #0x00000106 (n =   1)                       ( ) 4
 439         #0x00000108 (n =   3)                   (*) 6
 440         #0x00000107 (n =   1)                       ( ) 8
 441         #0x0000010b (n =   7)           (*) 10
 442         #0x0000010a (n =   1)                   (*) 12
 443         #0x00000113 (n =  14)   (*) 14
 444         #0x0000010c (n =   1)                   (*) 16
 445         #0x00000112 (n =   6)           (*) 18
 446         #0x0000010d (n =   1)                       ( ) 20
 447         #0x0000010f (n =   2)                   (*) 22
 448         #0x00000111 (n =   4)               ( ) 26
 449         #0x00000110 (n =   1)                   (*) 28
 450 28
 451 XYLA-RB REMOVE black sibling, outer red nibling (right child)
 452 tree dump, ht = 3
 453         #0x00000105 (n =   1)                   (*) 0
 454         #0x00000109 (n =   5)               ( ) 2
 455         #0x00000106 (n =   1)                       ( ) 4
 456         #0x00000108 (n =   3)                   (*) 6
 457         #0x00000107 (n =   1)                       ( ) 8
 458         #0x0000010b (n =   7)           (*) 10
 459         #0x0000010a (n =   1)                   (*) 12
 460         #0x00000113 (n =  13)   (*) 14
 461         #0x0000010c (n =   1)                   (*) 16
 462         #0x00000112 (n =   5)           (*) 18
 463         #0x0000010d (n =   1)                   (*) 20
 464         #0x0000010f (n =   3)               ( ) 22
 465         #0x00000111 (n =   1)                   (*) 26
 466
 467 ;; Black sibling, inner red nibling.
 468 8
 469 tree dump, ht = 3
 470         #0x00000114 (n =   1)                   (*) 0
 471         #0x00000118 (n =   4)               ( ) 2
 472         #0x00000115 (n =   1)                       ( ) 4
 473         #0x00000117 (n =   2)                   (*) 6
 474         #0x0000011a (n =   6)           (*) 10
 475         #0x00000119 (n =   1)                   (*) 12
 476         #0x00000122 (n =  14)   (*) 14
 477         #0x0000011b (n =   1)                   (*) 16
 478         #0x00000121 (n =   7)           (*) 18
 479         #0x0000011c (n =   1)                       ( ) 20
 480         #0x0000011e (n =   3)                   (*) 22
 481         #0x0000011d (n =   1)                       ( ) 24
 482         #0x00000120 (n =   5)               ( ) 26
 483         #0x0000011f (n =   1)                   (*) 28
 484 0
 485 XYLA-RB REMOVE black sibling, inner red nibling (left child)
 486 tree dump, ht = 3
 487         #0x00000118 (n =   1)                   (*) 2
 488         #0x00000115 (n =   3)               ( ) 4
 489         #0x00000117 (n =   1)                   (*) 6
 490         #0x0000011a (n =   5)           (*) 10
 491         #0x00000119 (n =   1)                   (*) 12
 492         #0x00000122 (n =  13)   (*) 14
 493         #0x0000011b (n =   1)                   (*) 16
 494         #0x00000121 (n =   7)           (*) 18
 495         #0x0000011c (n =   1)                       ( ) 20
 496         #0x0000011e (n =   3)                   (*) 22
 497         #0x0000011d (n =   1)                       ( ) 24
 498         #0x00000120 (n =   5)               ( ) 26
 499         #0x0000011f (n =   1)                   (*) 28
 500 20
 501 tree dump, ht = 3
 502         #0x00000123 (n =   1)                   (*) 0
 503         #0x00000127 (n =   5)               ( ) 2
 504         #0x00000124 (n =   1)                       ( ) 4
 505         #0x00000126 (n =   3)                   (*) 6
 506         #0x00000125 (n =   1)                       ( ) 8
 507         #0x00000129 (n =   7)           (*) 10
 508         #0x00000128 (n =   1)                   (*) 12
 509         #0x00000131 (n =  14)   (*) 14
 510         #0x0000012a (n =   1)                   (*) 16
 511         #0x00000130 (n =   6)           (*) 18
 512         #0x0000012d (n =   2)                   (*) 22
 513         #0x0000012c (n =   1)                       ( ) 24
 514         #0x0000012f (n =   4)               ( ) 26
 515         #0x0000012e (n =   1)                   (*) 28
 516 28
 517 XYLA-RB REMOVE black sibling, inner red nibling (right child)
 518 tree dump, ht = 3
 519         #0x00000123 (n =   1)                   (*) 0
 520         #0x00000127 (n =   5)               ( ) 2
 521         #0x00000124 (n =   1)                       ( ) 4
 522         #0x00000126 (n =   3)                   (*) 6
 523         #0x00000125 (n =   1)                       ( ) 8
 524         #0x00000129 (n =   7)           (*) 10
 525         #0x00000128 (n =   1)                   (*) 12
 526         #0x00000131 (n =  13)   (*) 14
 527         #0x0000012a (n =   1)                   (*) 16
 528         #0x00000130 (n =   5)           (*) 18
 529         #0x0000012d (n =   1)                   (*) 22
 530         #0x0000012c (n =   3)               ( ) 24
 531         #0x0000012f (n =   1)                   (*) 26
 532
 533 ;; Black sibling, red parent, no red nibling.
 534 4
 535 8
 536 tree dump, ht = 3
 537         #0x00000132 (n =   1)                   (*) 0
 538         #0x00000136 (n =   3)               ( ) 2
 539         #0x00000135 (n =   1)                   (*) 6
 540         #0x00000138 (n =   5)           (*) 10
 541         #0x00000137 (n =   1)                   (*) 12
 542         #0x00000140 (n =  13)   (*) 14
 543         #0x00000139 (n =   1)                   (*) 16
 544         #0x0000013f (n =   7)           (*) 18
 545         #0x0000013a (n =   1)                       ( ) 20
 546         #0x0000013c (n =   3)                   (*) 22
 547         #0x0000013b (n =   1)                       ( ) 24
 548         #0x0000013e (n =   5)               ( ) 26
 549         #0x0000013d (n =   1)                   (*) 28
 550 0
 551 XYLA-RB REMOVE black sibling, red parent, no red nibling (left child)
 552 tree dump, ht = 3
 553         #0x00000136 (n =   2)                   (*) 2
 554         #0x00000135 (n =   1)                       ( ) 6
 555         #0x00000138 (n =   4)           (*) 10
 556         #0x00000137 (n =   1)                   (*) 12
 557         #0x00000140 (n =  12)   (*) 14
 558         #0x00000139 (n =   1)                   (*) 16
 559         #0x0000013f (n =   7)           (*) 18
 560         #0x0000013a (n =   1)                       ( ) 20
 561         #0x0000013c (n =   3)                   (*) 22
 562         #0x0000013b (n =   1)                       ( ) 24
 563         #0x0000013e (n =   5)               ( ) 26
 564         #0x0000013d (n =   1)                   (*) 28
 565 20
 566 24
 567 tree dump, ht = 3
 568         #0x00000141 (n =   1)                   (*) 0
 569         #0x00000145 (n =   5)               ( ) 2
 570         #0x00000142 (n =   1)                       ( ) 4
 571         #0x00000144 (n =   3)                   (*) 6
 572         #0x00000143 (n =   1)                       ( ) 8
 573         #0x00000147 (n =   7)           (*) 10
 574         #0x00000146 (n =   1)                   (*) 12
 575         #0x0000014f (n =  13)   (*) 14
 576         #0x00000148 (n =   1)                   (*) 16
 577         #0x0000014e (n =   5)           (*) 18
 578         #0x0000014b (n =   1)                   (*) 22
 579         #0x0000014d (n =   3)               ( ) 26
 580         #0x0000014c (n =   1)                   (*) 28
 581 28
 582 XYLA-RB REMOVE black sibling, red parent, no red nibling (right child)
 583 tree dump, ht = 3
 584         #0x00000141 (n =   1)                   (*) 0
 585         #0x00000145 (n =   5)               ( ) 2
 586         #0x00000142 (n =   1)                       ( ) 4
 587         #0x00000144 (n =   3)                   (*) 6
 588         #0x00000143 (n =   1)                       ( ) 8
 589         #0x00000147 (n =   7)           (*) 10
 590         #0x00000146 (n =   1)                   (*) 12
 591         #0x0000014f (n =  12)   (*) 14
 592         #0x00000148 (n =   1)                   (*) 16
 593         #0x0000014e (n =   4)           (*) 18
 594         #0x0000014b (n =   1)                       ( ) 22
 595         #0x0000014d (n =   2)                   (*) 26
 596
 597 ;; Black sibling, black parent, no red nibling.
 598 4
 599 8
 600 0
 601 6
 602 20
 603 24
 604 16
 605 28
 606 tree dump, ht = 3
 607         #0x00000154 (n =   1)                   (*) 2
 608         #0x00000156 (n =   3)           (*) 10
 609         #0x00000155 (n =   1)                   (*) 12
 610         #0x0000015e (n =   7)   (*) 14
 611         #0x0000015d (n =   1)                   (*) 18
 612         #0x0000015a (n =   3)           (*) 22
 613         #0x0000015c (n =   1)                   (*) 26
 614 12
 615 XYLA-RB REMOVE black sibling, black parent, no red nibling (right child)
 616 XYLA-RB REMOVE black sibling, black parent, no red nibling (left child)
 617 XYLA-RB REMOVE shorten tree
 618 tree dump, ht = 2
 619         #0x0000015f (n =   1)               ( ) 2
 620         #0x00000161 (n =   2)           (*) 10
 621         #0x00000165 (n =   6)   (*) 14
 622         #0x00000162 (n =   1)           (*) 18
 623         #0x00000164 (n =   3)       ( ) 22
 624         #0x00000163 (n =   1)           (*) 26
 625 18
 626 XYLA-RB REMOVE black sibling, black parent, no red nibling (left child)
 627 XYLA-RB REMOVE black sibling, black parent, no red nibling (right child)
 628 XYLA-RB REMOVE shorten tree
 629 tree dump, ht = 2
 630         #0x00000166 (n =   1)           (*) 2
 631         #0x00000168 (n =   3)       ( ) 10
 632         #0x00000167 (n =   1)           (*) 12
 633         #0x0000016c (n =   6)   (*) 14
 634         #0x0000016b (n =   2)           (*) 22
 635         #0x0000016a (n =   1)               ( ) 26
 636 ;;;-------------------------------------------------------------------------
 637 ;;; Joining.
 638
 639 ;; Equal heights.
 640 tree dump, ht = 2
 641         #0x0000016d (n =   1)           (*) 1
 642         #0x0000016e (n =   6)   (*) 2
 643         #0x0000016f (n =   1)           (*) 3
 644         #0x00000170 (n =   4)       ( ) 4
 645         #0x00000171 (n =   2)           (*) 5
 646         #0x00000172 (n =   1)               ( ) 6
 647 tree dump, ht = 2
 648         #0x00000178 (n =   1)               ( ) 8
 649         #0x00000177 (n =   2)           (*) 9
 650         #0x00000176 (n =   4)       ( ) 10
 651         #0x00000175 (n =   1)           (*) 11
 652         #0x00000174 (n =   6)   (*) 12
 653         #0x00000173 (n =   1)           (*) 13
 654 7
 655 XYLA-RB JOIN equal heights
 656 tree dump, ht = 3
 657         #0x0000016d (n =   1)                   (*) 1
 658         #0x0000016e (n =   6)           (*) 2
 659         #0x0000016f (n =   1)                   (*) 3
 660         #0x00000170 (n =   4)               ( ) 4
 661         #0x00000171 (n =   2)                   (*) 5
 662         #0x00000172 (n =   1)                       ( ) 6
 663         #0x00000179 (n =  13)   (*) 7
 664         #0x00000178 (n =   1)                       ( ) 8
 665         #0x00000177 (n =   2)                   (*) 9
 666         #0x00000176 (n =   4)               ( ) 10
 667         #0x00000175 (n =   1)                   (*) 11
 668         #0x00000174 (n =   6)           (*) 12
 669         #0x00000173 (n =   1)                   (*) 13
 670
 671 ;; Red sibling.
 672 tree dump, ht = 2
 673         #0x0000017a (n =   1)           (*) 1
 674         #0x0000017b (n =   3)       ( ) 2
 675         #0x0000017c (n =   1)           (*) 3
 676         #0x0000017d (n =   8)   (*) 4
 677         #0x0000017e (n =   1)           (*) 5
 678         #0x0000017f (n =   4)       ( ) 6
 679         #0x00000180 (n =   2)           (*) 7
 680         #0x00000181 (n =   1)               ( ) 8
 681 tree dump, ht = 1
 682         #0x00000182 (n =   1)   (*) 10
 683 9
 684 XYLA-RB JOIN red sibling (right child): extend tree
 685 tree dump, ht = 3
 686         #0x0000017a (n =   1)                   (*) 1
 687         #0x0000017b (n =   3)           (*) 2
 688         #0x0000017c (n =   1)                   (*) 3
 689         #0x0000017d (n =  10)   (*) 4
 690         #0x0000017e (n =   1)                   (*) 5
 691         #0x0000017f (n =   6)           (*) 6
 692         #0x00000180 (n =   2)                   (*) 7
 693         #0x00000181 (n =   1)                       ( ) 8
 694         #0x00000183 (n =   4)               ( ) 9
 695         #0x00000182 (n =   1)                   (*) 10
 696 tree dump, ht = 1
 697         #0x00000184 (n =   1)   (*) 1
 698 tree dump, ht = 2
 699         #0x0000018c (n =   1)               ( ) 3
 700         #0x0000018b (n =   2)           (*) 4
 701         #0x0000018a (n =   4)       ( ) 5
 702         #0x00000189 (n =   1)           (*) 6
 703         #0x00000188 (n =   8)   (*) 7
 704         #0x00000187 (n =   1)           (*) 8
 705         #0x00000186 (n =   3)       ( ) 9
 706         #0x00000185 (n =   1)           (*) 10
 707 2
 708 XYLA-RB JOIN red sibling (left child): extend tree
 709 tree dump, ht = 3
 710         #0x00000184 (n =   1)                   (*) 1
 711         #0x0000018d (n =   4)               ( ) 2
 712         #0x0000018c (n =   1)                       ( ) 3
 713         #0x0000018b (n =   2)                   (*) 4
 714         #0x0000018a (n =   6)           (*) 5
 715         #0x00000189 (n =   1)                   (*) 6
 716         #0x00000188 (n =  10)   (*) 7
 717         #0x00000187 (n =   1)                   (*) 8
 718         #0x00000186 (n =   3)           (*) 9
 719         #0x00000185 (n =   1)                   (*) 10
 720 tree dump, ht = 3
 721         #0x0000018e (n =   1)                   (*) 1
 722         #0x0000018f (n =   3)           (*) 2
 723         #0x00000190 (n =   1)                   (*) 3
 724         #0x00000191 (n =  12)   (*) 4
 725         #0x00000192 (n =   1)                   (*) 5
 726         #0x00000193 (n =   3)               ( ) 6
 727         #0x00000194 (n =   1)                   (*) 7
 728         #0x00000195 (n =   8)           (*) 8
 729         #0x00000196 (n =   1)                   (*) 9
 730         #0x00000197 (n =   4)               ( ) 10
 731         #0x00000198 (n =   2)                   (*) 11
 732         #0x00000199 (n =   1)                       ( ) 12
 733 tree dump, ht = 1
 734         #0x0000019a (n =   1)   (*) 14
 735 13
 736 XYLA-RB JOIN red sibling (right child): ascend
 737 tree dump, ht = 3
 738         #0x0000018e (n =   1)                   (*) 1
 739         #0x0000018f (n =   3)           (*) 2
 740         #0x00000190 (n =   1)                   (*) 3
 741         #0x00000191 (n =  14)   (*) 4
 742         #0x00000192 (n =   1)                   (*) 5
 743         #0x00000193 (n =   3)           (*) 6
 744         #0x00000194 (n =   1)                   (*) 7
 745         #0x00000195 (n =  10)       ( ) 8
 746         #0x00000196 (n =   1)                   (*) 9
 747         #0x00000197 (n =   6)           (*) 10
 748         #0x00000198 (n =   2)                   (*) 11
 749         #0x00000199 (n =   1)                       ( ) 12
 750         #0x0000019b (n =   4)               ( ) 13
 751         #0x0000019a (n =   1)                   (*) 14
 752 tree dump, ht = 1
 753         #0x0000019c (n =   1)   (*) 1
 754 tree dump, ht = 3
 755         #0x000001a6 (n =   1)                       ( ) 3
 756         #0x000001a5 (n =   2)                   (*) 4
 757         #0x000001a4 (n =   4)               ( ) 5
 758         #0x000001a3 (n =   1)                   (*) 6
 759         #0x000001a2 (n =   6)           (*) 7
 760         #0x000001a1 (n =   1)                   (*) 8
 761         #0x000001a0 (n =  10)   (*) 9
 762         #0x0000019f (n =   1)                   (*) 10
 763         #0x0000019e (n =   3)           (*) 11
 764         #0x0000019d (n =   1)                   (*) 12
 765 2
 766 XYLA-RB JOIN no red sibling (left child)
 767 tree dump, ht = 3
 768         #0x0000019c (n =   1)                   (*) 1
 769         #0x000001a7 (n =   4)               ( ) 2
 770         #0x000001a6 (n =   1)                       ( ) 3
 771         #0x000001a5 (n =   2)                   (*) 4
 772         #0x000001a4 (n =   8)           (*) 5
 773         #0x000001a3 (n =   1)                   (*) 6
 774         #0x000001a2 (n =   3)               ( ) 7
 775         #0x000001a1 (n =   1)                   (*) 8
 776         #0x000001a0 (n =  12)   (*) 9
 777         #0x0000019f (n =   1)                   (*) 10
 778         #0x0000019e (n =   3)           (*) 11
 779         #0x0000019d (n =   1)                   (*) 12
 780
 781 ;; No red sibling.
 782 tree dump, ht = 2
 783         #0x000001a8 (n =   1)           (*) 1
 784         #0x000001a9 (n =   7)   (*) 2
 785         #0x000001aa (n =   1)           (*) 3
 786         #0x000001ab (n =   5)       ( ) 4
 787         #0x000001ac (n =   1)               ( ) 5
 788         #0x000001ad (n =   3)           (*) 6
 789         #0x000001ae (n =   1)               ( ) 7
 790 tree dump, ht = 1
 791         #0x000001af (n =   1)   (*) 9
 792 8
 793 XYLA-RB JOIN no red sibling (right child)
 794 tree dump, ht = 2
 795         #0x000001a8 (n =   1)           (*) 1
 796         #0x000001a9 (n =   3)       ( ) 2
 797         #0x000001aa (n =   1)           (*) 3
 798         #0x000001ab (n =   9)   (*) 4
 799         #0x000001ac (n =   1)               ( ) 5
 800         #0x000001ad (n =   3)           (*) 6
 801         #0x000001ae (n =   1)               ( ) 7
 802         #0x000001b0 (n =   5)       ( ) 8
 803         #0x000001af (n =   1)           (*) 9
 804 tree dump, ht = 1
 805         #0x000001b1 (n =   1)   (*) 1
 806 tree dump, ht = 2
 807         #0x000001b8 (n =   1)               ( ) 3
 808         #0x000001b7 (n =   3)           (*) 4
 809         #0x000001b6 (n =   1)               ( ) 5
 810         #0x000001b5 (n =   5)       ( ) 6
 811         #0x000001b4 (n =   1)           (*) 7
 812         #0x000001b3 (n =   7)   (*) 8
 813         #0x000001b2 (n =   1)           (*) 9
 814 2
 815 XYLA-RB JOIN no red sibling (left child)
 816 tree dump, ht = 2
 817         #0x000001b1 (n =   1)           (*) 1
 818         #0x000001b9 (n =   5)       ( ) 2
 819         #0x000001b8 (n =   1)               ( ) 3
 820         #0x000001b7 (n =   3)           (*) 4
 821         #0x000001b6 (n =   1)               ( ) 5
 822         #0x000001b5 (n =   9)   (*) 6
 823         #0x000001b4 (n =   1)           (*) 7
 824         #0x000001b3 (n =   3)       ( ) 8
 825         #0x000001b2 (n =   1)           (*) 9
 826
 827 ;;;----- That's all, folks -------------------------------------------------