红黑树数据结构
#ifndef __RED_BLACK_TREE_H#define __RED_BLACK_TREE_H#define RED 1#define BLACK 0typedef struct Red_Black_Node{ int id; int color; int key; struct Red_Black_Node* left; struct Red_Black_Node* right; struct Red_Black_Node* parent;}Red_Black_Node;typedef struct Red_Black_Tree{ int count; Red_Black_Node* root; Red_Black_Node* nil;}Red_Black_Tree;// nodeRed_Black_Node* red_black_node_create( );void red_black_node_free(Red_Black_Node* node);void red_black_node_copy(Red_Black_Node* dst, Red_Black_Node* src);// treeRed_Black_Tree* red_black_tree_create( );void _red_black_tree_free(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_free(Red_Black_Tree* tree);void _red_black_tree_print(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_print(Red_Black_Tree* tree);void red_black_tree_insert(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_insert_fixup(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_transplant(Red_Black_Tree* tree, Red_Black_Node* u, Red_Black_Node* v);void red_black_tree_delete(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_delete_fixup(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_left_rotate(Red_Black_Tree* tree, Red_Black_Node* node);void red_black_tree_right_rotate(Red_Black_Tree* tree, Red_Black_Node* node);Red_Black_Node* red_black_subtree_maximum(Red_Black_Tree* tree, Red_Black_Node* subtree);Red_Black_Node* red_black_subtree_minimum(Red_Black_Tree* tree, Red_Black_Node* subtree);Red_Black_Node* red_black_tree_search(Red_Black_Tree* tree, int key);#endif 实现代码
#include#include #include "red_black_tree.h"// nodeRed_Black_Node* red_black_node_create( ){ Red_Black_Node* node = (Red_Black_Node*)malloc(sizeof(Red_Black_Node)); return node;}void red_black_node_free(Red_Black_Node* node){ free(node);}void red_black_node_copy(Red_Black_Node* dst, Red_Black_Node* src){ dst->color = src->color; dst->key = src->key; dst->left = src->left; dst->right = src->right; dst->parent = src->parent;}// treeRed_Black_Tree* red_black_tree_create( ){ Red_Black_Tree* tree = (Red_Black_Tree*)malloc(sizeof(Red_Black_Tree)); tree->nil = red_black_node_create( ); tree->nil->id = -1; tree->nil->color = BLACK; tree->nil->key = 0; tree->nil->left = NULL; tree->nil->right = NULL; tree->nil->parent = NULL; tree->root = tree->nil; tree->count = 0; return tree;}void red_black_tree_print(Red_Black_Tree* tree){ _red_black_tree_print(tree, tree->root); printf("\n");}void _red_black_tree_print(Red_Black_Tree* tree, Red_Black_Node* node){ if (node != tree->nil) { _red_black_tree_print(tree, node->left); printf("[id: %d, color: %s, key: %d, parent: %d, left: %d, right: %d] ", node->id, node->color == BLACK ? "BLACK" : "RED", node->key, node->parent->id, node->left->id, node->right->id); _red_black_tree_print(tree, node->right); }}void _red_black_tree_free(Red_Black_Tree* tree, Red_Black_Node* node){ if (node != tree->nil) { _red_black_tree_free(tree, node->left); _red_black_tree_free(tree, node->right); red_black_node_free(node); }}void red_black_tree_free(Red_Black_Tree* tree){ _red_black_tree_free(tree, tree->root); red_black_node_free(tree->nil); free(tree);}void red_black_tree_left_rotate(Red_Black_Tree* tree, Red_Black_Node* x){ Red_Black_Node* y = x->right; x->right = y->left; if (y->left != tree->nil) { y->left->parent = x; } y->parent = x->parent; if (x->parent == tree->nil) { tree->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else if (x == x->parent->right) { x->parent->right = y; } y->left = x; x->parent = y;}void red_black_tree_right_rotate(Red_Black_Tree* tree, Red_Black_Node* x){ Red_Black_Node* y = x->left; x->left = y->right; if (y->right != tree->nil) { y->right->parent = x; } y->parent = x->parent; if (x->parent == tree->nil) { tree->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else if (x == x->parent->right) { x->parent->right = y; } y->right = x; x->parent = y;}void red_black_tree_insert(Red_Black_Tree* tree, Red_Black_Node* node){ // copy node to z Red_Black_Node* z = red_black_node_create( ); red_black_node_copy(z, node); z->id = tree->count++; Red_Black_Node* y = tree->nil; Red_Black_Node* x = tree->root; while (x != tree->nil) { y = x; if (z->key < x->key) { x = x->left; } else { x = x->right; } } z->parent = y; if (y == tree->nil) { tree->root = z; } else if (z->key < y->key) { y->left = z; } else if (z->key >= y->key) { y->right = z; } z->left = tree->nil; z->right = tree->nil; z->color = RED; red_black_tree_insert_fixup(tree, z);}void red_black_tree_insert_fixup(Red_Black_Tree* tree, Red_Black_Node* z){ Red_Black_Node* y = NULL; while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { /* z's parent is the left child of z's parent's parent*/ y = z->parent->parent->right; if (y->color == RED) { //case 1: y.color is RED z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { // the color of z's uncle is BLACK // case 2 if (z == z->parent->right) { z = z->parent; red_black_tree_left_rotate(tree, z); } // case 3 z->parent->color = BLACK; z->parent->parent->color = RED; red_black_tree_right_rotate(tree, z->parent->parent); } } else if (z->parent == z->parent->parent->right) { /* z's parent is the right child of z's parent's parent*/ y = z->parent->parent->left; //case 1 if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { // case 2 if (z == z->parent->left) { z = z->parent; red_black_tree_right_rotate(tree, z); } // go to case 3 z->parent->color = BLACK; z->parent->parent->color = RED; red_black_tree_left_rotate(tree, z->parent->parent); } } } tree->root->color = BLACK; }Red_Black_Node* red_black_subtree_maximum(Red_Black_Tree* tree, Red_Black_Node* subtree){ while (subtree->right != tree->nil) { subtree = subtree->right; } return subtree;}Red_Black_Node* red_black_subtree_minimum(Red_Black_Tree* tree, Red_Black_Node* subtree){ while (subtree->left != tree->nil) { subtree = subtree->left; } return subtree;}void red_black_tree_transplant(Red_Black_Tree* tree, Red_Black_Node* u, Red_Black_Node* v){ if (u->parent == tree->nil) { tree->root = v; } else if (u == u->parent->left) { u->parent->left = v; } else { u->parent->right = v; } v->parent = u->parent;}void red_black_tree_delete(Red_Black_Tree* tree, Red_Black_Node* z){ Red_Black_Node* y = z; Red_Black_Node* x = NULL; int y_original_color = y->color; if (z->left == tree->nil) { x = z->right; red_black_tree_transplant(tree, z, z->right); } else if (z->right == tree->nil) { x = z->left; red_black_tree_transplant(tree, z, z->left); } else { y = red_black_subtree_minimum(tree, z->right); y_original_color = y->color; x = y->right; if (y->parent == z) { x->parent = y; } else { red_black_tree_transplant(tree, y, y->right); y->right = z->right; y->right->parent = y; } red_black_tree_transplant(tree, z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } if (y_original_color == BLACK) { red_black_tree_delete_fixup(tree, x); } /* free node z */ red_black_node_free(z);}void red_black_tree_delete_fixup(Red_Black_Tree* tree, Red_Black_Node* x){ Red_Black_Node* w = NULL; while (x != tree->root && x->color == BLACK) { // left child if (x == x->parent->left) { w = x->parent->right; if (w->color == RED) { // case 1 w->color = BLACK; x->parent->color = RED; red_black_tree_left_rotate(tree, x->parent); } // go to case 2, 3 or 4 if (w->left->color == BLACK && w->right->color == BLACK) { // case 2 w->color = RED; x = x->parent; } else { // case 3 or 4 if (w->right->color == BLACK) { // case 3 w->left->color = BLACK; w->color = RED; red_black_tree_right_rotate(tree, w); } w->color = w->parent->color; w->parent->color = BLACK; w->right->color = BLACK; red_black_tree_left_rotate(tree, x->parent); x = tree->root; } } else if (x == x->parent->right) { // right child w = x->parent->left; if (w->color == RED) { // case 1 w->color = BLACK; x->parent->color = RED; red_black_tree_right_rotate(tree, x->parent); } // case 2, 3 or 4 if (w->left->color == BLACK && w->right->color == BLACK) { // case 2 w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { // case 3 w->right->color = BLACK; w->color = RED; red_black_tree_left_rotate(tree, w); w = x->parent->left; } // case 4 w->color = w->parent->color; x->parent->color = BLACK; w->left->color = BLACK; red_black_tree_right_rotate(tree, x->parent); x = tree->root; } } } x->color = BLACK;}Red_Black_Node* red_black_tree_search(Red_Black_Tree* tree, int key){ Red_Black_Node* node = tree->root; while (node != tree->nil && key != node->key) { if (key < node->key) { node = node->left; } else { node = node->right; } } return node;}
#include#include #include "red_black_tree.h"int main(int argc, char** argv){ Red_Black_Tree* tree = red_black_tree_create( ); Red_Black_Node* node = red_black_node_create( ); Red_Black_Node* result = NULL; int i = 0; for (i = 0; i < 4; i++) { node->key = i; red_black_tree_insert(tree, node); } red_black_tree_print(tree); result = red_black_tree_search(tree, 1); printf("id: %d\n", result->id); red_black_tree_delete(tree, result); red_black_tree_print(tree); red_black_node_free(node); red_black_tree_free(tree); return 0;}