struct node *grandparent(struct node *n) { if ((n != NULL) && (n->parent != NULL)) return n->parent->parent; else return NULL; } struct node *uncle(struct node *n) { struct node *g = grandparent(n); if (g == NULL) return NULL; // No grandparent means no uncle if (n->parent == g->left) return g->right; else return g->left; }




void insert_case1(struct node *n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n); }

void insert_case2(struct node *n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n); }

void insert_case3(struct node *n) { struct node *u = uncle(n), *g; if ((u != NULL) && (u->color == RED)) { n->parent->color = BLACK; u->color = BLACK; g = grandparent(n); g->color = RED; insert_case1(g); } else { insert_case4(n); } }


void insert_case4(struct node *n) { struct node *g = grandparent(n); if ((n == n->parent->right) && (n->parent == g->left)) { rotate_left(n->parent); n = n->left; } else if ((n == n->parent->left) && (n->parent == g->right)) { rotate_right(n->parent); n = n->right; } insert_case5(n); }


static void rotate_left(struct node *n) { struct node *c = n->right; struct node *p = n->parent; if (c->left != NULL) c->left->parent = n; n->right = c->left; n->parent = c; c->left = n; c->parent = p; if (p != NULL) { if (p->left == n) p->left = c; else p->right = c; } } static void rotate_right(struct node *n) { struct node *c = n->left; struct node *p = n->parent; if (c->right != NULL) c->right->parent = n; n->left = c->right; n->parent = c; c->right = n; c->parent = p; if (p != NULL) { if (p->right == n) p->right = c; else p->left = c; } }



위키에서 퍼옴