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