红黑树与C实现算法 - RedBlackTree.c
红黑树与C实现算法 - RedBlackTree.c
本文全部内容摘自互联网,作者根据需要做了修改和补充,最主要的是提供了对set的支持,并且给出完整的测试用例。
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。
红黑树的实现代码如下(red_black_tree.h,red_black_tree.c和测试文件rbtree_test.c):
- /******************************************************************************
- * red_black_tree.h *
- * Download From: *
- * http://www.cs.tau.ac.il/~efif/courses/Software1_Summer_03/code/rbtree/ *
- * Last Edited by: *
- * cheungmine *
- * 2010-8 *
- * Container class for a red-black tree: A binary tree that satisfies the *
- * following properties: *
- * 1. Each node has a color, which is either red or black. *
- * 2. A red node cannot have a red parent. *
- * 3. The number of black nodes from every path from the tree root to a leaf *
- * is the same for all tree leaves (it is called the 'black depth' of the *
- * tree). *
- * Due to propeties 2-3, the depth of a red-black tree containing n nodes *
- * is bounded by 2*log_2(n). *
- * *
- * The red_black_tree_t template requires two template parmeters: *
- * - The contained TYPE class represents the objects stored in the tree. *
- * It has to support the copy constructor and the assignment operator *
- * (operator=). *
- * *
- * - pfcbRBTreeCompFunc is a functor used to define the order of objects of *
- * class TYPE: *
- * This class has to support an operator() that recieves two objects from *
- * the TYPE class and returns a negative, zero or a positive integer, *
- * depending on the comparison result. *
- ******************************************************************************/
- #ifndef RED_BLACK_TREE_H
- #define RED_BLACK_TREE_H
- /*!
- * Define RBTREE_SUPPORTS_MULTI_OBJECTS for supporting mapset (multi-key-map)
- * if RBTREE_SUPPORTS_MULTI_OBJECTS defined, object must inherit from struct
- * rbtree_object_base. That means the first member of object must be a struct
- * pointer to next possible object if it has.
- *
- * #define RBTREE_SUPPORTS_MULTI_OBJECTS
- */
- #define RBTREE_SUPPORTS_MULTI_OBJECTS
- #ifdef RBTREE_SUPPORTS_MULTI_OBJECTS
- typedef struct _rbtree_object_base {
- struct _rbtree_object_base *__next_object;
- }rbtree_object_base;
- #endif
- /*! Color enumeration for nodes of red-black tree */
- typedef enum _red_black_color_enum
- {
- rbcRed,
- rbcBlack
- } red_black_color_enum;
- /*! Representation of a node in a red-black tree */
- typedef struct _red_black_node_t {
- void * object; /* the stored object user defined */
- red_black_color_enum color; /* the color of the node */
- struct _red_black_node_t * parent; /* points to the parent node */
- struct _red_black_node_t * right; /* points to the right child */
- struct _red_black_node_t * left; /* points to the left child */
- } red_black_node_t;
- /*! Callback function prototype for comparing objects */
- typedef int (pfcbRBTreeCompFunc)(void *object1, void *object2);
- /*! Callback function prototype for traverse objects */
- typedef void(pfcbRBTreeOperFunc)(void *object, void *param);
- /*! Construct of a red-black tree node
- * param object The object stored in the node
- * param color The color of the node
- */
- extern red_black_node_t * rbnode_construct(void * object, red_black_color_enum color);
- /*! Recursive destructor for the entire sub-tree */
- extern void rbnode_destruct(red_black_node_t * node);
- /*! Calculate the depth of the sub-tree spanned by the given node
- * param node The sub-tree root
- * return The sub-tree depth
- */
- extern int rbnode_depth(red_black_node_t * node);
- /*! Get the leftmost node in the sub-tree spanned by the given node
- * param node The sub-tree root
- * return The sub-tree minimum
- */
- extern red_black_node_t * rbnode_minimum(red_black_node_t * node);
- /*! Get the rightmost node in the sub-tree spanned by the given node
- * param node The sub-tree root
- * return The sub-tree maximum
- */
- extern red_black_node_t * rbnode_maximum(red_black_node_t * node);
- /*! Replace the object */
- extern void rbnode_replace(red_black_node_t * node, void * object);
- /*! Get the next node in the tree (according to the tree order)
- * param node The current node
- * return The successor node, or NULL if node is the tree maximum
- */
- extern red_black_node_t * rbnode_successor(red_black_node_t * node);
- /*! Get the previous node in the tree (according to the tree order)
- * param node The current node
- * return The predecessor node, or NULL if node is the tree minimum
- */
- extern red_black_node_t * rbnode_predecessor(red_black_node_t * node);
- /*! Duplicate the entire sub-tree rooted at the given node
- * param node The sub-tree root
- * return A pointer to the duplicated sub-tree root
- */
- extern red_black_node_t * rbnode_duplicate(red_black_node_t * node);
- /*! Traverse a red-black sub-tree left first
- * param node The sub-tree root
- * param op The operation to perform on each object in the sub-tree
- */
- extern void rbnode_traverse(red_black_node_t *node, pfcbRBTreeOperFunc *opFunc, void *param);
- /*! Traverse a red-black sub-tree right first
- */
- extern void rbnode_traverse_right(red_black_node_t *node, pfcbRBTreeOperFunc *opFunc, void*param);
- /*! Representation of a red-black tree */
- typedef struct _red_black_tree_t {
- red_black_node_t * root; /* pointer to the tree root */
- int iSize; /* number of objects stored */
- pfcbRBTreeCompFunc * comp; /* compare function */
- } red_black_tree_t;
- /*! Initialize a red-black tree with a comparision function
- * param tree The tree
- * param comp The comparision function
- */
- void rbtree_init(red_black_tree_t * tree, pfcbRBTreeCompFunc * comp);
- /*! Construct a red-black tree with a comparison object
- * param comp A pointer to the comparison object to be used by the tree
- * return The newly constructed tree
- */
- red_black_tree_t * rbtree_construct(pfcbRBTreeCompFunc * comp);
- /*! Clean a red-black tree [takes O(n) operations]
- * param tree The tree
- */
- extern void rbtree_clean(red_black_tree_t * tree);
- /*! Destruct a red-black tree
- * param tree The tree
- */
- extern void rbtree_destruct(red_black_tree_t * tree);
- /*! Get the size of the tree [takes O(1) operations]
- * param tree The tree
- * return The number of objects stored in the tree
- */
- extern int rbtree_size(red_black_tree_t * tree);
- /*! Get the depth of the tree [takes O(n) operations]
- * param tree The tree
- * return The length of the longest path from the root to a leaf node
- */
- extern int rbtree_depth(red_black_tree_t * tree);
- /*! Check whether the tree contains an object [takes O(log n) operations]
- * param tree The tree
- * param object The query object
- * return (true) if an equal object is found in the tree, otherwise (false)
- */
- extern int rbtree_contains(red_black_tree_t * tree, void * object);
- /*! Insert an object to the tree [takes O(log n) operations]
- * param tree The tree
- * param object The object to be inserted
- * return the inserted object node
- */
- extern red_black_node_t * rbtree_insert(red_black_tree_t * tree, void * object);
- /*! Insert an unique object to the tree */
- extern red_black_node_t * rbtree_insert_unique(red_black_tree_t * tree, void * object);
- /*! Insert a new object to the tree as the a successor of a given node
- * param tree The tree
- * return The new node
- */
- extern red_black_node_t * insert_successor_at(red_black_tree_t * tree,
- red_black_node_t * at_node,
- void * object);
- /*! Insert a new object to the tree as the a predecessor of a given node
- * param tree The tree
- * return The new node
- */
- extern red_black_node_t * insert_predecessor_at(red_black_tree_t * tree,
- red_black_node_t * at_node,
- void * object);
- /*! Remove an object from the tree [takes O(log n) operations]
- * param tree The tree
- * param object The object to be removed
- * pre The object should be contained in the tree
- */
- extern void rbtree_remove(red_black_tree_t * tree, void * object);
- /*! Get a handle to the tree minimum [takes O(log n) operations]
- * param tree The tree
- * return the minimal object in the tree, or a NULL if the tree is empty
- */
- extern red_black_node_t * rbtree_minimum(red_black_tree_t * tree);
- /*! Get a handle to the tree maximum [takes O(log n) operations]
- * param tree The tree
- * return the maximal object in the tree, or a NULL if the tree is empty
- */
- extern red_black_node_t * rbtree_maximum(red_black_tree_t * tree);
- /*! Get the next node in the tree (according to the tree order)
- * [takes O(log n) operations at worst-case, but only O(1) amortized]
- * param tree The tree
- * param node The current object
- * return The successor node, or a NULL, if we are at the tree maximum
- */
- extern red_black_node_t * rbtree_successor(red_black_tree_t * tree,
- red_black_node_t * node);
- /*! Get the previous node in the tree (according to the tree order)
- * [takes O(log n) operations at worst-case, but only O(1) amortized]
- * param tree The tree
- * param node The current object
- * return The predecessor node, or a NULL, if we are at the tree minimum
- */
- extern red_black_node_t * rbtree_predecessor(red_black_tree_t * tree,
- red_black_node_t * node);
- /*! Find a node that contains the given object
- * param tree The tree
- * param object The desired object
- * return A node that contains the given object, or NULL if no such object
- * is found in the tree
- */
- extern red_black_node_t * rbtree_find(red_black_tree_t * tree, void * object);
- /*! Remove the object stored in the given tree node
- * param tree The tree
- * param node The node storing the object to be removed from the tree
- */
- extern void rbtree_remove_at(red_black_tree_t * tree, red_black_node_t * node);
- /*! Left-rotate the sub-tree spanned by the given node
- * param tree The tree
- * param node The sub-tree root
- */
- extern void rbtree_rotate_left(red_black_tree_t * tree, red_black_node_t * node);
- /*! Right-rotate the sub-tree spanned by the given node
- * param tree The tree
- * param node The sub-tree root
- */
- extern void rbtree_rotate_right(red_black_tree_t * tree, red_black_node_t * node);
- /*!
- * Fix-up the red-black tree properties after an insertion operation
- * param tree The tree
- * param node The node that has just been inserted to the tree
- * pre The color of node must be red
- */
- extern void rbtree_insert_fixup(red_black_tree_t * tree, red_black_node_t * node);
- /*! Fix-up the red-black tree properties after a removal operation
- * param tree The tree
- * param node The child of the node that has just been removed from the tree
- */
- extern void rbtree_remove_fixup(red_black_tree_t * tree, red_black_node_t * node);
- /*! Traverse a red-black tree left first
- * param tree The tree
- * param op The operation to perform on every object of the tree (according to
- * the tree order)
- */
- extern void rbtree_traverse(red_black_tree_t * tree, pfcbRBTreeOperFunc * op, void *param);
- #define rbtree_traverse_left rbtree_traverse
- /*! Traverse a red-black tree right first */
- extern void rbtree_traverse_right(red_black_tree_t * tree, pfcbRBTreeOperFunc * op, void *param);
- #endif /* RED_BLACK_TREE_H */
----------------------------
- /******************************************************************************
- * red_black_tree.c *
- * Download From: *
- * http://www.cs.tau.ac.il/~efif/courses/Software1_Summer_03/code/rbtree/ *
- * Last Edited by: cheungmine *
- ******************************************************************************/
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include "red_black_tree.h"
- /*!
- * Operations on red_black_node_t struct
- */
- /* Construct a red-black tree node */
- red_black_node_t * rbnode_construct(void * object, red_black_color_enum color)
- {
- red_black_node_t * node = (red_black_node_t *) malloc(sizeof(red_black_node_t));
- if (!node) {
- fprintf(stderr, "Not enough memory!/n");
- return NULL;
- }
- node->object = object;
- node->color = color;
- node->parent = node->right = node->left = NULL;
- return node;
- }
- /* Destructor of a red-black tree node */
- void rbnode_destruct(red_black_node_t * node)
- {
- if (!node) return;
- rbnode_destruct(node->right);
- rbnode_destruct(node->left);
- free(node);
- }
- /* Calculate the depth of the subtree spanned by a given node */
- int rbnode_depth(red_black_node_t * node)
- {
- /* Recursively calculate the depth of the left and right sub-trees */
- int iRightDepth = (node->right) ? rbnode_depth(node->right) : 0;
- int iLeftDepth = (node->left) ? rbnode_depth(node->left) : 0;
- /* Return the maximal child depth + 1 (the current node) */
- return ((iRightDepth > iLeftDepth) ? (iRightDepth + 1) : (iLeftDepth + 1));
- }
- /* Return the leftmost leaf in the tree */
- red_black_node_t * rbnode_minimum(red_black_node_t * node)
- {
- while (node->left)
- node = node->left;
- return node;
- }
- /* Return the rightmost leaf in the tree */
- red_black_node_t * rbnode_maximum(red_black_node_t * node)
- {
- while (node->right)
- node = node->right;
- return node;
- }
- /* Replace the object */
- void rbnode_replace(red_black_node_t * node, void * object)
- {
- /* Make sure the replacement does not violate the tree order */
- /* Replace the object at node */
- node->object = object;
- }
- /* Get the next node in the tree (according to the tree order) */
- red_black_node_t * rbnode_successor(red_black_node_t * node)
- {
- red_black_node_t * succ_node;
- if (node->right) {
- /* If there is a right child, the successor is the minimal object in
- * the sub-tree spanned by this child.
- */
- succ_node = node->right;
- while (succ_node->left)
- succ_node = succ_node->left;
- }
- else {
- /* Otherwise, go up the tree until reaching the parent from the left
- * direction.
- */
- red_black_node_t * prev_node = node;
- succ_node = node->parent;
- while (succ_node && prev_node == succ_node->right) {
- prev_node = succ_node;
- succ_node = succ_node->parent;
- }
- }
- return (succ_node);
- }
- /* Get the previous node in the tree (according to the tree order) */
- red_black_node_t * rbnode_predecessor(red_black_node_t * node)
- {
- red_black_node_t * pred_node;
- if (node->left) {
- /* If there is a left child, the predecessor is the maximal object in
- * the sub-tree spanned by this child.
- */
- pred_node = node->left;
- while (pred_node->right)
- pred_node = pred_node->right;
- } else {
- /* Otherwise, go up the tree until reaching the parent from the right
- * direction.
- */
- red_black_node_t * prev_node = node;
- pred_node = node->parent;
- while (pred_node && prev_node == pred_node->left) {
- prev_node = pred_node;
- pred_node = pred_node->parent;
- }
- }
- return (pred_node);
- }
- /* Return a pointer to a duplication of the given node */
- red_black_node_t * rbnode_duplicate(red_black_node_t * node)
- {
- /* Create a node of the same color, containing the same object */
- red_black_node_t * dup_node = rbnode_construct(node->object, node->color);
- if (!dup_node) return NULL;
- /* Duplicate the children recursively */
- if (node->right) {
- dup_node->right = rbnode_duplicate (node->right);
- dup_node->right->parent = dup_node;
- } else {
- dup_node->right = NULL;
- }
- if (node->left) {
- dup_node->left = rbnode_duplicate(node->left);
- dup_node->left->parent = dup_node;
- } else {
- dup_node->left = NULL;
- }
- return dup_node; /* Return the duplicated node */
- }
- /* Traverse a red-black subtree */
- void rbnode_traverse(red_black_node_t * node, pfcbRBTreeOperFunc * opFunc, void* param)
- {
- if (!node) return;
- rbnode_traverse(node->left, opFunc, param);
- opFunc(node->object, param);
- rbnode_traverse(node->right, opFunc, param);
- }
- /* Right-first traverse a red-black subtree */
- void rbnode_traverse_right(red_black_node_t * node, pfcbRBTreeOperFunc * opFunc, void* param)
- {
- if (!node) return;
- rbnode_traverse_right(node->right, opFunc, param);
- opFunc(node->object, param);
- rbnode_traverse_right(node->left, opFunc, param);
- }
- /*
- * Operations on red_black_tree_t struct
- */
- /* Intialize a tree */
- void rbtree_init(red_black_tree_t * tree, pfcbRBTreeCompFunc * comp)
- {
- tree->comp = comp;
- tree->iSize = 0;
- tree->root = NULL;
- }
- /* Construct a tree given a comparison function */
- red_black_tree_t * rbtree_construct(pfcbRBTreeCompFunc * comp)
- {
- red_black_tree_t * tree = (red_black_tree_t *) malloc(sizeof(red_black_tree_t));
- if (!tree) {
- fprintf(stderr, "Not enough memory!/n");
- return NULL;
- }
- rbtree_init(tree, comp);
- return tree;
- }
- /* Remove all objects from a black-red tree */
- void rbtree_clean(red_black_tree_t * tree)
- {
- if (tree->root)
- rbnode_destruct(tree->root);
- tree->root = NULL;
- tree->iSize = 0;
- }
- /* Destruct a red-black tree */
- void rbtree_destruct(red_black_tree_t * tree)
- {
- rbtree_clean(tree);
- free(tree);
- }
- /* Returns the size of the tree */
- int rbtree_size(red_black_tree_t * tree)
- {
- return tree->iSize;
- }
- /* Returns the depth of the tree */
- int rbtree_depth(red_black_tree_t * tree)
- {
- if (!(tree->root))
- return 0;
- return rbnode_depth(tree->root);
- }
- /* Check whether the tree contains an object */
- int rbtree_contains(red_black_tree_t * tree, void * object)
- {
- return (rbtree_find(tree, object) != NULL);
- }
- /* Insert an object to the tree */
- red_black_node_t * rbtree_insert(red_black_tree_t * tree, void * object)
- {
- int cmp;
- red_black_node_t * cur_node;
- red_black_node_t * new_node = NULL;
- if (!(tree->root)) {
- /* Assign a new root node. Notice that the root is always black */
- new_node = rbnode_construct(object, rbcBlack);
- if (!new_node) return NULL;
- tree->root = new_node;
- tree->iSize = 1;
- return new_node;
- }
- /* Find a place for the new object, and insert it as a red leaf */
- cur_node = tree->root;
- while (cur_node) {
- cmp = (*(tree->comp))(object, cur_node->object);
- #ifdef RBTREE_SUPPORTS_MULTI_OBJECTS
- if (cmp==0) {
- if (cur_node->object != object)
- ((rbtree_object_base*)cur_node->object)->__next_object = (rbtree_object_base*)object;
- return cur_node;
- }
- #endif
- /* Compare inserted object with the object stored in the current node */
- if (cmp > 0) {
- if (!(cur_node->left)) {
- /* Insert the new leaf as the left child of the current node */
- new_node = rbnode_construct(object, rbcRed);
- if (!new_node) return NULL;
- cur_node->left = new_node;
- new_node->parent = cur_node;
- cur_node = NULL; /* terminate the while loop */
- } else {
- cur_node = cur_node->left; /* Go to the left sub-tree */
- }
- } else {
- if (!(cur_node->right)) {
- /* Insert the new leaf as the right child of the current node */
- new_node = rbnode_construct(object, rbcRed);
- if (!new_node) return NULL;
- cur_node->right = new_node;
- new_node->parent = cur_node;
- cur_node = NULL; /* terminate the while loop */
- } else {
- cur_node = cur_node->right; /* Go to the right sub-tree */
- }
- }
- }
- /* Mark that a new node was added */
- tree->iSize++;
- /* Fix up the tree properties */
- rbtree_insert_fixup(tree, new_node);
- return new_node;
- }
- /* Insert an unique object to the tree */
- red_black_node_t * rbtree_insert_unique(red_black_tree_t * tree, void * object)
- {
- int cmp;
- red_black_node_t * cur_node;
- red_black_node_t * new_node = NULL;
- if (!(tree->root)) {
- /* Assign a new root node. Notice that the root is always black */
- new_node = rbnode_construct(object, rbcBlack);
- if (!new_node) return NULL;
- tree->root = new_node;
- tree->iSize = 1;
- return new_node;
- }
- /* Find a place for the new object, and insert it as a red leaf */
- cur_node = tree->root;
- while (cur_node) {
- cmp = (*(tree->comp))(object, cur_node->object);
- if (cmp==0) {
- /* there already has an object with the same id as object to be inserted */
- return cur_node;
- }
- /* Compare inserted object with the object stored in the current node */
- if (cmp > 0) {
- if (!(cur_node->left)) {
- /* Insert the new leaf as the left child of the current node */
- new_node = rbnode_construct(object, rbcRed);
- if (!new_node)
- return NULL;
- cur_node->left = new_node;
- new_node->parent = cur_node;
- cur_node = NULL; /* terminate the while loop */
- } else {
- cur_node = cur_node->left; /* Go to the left sub-tree */
- }
- } else {
- if (!(cur_node->right)) {
- /* Insert the new leaf as the right child of the current node */
- new_node = rbnode_construct(object, rbcRed);
- if (!new_node)
- return NULL;
- cur_node->right = new_node;
- new_node->parent = cur_node;
- cur_node = NULL; /* terminate the while loop */
- } else {
- cur_node = cur_node->right; /* Go to the right sub-tree */
- }
- }
- }
- /* Mark that a new node was added */
- tree->iSize++;
- /* Fix up the tree properties */
- rbtree_insert_fixup(tree, new_node);
- return new_node;
- }
- /* Insert a new object to the tree as the a successor of a given node */
- red_black_node_t * insert_successor_at(red_black_tree_t * tree,
- red_black_node_t * at_node, void * object)
- {
- red_black_node_t * parent;
- red_black_node_t * new_node;
- if (!(tree->root)) {
- /* Assign a new root node. Notice that the root is always black */
- new_node = rbnode_construct(object, rbcBlack);
- if (!new_node) return NULL;
- tree->root = new_node;
- tree->iSize = 1;
- return new_node;
- }
- /* Insert the new object as a red leaf, being the successor of node */
- new_node = rbnode_construct(object, rbcRed);
- if (!new_node) return NULL;
- if (!at_node) {
- /* The new node should become the tree minimum: Place is as the left
- * child of the current minimal leaf.
- */
- parent = rbnode_minimum(tree->root);
- parent->left = new_node;
- } else {
- /* Make sure the insertion does not violate the tree order */
- /* In case given node has no right child, place the new node as its
- * right child. Otherwise, place it at the leftmost position at the
- * sub-tree rooted at its right side.
- */
- if (!at_node->right) {
- parent = at_node;
- parent->right = new_node;
- } else {
- parent = rbnode_minimum(at_node->right);
- parent->left = new_node;
- }
- }
- new_node->parent = parent;
- /* Mark that a new node was added */
- tree->iSize++;
- /* Fix up the tree properties */
- rbtree_insert_fixup(tree, new_node);
- return new_node;
- }
- /* Insert a new object to the tree as the a predecessor of a given node */
- red_black_node_t * insert_predecessor_at(red_black_tree_t * tree,
- red_black_node_t * at_node, void * object)
- {
- red_black_node_t * parent;
- red_black_node_t * new_node;
- if (!(tree->root)) {
- /* Assign a new root node. Notice that the root is always black */
- new_node = rbnode_construct(object, rbcBlack);
- if (!new_node) return NULL;
- tree->root = new_node;
- tree->iSize = 1;
- return new_node;
- }
- /* Insert the new object as a red leaf, being the predecessor of at_node */
- new_node = rbnode_construct(object, rbcRed);
- if (!new_node) return NULL;
- if (!at_node) {
- /* The new node should become the tree maximum: Place is as the right
- * child of the current maximal leaf.
- */
- parent = rbnode_maximum(tree->root);
- parent->right = new_node;
- } else {
- /* Make sure the insertion does not violate the tree order */
- /* In case given node has no left child, place the new node as its
- * left child. Otherwise, place it at the rightmost position at the
- * sub-tree rooted at its left side.
- */
- if (!(at_node->left)) {
- parent = at_node;
- parent->left = new_node;
- } else {
- parent = rbnode_maximum (at_node->left);
- parent->right = new_node;
- }
- }
- new_node->parent = parent;
- /* Mark that a new node was added */
- tree->iSize++;
- /* Fix up the tree properties */
- rbtree_insert_fixup(tree, new_node);
- return new_node;
- }
- /* Remove an object from the tree */
- void rbtree_remove(red_black_tree_t * tree, void * object)
- {
- red_black_node_t * node = rbtree_find(tree, object); /* find the node */
- rbtree_remove_at(tree, node); /* remove the node */
- }
- /* Remove the object pointed by the given node. */
- void rbtree_remove_at(red_black_tree_t * tree, red_black_node_t * node)
- {
- red_black_node_t * child = NULL;
- /* In case of deleting the single object stored in the tree, free the root,
- * thus emptying the tree.
- */
- if (tree->iSize == 1) {
- rbnode_destruct(tree->root);
- tree->root = NULL;
- tree->iSize = 0;
- return;
- }
- /* Remove the given node from the tree */
- if (node->left && node->right) {
- /* If the node we want to remove has two children, find its successor,
- * which is the leftmost child in its right sub-tree and has at most
- * one child (it may have a right child).
- */
- red_black_node_t * succ_node = rbnode_minimum(node->right);
- /* Now physically swap node and its successor. Notice this may temporarily
- * violate the tree properties, but we are going to remove node anyway.
- * This way we have moved node to a position were it is more convinient
- * to delete it.
- */
- int immediate_succ = (node->right == succ_node);
- red_black_node_t * succ_parent = succ_node->parent;
- red_black_node_t * succ_left = succ_node->left;
- red_black_node_t * succ_right = succ_node->right;
- red_black_color_enum succ_color = succ_node->color;
- succ_node->parent = node->parent;
- succ_node->left = node->left;
- succ_node->right = immediate_succ ? node : node->right;
- succ_node->color = node->color;
- node->parent = immediate_succ ? succ_node : succ_parent;
- node->left = succ_left;
- node->right = succ_right;
- node->color = succ_color;
- if (!immediate_succ) {
- if (succ_node == node->parent->left)
- node->parent->left = node;
- else
- node->parent->right = node;
- }
- if (node->left)
- node->left->parent = node;
- if (node->right)
- node->right->parent = node;
- if (succ_node->parent) {
- if (node == succ_node->parent->left)
- succ_node->parent->left = succ_node;
- else
- succ_node->parent->right = succ_node;
- } else {
- tree->root = succ_node;
- }
- if (succ_node->left)
- succ_node->left->parent = succ_node;
- if (succ_node->right)
- succ_node->right->parent = succ_node;
- }
- /* At this stage, the node we are going to remove has at most one child */
- child = (node->left) ? node->left : node->right;
- /* Splice out the node to be removed, by linking its parent straight to the
- * removed node's single child.
- */
- if (child)
- child->parent = node->parent;
- if (!(node->parent)) {
- /* If we are deleting the root, make the child the new tree node */
- tree->root = child;
- } else {
- /* Link the removed node parent to its child */
- if (node == node->parent->left) {
- node->parent->left = child;
- } else {
- node->parent->right = child;
- }
- }
- /* Fix-up the red-black properties that may have been damaged: If we have
- * just removed a black node, the black-depth property is no longer valid.
- */
- if (node->color == rbcBlack && child)
- rbtree_remove_fixup(tree, child);
- /* Delete the un-necessary node (we nullify both its children because the
- * node's destructor is recursive).
- */
- node->left = NULL;
- node->right = NULL;
- free(node);
- /* Descrease the number of objects in the tree */
- tree->iSize--;
- }
- /* Get the tree minimum */
- red_black_node_t * rbtree_minimum(red_black_tree_t * tree)
- {
- if (!(tree->root))
- return NULL;
- /* Return the leftmost leaf in the tree */
- return rbnode_minimum(tree->root);
- }
- /* Get the tree maximum */
- red_black_node_t * rbtree_maximum(red_black_tree_t * tree)
- {
- if (!(tree->root))
- return NULL;
- /* Return the rightmost leaf in the tree */
- return rbnode_maximum(tree->root);
- }
- /* Return a pointer to the node containing the given object */
- red_black_node_t * rbtree_find(red_black_tree_t * tree, void * object)
- {
- red_black_node_t * cur_node = tree->root;
- int comp_result;
- while (cur_node) {
- /* In case of equality, we can return the current node. */
- if ((comp_result = (*(tree->comp))(object, cur_node->object)) == 0)
- return cur_node;
- /* Go down to the left or right child. */
- cur_node = (comp_result > 0) ? cur_node->left : cur_node->right;
- }
- /* If we reached here, the object is not found in the tree */
- return NULL;
- }
- /* Left-rotate the sub-tree spanned by the given node:
- *
- * | RoateRight(y) |
- * y --------------> x
- * / / / / .
- * x T3 RoatateLeft(x) T1 y .
- * / / <-------------- / / .
- * T1 T2 T2 T3
- */
- void rbtree_rotate_left(red_black_tree_t * tree, red_black_node_t * x_node)
- {
- /* Get the right child of the node */
- red_black_node_t * y_node = x_node->right;
- /* Change its left subtree (T2) to x's right subtree */
- x_node->right = y_node->left;
- /* Link T2 to its new parent x */
- if (y_node->left != NULL)
- y_node->left->parent = x_node;
- /* Assign x's parent to be y's parent */
- y_node->parent = x_node->parent;
- if (!(x_node->parent)) {
- /* Make y the new tree root */
- tree->root = y_node;
- } else {
- /* Assign a pointer to y from x's parent */
- if (x_node == x_node->parent->left) {
- x_node->parent->left = y_node;
- } else {
- x_node->parent->right = y_node;
- }
- }
- /* Assign x to be y's left child */
- y_node->left = x_node;
- x_node->parent = y_node;
- }
- /* Right-rotate the sub-tree spanned by the given node */
- void rbtree_rotate_right(red_black_tree_t * tree, red_black_node_t * y_node)
- {
- /* Get the left child of the node */
- red_black_node_t * x_node = y_node->left;
- /* Change its right subtree (T2) to y's left subtree */
- y_node->left = x_node->right;
- /* Link T2 to its new parent y */
- if (x_node->right != NULL)
- x_node->right->parent = y_node;
- /* Assign y's parent to be x's parent */
- x_node->parent = y_node->parent;
- if (!(y_node->parent)) {
- /* Make x the new tree root */
- tree->root = x_node;
- } else {
- /* Assign a pointer to x from y's parent */
- if (y_node == y_node->parent->left) {
- y_node->parent->left = x_node;
- } else {
- y_node->parent->right = x_node;
- }
- }
- /* Assign y to be x's right child */
- x_node->right = y_node;
- y_node->parent = x_node;
- }
- /* Fix-up the tree so it maintains the red-black properties after insertion */
- void rbtree_insert_fixup(red_black_tree_t * tree, red_black_node_t * node)
- {
- /* Fix the red-black propreties: we may have inserted a red leaf as the
- * child of a red parent - so we have to fix the coloring of the parent
- * recursively.
- */
- red_black_node_t * curr_node = node;
- red_black_node_t * grandparent;
- red_black_node_t *uncle;
- assert(node && node->color == rbcRed);
- while (curr_node != tree->root && curr_node->parent->color == rbcRed) {
- /* Get a pointer to the current node's grandparent (notice the root is
- * always black, so the red parent must have a parent).
- */
- grandparent = curr_node->parent->parent;
- if (curr_node->parent == grandparent->left) {
- /* If the red parent is a left child, the uncle is the right child of
- * the grandparent.
- */
- uncle = grandparent->right;
- if (uncle && uncle->color == rbcRed) {
- /* If both parent and uncle are red, color them black and color the
- * grandparent red.
- * In case of a NULL uncle, we treat it as a black node.
- */
- curr_node->parent->color = rbcBlack;
- uncle->color = rbcBlack;
- grandparent->color = rbcRed;
- /* Move to the grandparent */
- curr_node = grandparent;
- } else {
- /* Make sure the current node is a right child. If not, left-rotate
- * the parent's sub-tree so the parent becomes the right child of the
- * current node (see _rotate_left).
- */
- if (curr_node == curr_node->parent->right) {
- curr_node = curr_node->parent;
- rbtree_rotate_left(tree, curr_node);
- }
- /* Color the parent black and the grandparent red */
- curr_node->parent->color = rbcBlack;
- grandparent->color = rbcRed;
- /* Right-rotate the grandparent's sub-tree */
- rbtree_rotate_right(tree, grandparent);
- }
- } else {
- /* If the red parent is a right child, the uncle is the left child of
- * the grandparent.
- */
- uncle = grandparent->left;
- if (uncle && uncle->color == rbcRed) {
- /* If both parent and uncle are red, color them black and color the
- * grandparent red.
- * In case of a NULL uncle, we treat it as a black node.
- */
- curr_node->parent->color = rbcBlack;
- uncle->color = rbcBlack;
- grandparent->color = rbcRed;
- /* Move to the grandparent */
- curr_node = grandparent;
- } else {
- /* Make sure the current node is a left child. If not, right-rotate
- * the parent's sub-tree so the parent becomes the left child of the
- * current node.
- */
- if (curr_node == curr_node->parent->left) {
- curr_node = curr_node->parent;
- rbtree_rotate_right(tree, curr_node);
- }
- /* Color the parent black and the grandparent red */
- curr_node->parent->color = rbcBlack;
- grandparent->color = rbcRed;
- /* Left-rotate the grandparent's sub-tree */
- rbtree_rotate_left(tree, grandparent);
- }
- }
- }
- /* Make sure that the root is black */
- tree->root->color = rbcBlack;
- }
- void rbtree_remove_fixup(red_black_tree_t * tree, red_black_node_t * node)
- {
- red_black_node_t * curr_node = node;
- red_black_node_t * sibling;
- while (curr_node != tree->root && curr_node->color == rbcBlack) {
- /* Get a pointer to the current node's sibling (notice that the node's
- * parent must exist, since the node is not the root).
- */
- if (curr_node == curr_node->parent->left) {
- /* If the current node is a left child, its sibling is the right
- * child of the parent.
- */
- sibling = curr_node->parent->right;
- /* Check the sibling's color. Notice that NULL nodes are treated
- * as if they are colored black.
- */
- if (sibling && sibling->color == rbcRed) {
- /* In case the sibling is red, color it black and rotate.
- * Then color the parent red (and the grandparent is now black).
- */
- sibling->color = rbcBlack;
- curr_node->parent->color = rbcRed;
- rbtree_rotate_left(tree, curr_node->parent);
- sibling = curr_node->parent->right;
- }
- if (sibling &&
- (!(sibling->left) || sibling->left->color == rbcBlack) &&
- (!(sibling->right) || sibling->right->color == rbcBlack))
- {
- /* If the sibling has two black children, color it red */
- sibling->color = rbcRed;
- if (curr_node->parent->color == rbcRed) {
- /* If the parent is red, we can safely color it black and terminate
- * the fix-up process.
- */
- curr_node->parent->color = rbcBlack;
- curr_node = tree->root; /* In order to stop the while loop */
- } else {
- /* The black depth of the entire sub-tree rooted at the parent is
- * now too small - fix it up recursively.
- */
- curr_node = curr_node->parent;
- }
- } else {
- if (!sibling) {
- /* Take special care of the case of a NULL sibling */
- if (curr_node->parent->color == rbcRed) {
- curr_node->parent->color = rbcBlack;
- curr_node = tree->root; /* In order to stop the while loop */
- } else {
- curr_node = curr_node->parent;
- }
- } else {
- /* In this case, at least one of the sibling's children is red.
- * It is therfore obvious that the sibling itself is black.
- */
- if (sibling->right && sibling->right->color == rbcRed) {
- /* If the right child of the sibling is red, color it black and
- * rotate around the current parent.
- */
- sibling->right->color = rbcBlack;
- rbtree_rotate_left(tree, curr_node->parent);
- } else {
- /* If the left child of the sibling is red, rotate around the
- * sibling, then rotate around the new sibling of our current
- * node.
- */
- rbtree_rotate_right(tree, sibling);
- sibling = curr_node->parent->right;
- rbtree_rotate_left(tree, sibling);
- }
- /* It is now safe to color the parent black and to terminate the
- * fix-up process.
- */
- if (curr_node->parent->parent)
- curr_node->parent->parent->color = curr_node->parent->color;
- curr_node->parent->color = rbcBlack;
- curr_node = tree->root; /* In order to stop the while loop */
- }
- }
- } else {
- /* If the current node is a right child, its sibling is the left
- * child of the parent.
- */
- sibling = curr_node->parent->left;
- /* Check the sibling's color. Notice that NULL nodes are treated
- * as if they are colored black.
- */
- if (sibling && sibling->color == rbcRed) {
- /* In case the sibling is red, color it black and rotate.
- * Then color the parent red (and the grandparent is now black).
- */
- sibling->color = rbcBlack;
- curr_node->parent->color = rbcRed;
- rbtree_rotate_right(tree, curr_node->parent);
- sibling = curr_node->parent->left;
- }
- if (sibling &&
- (!(sibling->left) || sibling->left->color == rbcBlack) &&
- (!(sibling->right) || sibling->right->color == rbcBlack))
- {
- /* If the sibling has two black children, color it red */
- sibling->color = rbcRed;
- if (curr_node->parent->color == rbcRed) {
- /* If the parent is red, we can safely color it black and terminate
- * the fix-up process.
- */
- curr_node->parent->color = rbcBlack;
- curr_node = tree->root; /* In order to stop the while loop */
- } else {
- /* The black depth of the entire sub-tree rooted at the parent is
- * now too small - fix it up recursively.
- */
- curr_node = curr_node->parent;
- }
- } else {
- if (!sibling) {
- /* Take special care of the case of a NULL sibling */
- if (curr_node->parent->color == rbcRed) {
- curr_node->parent->color = rbcBlack;
- curr_node = tree->root; /* In order to stop the while loop */
- } else {
- curr_node = curr_node->parent;
- }
- } else {
- /* In this case, at least one of the sibling's children is red.
- * It is therfore obvious that the sibling itself is black.
- */
- if (sibling->left && sibling->left->color == rbcRed) {
- /* If the left child of the sibling is red, color it black and
- * rotate around the current parent
- */
- sibling->left->color = rbcBlack;
- rbtree_rotate_right(tree, curr_node->parent);
- } else {
- /* If the right child of the sibling is red, rotate around the
- * sibling, then rotate around the new sibling of our current
- * node
- */
- rbtree_rotate_left(tree, sibling);
- sibling = curr_node->parent->left;
- rbtree_rotate_right(tree, sibling);
- }
- /* It is now safe to color the parent black and to terminate the
- * fix-up process.
- */
- if (curr_node->parent->parent)
- curr_node->parent->parent->color = curr_node->parent->color;
- curr_node->parent->color = rbcBlack;
- curr_node = tree->root; /* In order to stop the while loop */
- }
- }
- }
- }
- /* The root can always be colored black */
- curr_node->color = rbcBlack;
- }
- /* Traverse a red-black tree */
- void rbtree_traverse(red_black_tree_t * tree, pfcbRBTreeOperFunc * op, void *param)
- {
- rbnode_traverse(tree->root, op, param);
- }
- /* Right-first traverse a red-black tree */
- void rbtree_traverse_right(red_black_tree_t * tree, pfcbRBTreeOperFunc * op, void *param)
- {
- rbnode_traverse_right(tree->root, op, param);
- }
---------------------------
- //
- // rbtree_test.c
- // by cheungmine
- //
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- // RBTREE_SUPPORTS_MULTI_OBJECTS 在下面的文件中被定义,如果不想支持多图,注释掉它
- #include "red_black_tree.h"
- /*!
- */
- int cmp_int(int a, int b)
- {
- return (a > b) ? -1 : ((a == b) ? 0 : 1);
- }
- /*!
- */
- void my_print(int value)
- {
- printf("%d ", value);
- }
- #if !defined(RBTREE_SUPPORTS_MULTI_OBJECTS)
- void test_rbtree_insert_repeat()
- {
- int i, n;
- red_black_tree_t tree;
- red_black_node_t *node, *node2;
- n = 20;
- rbtree_init(&tree, (pfcbRBTreeCompFunc*) cmp_int);
- for (i=0; i<n; i++){
- rbtree_insert(&tree, (void*) i);
- }
- node = rbtree_find(&tree, (void*) 5);
- assert(node);
- node2 = rbtree_insert(&tree, (void*) 5);
- assert(node2);
- assert(node!=node2);
- node = rbtree_find(&tree, (void*) 10);
- assert(node);
- node2 = rbtree_insert(&tree, (void*) 10);
- assert(node2);
- assert(node!=node2);
- printf("n = %d, d = %d/n", n, rbtree_depth(&tree));
- rbtree_traverse(&tree, (pfcbRBTreeOperFunc*) my_print);
- printf("/n");
- rbtree_traverse_right(&tree, (pfcbRBTreeOperFunc*) my_print);
- printf("/n");
- rbtree_clean(&tree);
- }
- #endif
- void test_rbtree_insert_unique()
- {
- int i, n;
- red_black_tree_t tree;
- red_black_node_t *node, *node2;
- n = 20;
- rbtree_init(&tree, (pfcbRBTreeCompFunc*) cmp_int);
- for (i=0; i<n; i++){
- rbtree_insert_unique(&tree, (void*) i);
- }
- node = rbtree_find(&tree, (void*) 5);
- assert(node);
- node2 = rbtree_insert_unique(&tree, (void*) 5);
- assert(node2);
- assert(node==node2);
- node = rbtree_find(&tree, (void*) 10);
- assert(node);
- node2 = rbtree_insert_unique(&tree, (void*) 10);
- assert(node2);
- assert(node==node2);
- printf("n = %d, d = %d/n", n, rbtree_depth(&tree));
- rbtree_traverse(&tree, (pfcbRBTreeOperFunc*) my_print, 0);
- printf("/n");
- rbtree_traverse_right(&tree, (pfcbRBTreeOperFunc*) my_print, 0);
- printf("/n");
- rbtree_clean(&tree);
- }
- #ifdef RBTREE_SUPPORTS_MULTI_OBJECTS
- typedef struct _MYOBJECT
- {
- struct _MYOBJECT *__next_object;
- int data;
- }MYOBJECT;
- int cmp_int_multimap(MYOBJECT *a, MYOBJECT *b)
- {
- return (a->data > b->data) ? -1 : ((a->data == b->data) ? 0 : 1);
- }
- /*!
- */
- void my_print_multimap(MYOBJECT *obj)
- {
- while (obj) {
- printf("%d ", obj->data);
- obj = obj->__next_object;
- }
- }
- void test_rbtree_insert_multimap()
- {
- int i, n;
- MYOBJECT *obj;
- MYOBJECT **objects;
- red_black_tree_t tree;
- red_black_node_t *node;
- n = 20;
- rbtree_init(&tree, (pfcbRBTreeCompFunc*) cmp_int_multimap);
- objects = (MYOBJECT**) calloc(n, sizeof(MYOBJECT*));
- for (i=0; i<n; i++){
- obj = (MYOBJECT*) malloc(sizeof(MYOBJECT));
- objects[i] = obj;
- obj->__next_object = 0; // MUST be NULL
- obj->data = i;
- rbtree_insert(&tree, (void*) obj);
- }
- rbtree_insert(&tree, (void*) objects[5]);
- obj = (MYOBJECT*) malloc(sizeof(MYOBJECT));
- obj->__next_object = 0; // MUST be NULL
- obj->data = 5;
- rbtree_insert(&tree, (void*) obj);
- printf("n = %d, d = %d/n", n, rbtree_depth(&tree));
- printf("(");
- node = rbtree_find(&tree, (void*) objects[5]);
- if (node){
- MYOBJECT *obj = node->object;
- while (obj) {
- printf("%d ", obj->data);
- obj = obj->__next_object;
- }
- }
- printf(")/n");
- rbtree_traverse(&tree, (pfcbRBTreeOperFunc*) my_print_multimap, 0);
- printf("/n");
- rbtree_traverse_right(&tree, (pfcbRBTreeOperFunc*) my_print_multimap, 0);
- printf("/n");
- rbtree_clean(&tree);
- for (i=0; i<n; i++){
- free(objects[i]);
- }
- free(objects);
- free(obj);
- }
- #endif // RBTREE_SUPPORTS_MULTI_OBJECTS
- int main(int argc, char * argv[])
- {
- #if !defined(RBTREE_SUPPORTS_MULTI_OBJECTS)
- test_rbtree_insert_repeat();
- #endif
- test_rbtree_insert_unique();
- test_rbtree_insert_multimap();
- return 0;
- }
任何人使用此代码必须遵守原作者的协议。
评论暂时关闭