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

   1 :;;;-------------------------------------------------------------------------
   2 :;;; Insertion.
   3
   4 :
   5 :;; Starting point for the following tests.
   6 =                               ((((_ 10 _)
   7                         *20
   8                                 (_ 30 _))
   9                 40
  10                                 ((_ 50 _)
  11                         *60 _))
  12         *70
  13                         (_ *80
  14                                 (_ 90 _)))
  15 D!
  16
  17 :
  18 :;; Children of a black node.
  19 " 65k+ D! )
  20 " 75k+ D! )
  21
  22 :
  23 :;; Ascend tree.
  24 ;;                p                               p
  25 ;;                 (*)                             ( )
  26 ;;          n    /     \    s               n    /     \    s
  27 ;;           ( )         ( )    --->         (*)         (*)
  28 ;;      c   /   \       /   \           c   /   \       /   \
  29 ;;       ( )                             ( )
  30 ;;      /   \                           /   \
  31 " 5k+ 15k+ 0k+ D! )
  32
  33 :
  34 :;; Zig-zig.
  35 ;;                p
  36 ;;                 (*)                        n
  37 ;;          n    /     \                       (*)
  38 ;;           ( )                --->    c    /     \    p
  39 ;;      c   /   \                        ( )         ( )
  40 ;;       ( )                            /   \       /   \
  41 ;;      /   \
  42 " 45k+ D! )
  43 " 95k+ D! )
  44
  45 :
  46 :;; Zig-zag.
  47 ;;                p
  48 ;;                 (*)                        c
  49 ;;          n    /     \                       (*)
  50 ;;           ( )                --->    n    /     \    p
  51 ;;          /   \   c                    ( )         ( )
  52 ;;               ( )                    /   \       /   \
  53 ;;              /   \
  54 " 55k+ D! )
  55 " 85k+ D! )
  56
  57 :
  58 :;;;-------------------------------------------------------------------------
  59 :;;; Removal.
  60
  61 ;; There are too many cases here.
  62
  63 :
  64 :;; Initial state.
  65 =                                       ((((_ *0 _)
  66                                 2
  67                                                 ((_ 4 _)
  68                                         *6
  69                                                 (_ 8 _)))
  70                         *10
  71                                         (_ *12 _))
  72         *14
  73                                         ((_ *16 _)
  74                         *18
  75                                                 (((_ 20 _)
  76                                         *22
  77                                                 (_ 24 _))
  78                                 26
  79                                         (_ *28 _))))
  80 D!
  81
  82 :
  83 :;; Red node.
  84 " 2k- D! )
  85 " 4k- D! )
  86 " 8k- D! )
  87 " 18k- D! )
  88
  89 :
  90 :;; Red sibling, outer red great-nibling.
  91 ;;            p                                       s
  92 ;;             (*)                                     (*)
  93 ;;     n     /     \    s                       t    /     \
  94 ;;      (* *)        ( )        --->             ( )
  95 ;;      /   \   t   /   \                   p   /   \   r
  96 ;;               (*)                         (*)     (*)
  97 ;;              /   \   r               n   /   \   /   \
  98 ;;                   ( )                 (*)
  99 ;;                  /   \               /   \
 100 " 8k- D! 12k- D! )
 101 " 20k- D! 16k- D! )
 102
 103 :
 104 :;; Red sibling, inner red great-nibling.
 105 ;;            p                                       s
 106 ;;             (*)                                     (*)
 107 ;;     n     /     \    s                       l    /     \
 108 ;;      (* *)        ( )        --->             ( )
 109 ;;      /   \   t   /   \                   p   /   \   t
 110 ;;               (*)                         (*)     (*)
 111 ;;          l   /   \                   n   /   \   /   \
 112 ;;           ( )                         (*)
 113 ;;          /   \                       /   \
 114 " 4k- D! 12k- D! )
 115 " 24k- D! 16k- D! )
 116
 117 :
 118 :;; Red sibling, no red great-nibling.
 119 ;;            p                                   s
 120 ;;             (*)                                 (*)
 121 ;;     n     /     \    s                   p    /     \
 122 ;;      (* *)        ( )        --->         (*)
 123 ;;      /   \   t   /   \               n   /   \   t
 124 ;;               (*)                     (*)     ( )
 125 ;;              /   \                   /   \   /   \
 126 " 4k- 8k- D! 12k- D! )
 127 " 20k- 24k- D! 16k- D! )
 128
 129 :
 130 :;; Black sibling, outer red nibling.
 131 ;;            p                                    s
 132 ;;             (?)                                  (?)
 133 ;;     n     /     \   s                     p    /     \   r
 134 ;;      (* *)       (*)         --->          (*)        (*)
 135 ;;      /   \      /   \   r            n    /   \      /   \
 136 ;;                      ( )              (*)
 137 ;;                     /   \            /   \
 138 " 4k- D! 0k- D! )
 139 " 24k- D! 28k- D! )
 140
 141 :
 142 :;; Black sibling, inner red nibling.
 143 ;;            p                                    l
 144 ;;             (?)                                  (?)
 145 ;;     n     /     \   s                     p    /     \   s
 146 ;;      (* *)       (*)         --->          (*)        (*)
 147 ;;      /   \  l   /   \                n    /   \      /   \
 148 ;;              ( )                      (*)
 149 ;;             /   \                    /   \
 150 " 8k- D! 0k- D! )
 151 " 20k- D! 28k- D! )
 152
 153 :
 154 :;; Black sibling, red parent, no red nibling.
 155 ;;            p                                    p
 156 ;;             ( )                                  (*)
 157 ;;     n     /     \   s                     p    /     \   s
 158 ;;      (* *)       (*)         --->          (*)        ( )
 159 ;;      /   \      /   \                n    /   \      /   \
 160 " 4k- 8k- D! 0k- D! )
 161 " 20k- 24k- D! 28k- D! )
 162
 163 :
 164 :;; Black sibling, black parent, no red nibling.
 165 ;;            p                                    p
 166 ;;             (*)                                 (* *)
 167 ;;     n     /     \   s                     p    /     \   s
 168 ;;      (* *)       (*)         --->          (*)        ( )
 169 ;;      /   \      /   \                n    /   \      /   \
 170 " 4k- 8k- 0k- 6k- 20k- 24k- 16k- 28k- D!
 171 " 12k- D! )
 172 " 18k- D! ) )
 173
 174 :;;;-------------------------------------------------------------------------
 175 :;;; Joining.
 176
 177 :
 178 :;; Equal heights.
 179 =_ #6 D! ( #13-8 D! 7k ~ D!
 180
 181 :
 182 :;; Red sibling.
 183 =_ #8 D! ( 10+ D! 9k~ D!
 184 =_ 1+ D! ( #10-3 D! 2k~ D!
 185
 186 =_ #12 D! ( 14+ D! 13k~ D!
 187 =_ 1+ D! ( #12-3 D! 2k~ D!
 188
 189 :
 190 :;; No red sibling.
 191 =_ # 7 D! ( 9+ D! 8k~ D!
 192 =_ 1+ D! ( #9-3 D! 2k~ D!
 193
 194 :
 195 :;;;----- That's all, folks -------------------------------------------------