-
-
Save wdpm/91c2c453614cabb19862dac3f299b63a to your computer and use it in GitHub Desktop.
simple rbtree source code
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| int BLACK = 0; | |
| int RED = 1; | |
| struct node | |
| { | |
| struct node *left; | |
| struct node *right; | |
| struct node *parent; | |
| int value; | |
| int color; // 0 is black, 1 is red | |
| }; | |
| struct rbtree | |
| { | |
| struct node *root; | |
| }; | |
| void print(struct rbtree *t); | |
| struct rbtree *create(); | |
| void insert_node(struct rbtree *t, int value); | |
| void delete_node(struct rbtree *t, int value); | |
| static void replace_node(struct rbtree *t, struct node *o, struct node *n); | |
| static void insert_case1(struct rbtree *t, struct node *n); | |
| static void insert_case2(struct rbtree *t, struct node *n); | |
| static void insert_case3(struct rbtree *t, struct node *n); | |
| static void insert_case4(struct rbtree *t, struct node *n); | |
| static void insert_case5(struct rbtree *t, struct node *n); | |
| static void delete_case1(struct rbtree *t, struct node *n); | |
| static void delete_case2(struct rbtree *t, struct node *n); | |
| static void delete_case3(struct rbtree *t, struct node *n); | |
| static void delete_case4(struct rbtree *t, struct node *n); | |
| static void delete_case5(struct rbtree *t, struct node *n); | |
| static void delete_case6(struct rbtree *t, struct node *n); | |
| /* | |
| helper tools | |
| */ | |
| void _print_node(struct node *n) | |
| { | |
| if (n->parent) | |
| { | |
| printf(" parent=%d ", n->parent->value); | |
| } | |
| else | |
| { | |
| printf(" parent=nil "); | |
| } | |
| if (n->left) | |
| { | |
| printf(" left=%d ", n->left->value); | |
| } | |
| else | |
| { | |
| printf(" left=nil "); | |
| } | |
| if (n->right) | |
| { | |
| printf(" right=%d ", n->right->value); | |
| } | |
| else | |
| { | |
| printf(" right=nil "); | |
| } | |
| } | |
| void _print(struct node *n) | |
| { | |
| if (!n) | |
| { | |
| return; | |
| } | |
| if (n->color == RED) | |
| { | |
| printf("%d(red)", n->value); | |
| _print_node(n); | |
| } | |
| else | |
| { | |
| printf("%d(black)", n->value); | |
| _print_node(n); | |
| } | |
| printf("\n"); | |
| _print(n->left); | |
| _print(n->right); | |
| } | |
| void print(struct rbtree *t) | |
| { | |
| struct node *r = t->root; | |
| printf("root is %d\n", r->value); | |
| _print(r); | |
| } | |
| struct node *grandparent(struct node *n) | |
| { | |
| return n->parent->parent; | |
| } | |
| struct node *sibling(struct node *n) | |
| { | |
| if (n == n->parent->left) | |
| return n->parent->right; | |
| else | |
| return n->parent->left; | |
| } | |
| struct node *uncle(struct node *n) | |
| { | |
| return sibling(n->parent); | |
| } | |
| int node_color(struct node *n) | |
| { | |
| return n == NULL ? BLACK : n->color; | |
| } | |
| struct rbtree *create() | |
| { | |
| struct rbtree *t = (struct rbtree *)malloc(sizeof(struct rbtree)); | |
| t->root = NULL; | |
| return t; | |
| } | |
| struct node *new_node(int value, int color, struct node *left, struct node *right) | |
| { | |
| struct node *n = (struct node *)malloc(sizeof(struct node)); | |
| n->color = color; | |
| n->left = left; | |
| n->right = right; | |
| n->value = value; | |
| if (left != NULL) | |
| { | |
| left->parent = n; | |
| } | |
| if (right != NULL) | |
| { | |
| right->parent = n; | |
| } | |
| // 新节点的父节点默认NULL | |
| n->parent = NULL; | |
| return n; | |
| } | |
| struct node *search(struct rbtree *t, int value) | |
| { | |
| struct node *n = t->root; | |
| while (n != NULL) | |
| { | |
| if (value == n->value) | |
| { | |
| return n; | |
| } | |
| else if (value < n->value) | |
| { | |
| n = n->left; | |
| } | |
| else if (value > n->value) | |
| { | |
| n = n->right; | |
| } | |
| } | |
| return NULL; | |
| } | |
| void replace_node(struct rbtree *t, struct node *o, struct node *n) | |
| { | |
| // 将旧节点[o] <---> [o->parent] 的双向链接改为：[n] <--> [o->parent] 的双向链接 | |
| if (o->parent == NULL) | |
| { | |
| t->root = n; | |
| } | |
| else | |
| { | |
| if (o == o->parent->left) | |
| o->parent->left = n; | |
| else | |
| o->parent->right = n; | |
| } | |
| if (n != NULL) | |
| { | |
| n->parent = o->parent; | |
| } | |
| } | |
| void rotate_left(struct rbtree *t, struct node *n) | |
| { | |
| struct node *r = n->right; | |
| replace_node(t, n, r); | |
| n->right = r->left; | |
| if (r->left != NULL) | |
| { | |
| r->left->parent = n; | |
| } | |
| r->left = n; | |
| n->parent = r; | |
| } | |
| void rotate_right(struct rbtree *t, struct node *n) | |
| { | |
| struct node *l = n->left; | |
| replace_node(t, n, l); | |
| n->left = l->right; | |
| if (l->right != NULL) | |
| { | |
| l->right->parent = n; | |
| } | |
| l->right = n; | |
| n->parent = l; | |
| } | |
| /* | |
| insert function start | |
| */ | |
| void insert_case1(struct rbtree *t, struct node *n) | |
| { | |
| // 新节点N位于树的根上，没有父节点。此时直接将根设置为黑。 | |
| if (n->parent == NULL) | |
| n->color = BLACK; | |
| else | |
| // 否则继续 | |
| insert_case2(t, n); | |
| } | |
| void insert_case2(struct rbtree *t, struct node *n) | |
| { | |
| // 新节点的父节点P是黑色，性质4没有失效（新节点是红色的）。因为新节点为红，不会影响黑高平衡。 | |
| if (node_color(n->parent) == BLACK) | |
| return; /* Tree is still valid */ | |
| else | |
| // 否则继续，这里的情况我们可以预料：父节点P为红，新节点N约定初始化是红色 | |
| insert_case3(t, n); | |
| } | |
| void insert_case3(struct rbtree *t, struct node *n) | |
| { | |
| // 这里：新节点的父节点为红色，所以它有祖父节点（否则双红矛盾）；因为如果父节点是根节点，那父节点就应当是黑色。 | |
| // 所以新节点必然有一个叔父节点，但是它可能是叶子节点，也可能是正常节点。 | |
| // 这里，先处理叔父节点是红色节点的情形。 | |
| // 说明：对于这个情形，此时插入节点N做为P的左子节点或右子节点都是等价的。 | |
| if (node_color(uncle(n)) == RED) | |
| { | |
| // 将父节点P和叔父节点U置黑，祖父节点置红 | |
| n->parent->color = BLACK; | |
| uncle(n)->color = BLACK; | |
| grandparent(n)->color = RED; | |
| // 考虑到祖父节点可能为根节点，而根节点不能为红。因此需要在祖父节点进行初始递归处理。 | |
| insert_case1(t, grandparent(n)); | |
| } | |
| else | |
| { | |
| // 否则，考虑其他可能情形：叔父节点为黑节点。 | |
| insert_case4(t, n); | |
| } | |
| } | |
| void insert_case4(struct rbtree *t, struct node *n) | |
| { | |
| // 在这个情形下，假定父节点P是其祖父G的左子节点。如果它是右子节点，情形4和情形5中的左和右应当对调。 | |
| if (n == n->parent->right && n->parent == grandparent(n)->left) | |
| { | |
| rotate_left(t, n->parent); | |
| n = n->left; // 旋转后，将N的左子树赋值给N，为了后续能够递归N的左子树。注意后续P、N互换角色 | |
| } | |
| else if (n == n->parent->left && n->parent == grandparent(n)->right) | |
| { | |
| rotate_right(t, n->parent); | |
| n = n->right; // 旋转后，将N的右子树赋值给N，为了后续能够递归N的右子树。注意后续P、N互换角色 | |
| } | |
| // 此时n是示意图的P | |
| insert_case5(t, n); | |
| } | |
| void insert_case5(struct rbtree *t, struct node *n) | |
| { | |
| // 情形描述，经过insert_case4的转化： | |
| // 父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点， | |
| // 而父节点P又是其父节点G的左子节点 | |
| // 此时触发双红矛盾。 | |
| n->parent->color = BLACK; // P变黑 | |
| grandparent(n)->color = RED; // G变红 | |
| // 适当旋转，破除双红矛盾。 | |
| if (n == n->parent->left && n->parent == grandparent(n)->left) | |
| { | |
| rotate_right(t, grandparent(n)); | |
| } | |
| else | |
| { | |
| rotate_left(t, grandparent(n)); | |
| } | |
| } | |
| void insert_node(struct rbtree *t, int value) | |
| { | |
| struct node *n = new_node(value, RED, NULL, NULL); | |
| // 处理BST逻辑，寻找合适的插入位置，执行插入 | |
| if (t->root == NULL) | |
| { | |
| t->root = n; | |
| } | |
| else | |
| { | |
| struct node *r = t->root; | |
| while (1) | |
| { | |
| if (value == r->value) | |
| { | |
| // value is root value | |
| return; | |
| } | |
| else if (value > r->value) | |
| { | |
| if (r->right == NULL) | |
| { | |
| r->right = n; | |
| break; | |
| } | |
| else | |
| { | |
| r = r->right; | |
| } | |
| } | |
| else if (value < r->value) | |
| { | |
| // 这里的n都是new出来的，这个判断 if (n->left == NULL) 不需要 | |
| if (n->left == NULL) | |
| { | |
| if (r->left == NULL) | |
| { | |
| r->left = n; | |
| break; | |
| } | |
| else | |
| { | |
| r = r->left; | |
| } | |
| } | |
| } | |
| } | |
| n->parent = r; | |
| } | |
| // 处理红黑树的invariant（不变约束） | |
| insert_case1(t, n); | |
| } | |
| /* | |
| insert function end | |
| */ | |
| // 出于方便，删除逻辑的代码将假定空叶子被用不是NULL的实际节点对象来表示 | |
| void delete_case1(struct rbtree *t, struct node *n) | |
| { | |
| // N是根节点。 | |
| // 相当于从所有路径去除一个黑色节点，这是最简单的情形。 | |
| if (n->parent == NULL) | |
| return; | |
| else | |
| // 此时要删除的N不是根节点 | |
| delete_case2(t, n); | |
| } | |
| // 首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N（在新的位置上）， | |
| // 称呼它的兄弟（它父亲的另一个儿子）为S。示意图中，我们还是使用P称呼N的父亲，SL称呼S的左儿子，SR称呼S的右儿子 | |
| // 下面所做的一切平衡操作，都是基于P下面的路径黑色节点少1来进行的。 | |
| void delete_case2(struct rbtree *t, struct node *n) | |
| { | |
| if (node_color(sibling(n)) == RED) | |
| { | |
| n->parent->color = RED; | |
| sibling(n)->color = BLACK; | |
| if (n == n->parent->left) | |
| rotate_left(t, n->parent); | |
| else | |
| rotate_right(t, n->parent); | |
| } | |
| // 尽管所有路径上黑色节点的数目没有改变， | |
| // 但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子）， | |
| // 此时为何还需要往下面调整呢？ | |
| // **[N是删除了黑色节点后替换上来的子节点]** | |
| delete_case3(t, n); | |
| } | |
| void delete_case3(struct rbtree *t, struct node *n) | |
| { | |
| if (node_color(n->parent) == BLACK && | |
| node_color(sibling(n)) == BLACK && | |
| node_color(sibling(n)->left) == BLACK && | |
| node_color(sibling(n)->right) == BLACK) | |
| { | |
| sibling(n)->color = RED; | |
| // wiki delete case 3: | |
| // Now all paths in the subtree rooted by P have the same number of black nodes, | |
| // but one fewer than the paths that do not pass through P, so requirement 4 may still be violated. | |
| delete_case1(t, n->parent); | |
| } | |
| else | |
| delete_case4(t, n); | |
| } | |
| void delete_case4(struct rbtree *t, struct node *n) | |
| { | |
| if (node_color(n->parent) == RED && | |
| node_color(sibling(n)) == BLACK && | |
| node_color(sibling(n)->left) == BLACK && | |
| node_color(sibling(n)->right) == BLACK) | |
| { | |
| // S和S的儿子都是黑色，但是N的父亲是红色。 | |
| // 在这种情形下，我们简单的交换N的兄弟和父亲的颜色。 | |
| // 这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点 | |
| sibling(n)->color = RED; | |
| n->parent->color = BLACK; | |
| } | |
| else | |
| delete_case5(t, n); | |
| } | |
| void delete_case5(struct rbtree *t, struct node *n) | |
| { | |
| // /* this if statement is trivial, | |
| // due to Case 2(even though Case two changed the sibling to a sibling's child, | |
| // the sibling's child can't be red, since no red parent can have a red child). */ | |
| // the following statements just force the red to be on the left of the left of the parent, | |
| // or right of the right, so case six will rotate correctly. | |
| if (node_color(sibling(n)) == BLACK) | |
| { | |
| if (n == n->parent->left && | |
| node_color(sibling(n)->left) == RED && | |
| node_color(sibling(n)->right) == BLACK) | |
| { | |
| sibling(n)->color = RED; | |
| sibling(n)->left->color = BLACK; | |
| rotate_right(t, sibling(n)); | |
| } | |
| else if (n == n->parent->right && | |
| node_color(sibling(n)->right) == RED && | |
| node_color(sibling(n)->left) == BLACK) | |
| { | |
| sibling(n)->color = RED; | |
| sibling(n)->right->color = BLACK; | |
| rotate_left(t, sibling(n)); | |
| } | |
| } | |
| delete_case6(t, n); | |
| } | |
| void delete_case6(struct rbtree *t, struct node *n) | |
| { | |
| sibling(n)->color = node_color(n->parent); | |
| n->parent->color = BLACK; | |
| if (n == n->parent->left) | |
| { | |
| sibling(n)->right->color = BLACK; | |
| rotate_left(t, n->parent); | |
| } | |
| else | |
| { | |
| sibling(n)->left->color = BLACK; | |
| rotate_right(t, n->parent); | |
| } | |
| } | |
| struct node *maximum_node(struct node *n) | |
| { | |
| while (n->right != NULL) | |
| { | |
| n = n->right; | |
| } | |
| return n; | |
| } | |
| void delete_node(struct rbtree *t, int value) | |
| { | |
| struct node *child; | |
| struct node *n = search(t, value); | |
| // not found | |
| if (n == NULL) | |
| { | |
| return; | |
| } | |
| // found | |
| // 要被删除的节点只有三种情况：1.含有两个非叶子节点（内部节点）；2含有一个非叶子节点；3.含有两个叶子节点 | |
| // 讨论：如果需要删除的节点有两个儿子，问题可以被转化成删除另一个只有一个儿子的节点的问题 | |
| if (n->left != NULL && n->right != NULL) | |
| { | |
| // 取N的左子树的最大值作为前驱结点。 | |
| // !注意思考：替换者的特性：必定有少于两个非叶子的儿子。否则，它不可能成为替换者。 | |
| struct node *pred = maximum_node(n->left); | |
| // 复制pred的值到N中，N的颜色并没有改变。此时树依旧满足红黑树的约束。 | |
| n->value = pred->value; | |
| // 将找到的前驱结点赋值给N，后续再来处理N， | |
| n = pred; | |
| } | |
| // 到了这里，前置条件：此时N最多只能含有一个非null的子节点。可能为一个，也可能为0个。 | |
| child = n->right == NULL ? n->left : n->right; | |
| // 思考： | |
| // 1.如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。 | |
| // 所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4 | |
| // 2.另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5， | |
| // 但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5 | |
| // 3.需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候。最为复杂。 | |
| // Think 2&3 | |
| if (node_color(n) == BLACK) | |
| { | |
| // 为何需要将儿子的颜色传给父亲?如果按照wiki，这里child应该是黑，需要验证？ | |
| n->color = node_color(child); | |
| delete_case1(t, n); | |
| } | |
| // Think 1 | |
| // 要删除的结点和它的child进行交换。此时可以交换是因为，N只会有一个实质的儿子节点。因此独生子是完全能继承父亲的地位的。 | |
| replace_node(t, n, child); | |
| // N父亲为空，孩子不为空。说明此时child为新根。child应该置黑 | |
| if (n->parent == NULL && child != NULL) | |
| { | |
| child->color = BLACK; | |
| } | |
| // 最后删除N | |
| free(n); | |
| } | |
| int main() | |
| { | |
| struct rbtree *t = create(); | |
| insert_node(t, 1); | |
| insert_node(t, 2); | |
| insert_node(t, 3); | |
| insert_node(t, 4); | |
| insert_node(t, 5); | |
| insert_node(t, 0); | |
| insert_node(t, -1); | |
| insert_node(t, 10); | |
| insert_node(t, 11); | |
| insert_node(t, 12); | |
| delete_node(t, 10); | |
| print(t); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment