58 void rotateLeft(
Node *node);
59 void rotateRight(
Node *node);
60 void update(
Node *node);
65 int blackDepth(
Node *
top)
const;
66 bool checkRedBlackProperty(
Node *
top)
const;
69 void detach(
Node *node);
72 void rebalance(
Node *node);
87 freeList->right =
nullptr;
111 Node *&
ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
113 node->right->parent = node->parent;
122 node->right =
ref->left;
124 ref->left->parent = node;
152 Node *&
ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
154 node->left->parent = node->parent;
156 node->left =
ref->right;
158 ref->right->parent = node;
168 Node *parent = node->parent;
181 Node *grandpa = parent->parent;
184 Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
185 if (uncle && uncle->red) {
197 if (node == parent->right && parent == grandpa->left)
198 rotateLeft(node = parent);
199 else if (node == parent->left && parent == grandpa->right)
200 rotateRight(node = parent);
201 parent = node->parent;
203 if (parent == grandpa->left) {
204 rotateRight(grandpa);
220 parent->left =
child;
221 child->parent = parent;
229 parent->right =
child;
230 child->parent = parent;
238 update(root =
child);
240 attachRight(back(root),
child);
241 else if (parent->
left)
244 attachLeft(parent,
child);
251 update(root =
child);
253 attachLeft(front(root),
child);
254 else if (parent->
right)
257 attachRight(parent,
child);
264 if (n1->parent == n2) {
265 n1->parent = n2->parent;
267 }
else if (n2->parent == n1) {
268 n2->parent = n1->parent;
271 qSwap(n1->parent, n2->parent);
274 qSwap(n1->left, n2->left);
275 qSwap(n1->right, n2->right);
276 qSwap(n1->red, n2->red);
279 if (n1->parent->left == n2)
280 n1->parent->left = n1;
282 n1->parent->right = n1;
288 if (n2->parent->left == n1)
289 n2->parent->left = n2;
291 n2->parent->right = n2;
297 n1->left->parent = n1;
299 n1->right->parent = n1;
302 n2->left->parent = n2;
304 n2->right->parent = n2;
311 swapNodes(node, front(node->right));
313 Node *
child = (node->left ? node->left : node->right);
322 Node *&
ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
325 child->parent = node->parent;
326 node->left = node->right = node->parent =
nullptr;
339 Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
343 sibling->red =
false;
344 node->parent->red =
true;
345 if (node == node->parent->left)
346 rotateLeft(node->parent);
348 rotateRight(node->parent);
349 sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
356 if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
357 bool parentWasRed = node->parent->red;
359 node->parent->red =
false;
368 if (node == node->parent->left) {
369 if (!sibling->right || !sibling->right->red) {
372 sibling->left->red =
false;
373 rotateRight(sibling);
375 sibling = sibling->parent;
378 sibling->red = node->parent->red;
379 node->parent->red =
false;
382 sibling->right->red =
false;
383 rotateLeft(node->parent);
385 if (!sibling->left || !sibling->left->red) {
388 sibling->right->red =
false;
391 sibling = sibling->parent;
394 sibling->red = node->parent->red;
395 node->parent->red =
false;
398 sibling->left->red =
false;
399 rotateRight(node->parent);
425 return front(node->
right);
435 return back(node->
left);
446 int leftDepth = blackDepth(
top->left);
447 int rightDepth = blackDepth(
top->right);
448 if (leftDepth != rightDepth)
460 if (
top->left && !checkRedBlackProperty(
top->left))
462 if (
top->right && !checkRedBlackProperty(
top->right))
464 return !(
top->red && ((
top->left &&
top->left->red) || (
top->right &&
top->right->red)));
470 return checkRedBlackProperty(root) && blackDepth(root) != -1;
505 QList<Node *> leftAncestors;
506 QList<Node *> rightAncestors;
508 leftAncestors.push_back(
left);
512 rightAncestors.push_back(
right);
515 Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);
517 while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
518 leftAncestors.pop_back();
519 rightAncestors.pop_back();
522 if (!leftAncestors.empty())
523 return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);
525 if (!rightAncestors.empty())
526 return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);
529 Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());