rb.om (2948B)
1 struct rbnode { 2 red: int; 3 parent: *rbnode; 4 left: *rbnode; 5 right: *rbnode; 6 } 7 8 func rb_rotate_left(tree: **rbnode, n: *rbnode) { 9 var gg: *rbnode; 10 var g: *rbnode; 11 var p: *rbnode; 12 var s: *rbnode; 13 14 s = n.left; 15 p = n.parent; 16 g = p.parent; 17 18 n.left = p; 19 p.parent = n; 20 21 p.right = s; 22 if s { 23 s.parent = p; 24 } 25 26 n.parent = g; 27 if g { 28 if g.left == p { 29 g.left = n; 30 } else { 31 g.right = n; 32 } 33 } else { 34 *tree = n; 35 } 36 } 37 38 func rb_rotate_right(tree: **rbnode, n: *rbnode) { 39 var gg: *rbnode; 40 var g: *rbnode; 41 var p: *rbnode; 42 var s: *rbnode; 43 44 s = n.right; 45 p = n.parent; 46 g = p.parent; 47 48 n.right = p; 49 p.parent = n; 50 51 p.left = s; 52 if s { 53 s.parent = p; 54 } 55 56 n.parent = g; 57 if g { 58 if g.left == p { 59 g.left = n; 60 } else { 61 g.right = n; 62 } 63 } else { 64 *tree = n; 65 } 66 } 67 68 func rb_link(tree: **rbnode, link: **rbnode, parent: *rbnode, n: *rbnode) { 69 var l: *rbnode; 70 var r: *rbnode; 71 var g: *rbnode; 72 var p: *rbnode; 73 74 // Insert a red node to not disturb the black balance. 75 n.red = 1; 76 n.parent = parent; 77 n.left = nil; 78 n.right = nil; 79 *link = n; 80 81 loop { 82 p = n.parent; 83 if !p { 84 // If we have reached the root make sure it's black. 85 // At this point no more red-red violations are possible. 86 n.red = 0; 87 return; 88 } 89 90 if !p.red { 91 // We reached a node that's black. 92 // There is no red-red violation and our transformations did not disturb balance. 93 return; 94 } 95 96 g = p.parent; 97 if !g { 98 // Parent is the root and is red, just color it black. 99 p.red = 0; 100 return; 101 } 102 103 // Now, n is red and p is red. This is a red-red violation. 104 l = g.left; 105 r = g.right; 106 if l && r && l.red && r.red { 107 // Both parent and it's sibling are red. 108 // We can bubble up to the grandparent. 109 l.red = 0; 110 r.red = 0; 111 g.red = 1; 112 n = g; 113 continue; 114 } 115 116 // Otherwise, we require rotations to resolve the violation. 117 if p == g.left { 118 if n == p.left { 119 n.red = 0; 120 rb_rotate_right(tree, p); 121 n = p; 122 } else { 123 p.red = 0; 124 rb_rotate_left(tree, n); 125 rb_rotate_right(tree, n); 126 } 127 } else { 128 if n == p.left { 129 p.red = 0; 130 rb_rotate_right(tree, n); 131 rb_rotate_left(tree, n); 132 } else { 133 n.red = 0; 134 rb_rotate_left(tree, p); 135 n = p; 136 } 137 } 138 } 139 } 140 141 func rb_first(n: *rbnode): *rbnode { 142 if !n { 143 return nil; 144 } 145 146 loop { 147 if !n.left { 148 break; 149 } 150 151 n = n.left; 152 } 153 154 return n; 155 } 156 157 func rb_last(n: *rbnode): *rbnode { 158 if !n { 159 return nil; 160 } 161 162 loop { 163 if !n.right { 164 break; 165 } 166 167 n = n.right; 168 } 169 170 return n; 171 } 172 173 func rb_next(n: *rbnode): *rbnode { 174 if !n { 175 return nil; 176 } 177 178 if n.right { 179 return rb_first(n.right); 180 } 181 182 loop { 183 if !n.parent { 184 return nil; 185 } 186 187 if n.parent.left == n { 188 return n.parent; 189 } 190 191 n = n.parent; 192 } 193 } 194 195 func rb_prev(n: *rbnode): *rbnode { 196 if !n { 197 return nil; 198 } 199 200 if n.left { 201 return rb_last(n.left); 202 } 203 204 loop { 205 if !n.parent { 206 return nil; 207 } 208 209 if n.parent.right == n { 210 return n.parent; 211 } 212 213 n = n.parent; 214 } 215 }