64 comp = z->nm.compare(hint->parent->nm);
65 if ((comp>0 && hint == hint->parent->left)
66 || (comp<0 && hint == hint->parent->right))
78 for (; hint; hint = comp<0 ? hint->left : hint->right)
82 comp = z->nm.compare(hint->nm);
83 if (!comp)
return hint;
86 if (y == &header || z->nm < y->nm)
97 else if (y == header.left) header.left = z;
104 if (y == header.right) header.right = z;
121 void Tree::rebalance(TreeNode* x)
125 while (x != header.parent && x->parent->color ==
red)
127 if (x->parent == x->parent->parent->left)
129 TreeNode* y = x->parent->parent->right;
130 if (y && y->color ==
red)
132 x->parent->color =
black;
134 x->parent->parent->color =
red;
135 x = x->parent->parent;
139 if (x == x->parent->right)
144 x->parent->color =
black;
145 x->parent->parent->color =
red;
146 rotateRight(x->parent->parent);
151 TreeNode* y = x->parent->parent->left;
152 if (y && y->color ==
red)
154 x->parent->color =
black;
156 x->parent->parent->color =
red;
157 x = x->parent->parent;
161 if (x == x->parent->left)
166 x->parent->color =
black;
167 x->parent->parent->color =
red;
168 rotateLeft(x->parent->parent);
172 header.parent->color =
black;
180 if (!z || z->color ==
none)
return;
188 else if (y->right == NULL)
194 while (y->left != NULL) y = y->left;
204 x_parent = y->parent;
205 if (x) x->parent = y->parent;
208 z->right->parent = y;
212 if (header.parent == z) header.parent = y;
213 else if (z->parent->left == z) z->parent->left = y;
214 else z->parent->right = y;
215 y->parent = z->parent;
216 std::swap(y->color, z->color);
223 x_parent = y->parent;
224 if (x) x->parent = y->parent;
225 if (header.parent == z) header.parent = x;
226 else if (z->parent->left == z) z->parent->left = x;
227 else z->parent->right = x;
228 if (header.left == z)
230 if (z->right == NULL)
231 header.left = z->parent;
234 header.left = minimum(x);
236 if (header.right == z)
239 header.right = z->parent;
242 header.right = maximum(x);
247 while (x != header.parent && (x == NULL || x->color ==
black))
248 if (x == x_parent->left)
254 x_parent->color =
red;
255 rotateLeft(x_parent);
258 if ((w->left == NULL || w->left->color ==
black) &&
259 (w->right == NULL || w->right->color ==
black))
263 x_parent = x_parent->parent;
267 if (w->right == NULL || w->right->color ==
black)
269 w->left->color =
black;
274 w->color = x_parent->color;
275 x_parent->color =
black;
276 if (w->right) w->right->color =
black;
277 rotateLeft(x_parent);
288 x_parent->color =
red;
289 rotateRight(x_parent);
292 if ((w->right == NULL || w->right->color ==
black) &&
293 (w->left == NULL || w->left->color ==
black))
297 x_parent = x_parent->parent;
301 if (w->left == NULL || w->left->color ==
black)
303 w->right->color =
black;
308 w->color = x_parent->color;
309 x_parent->color =
black;
310 if (w->left) w->left->color =
black;
311 rotateRight(x_parent);
315 if (x) x->color =
black;
320 void Tree::rotateLeft(TreeNode* x)
322 TreeNode* y = x->right;
324 if (y->left != NULL) y->left->parent = x;
325 y->parent = x->parent;
327 if (x == header.parent)
330 else if (x == x->parent->left)
335 x->parent->right = y;
341 void Tree::rotateRight(TreeNode* x)
343 TreeNode* y = x->left;
345 if (y->right != NULL) y->right->parent = x;
346 y->parent = x->parent;
348 if (x == header.parent)
351 else if (x == x->parent->right)
353 x->parent->right = y;
367 bool ok = (
empty() &&
369 header.left == &header &&
370 header.right == &header);
375 unsigned int len = countBlackNodes(header.left);
383 if (x->color ==
none)
388 if ((L && L->color ==
red) || (R && R->color ==
red))
392 if (L && x->nm<L->nm)
396 if (R && R->nm<x->nm)
400 if (!L && !R && countBlackNodes(x) != len)
407 if (header.left != minimum(header.parent))
411 if (header.right != maximum(header.parent))
415 if (counter !=
size())