123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568 |
- /*!
- Temelia - Red Black Tree implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/red_black_tree.h"
- #include "include/stack.h"
- #include <stdlib.h>
- extern stack_t iterating_handlers;
- extern stack_t compare_stack;
- /*
- * Properties of red black trees :
- * 1. A node is either red or black.
- * 2. The root is black.
- * 3. All external nodes are black, even when the parent is black
- * (The external nodes are the null value children.)
- * 4. Both children of every red node are black.
- * 5. Every simple path from a node to a descendant leaf contains
- * the same number of black nodes, either counting or not counting
- * the null black nodes.
- */
- struct _red_black_tree_node_t
- {
- /*! user's key */
- void *key;
- unsigned int color;
- };
- #define GET_RED_BLACK_MEMBER(x, member) (((red_black_tree_node_t)(x))->member)
- /*!
- * Encapsulates user's key into a red black node.
- */
- static red_black_tree_node_t _red_black_tree_node_new(void *key,
- unsigned int color);
- static void _red_black_tree_node_delete(red_black_tree_node_t tree_node);
- static void _red_black_tree_internal_handling(void *x, void *context);
- static void _red_black_tree_internal_printing_level(void *x, int level,
- void *contextcontext);
- static int _red_black_tree_internal_compare(void *x, void *y, void *context);
- void _red_black_tree_set_color(red_black_tree_t red_black_tree,
- unsigned int color);
- red_black_tree_t red_black_tree_new(void *key)
- {
- return _binary_tree_new(_red_black_tree_node_new(key, RED));
- }
- void red_black_tree_delete_node(red_black_tree_t red_black_tree)
- {
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);
- _red_black_tree_node_delete(_binary_tree_get_key(red_black_tree));
- _delete(red_black_tree);
- }
- void red_black_tree_delete(red_black_tree_t red_black_tree)
- {
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);
- red_black_tree_delete(_binary_tree_get_left_child(red_black_tree));
- red_black_tree_delete(_binary_tree_get_right_child(red_black_tree));
- red_black_tree_delete_node(red_black_tree);
- }
- int red_black_tree_compare_trees(red_black_tree_t red_black_tree1,
- red_black_tree_t red_black_tree2, int compare(void *x, void *y,
- void *context), void *context)
- {
- return _binary_tree_compare_trees(red_black_tree1, red_black_tree2,
- compare, context);
- }
- int red_black_tree_is_empty(red_black_tree_t red_black_tree)
- {
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, -1);
- return (_binary_tree_get_parent(red_black_tree) == NULL)
- && (_binary_tree_get_left_child(red_black_tree) == NULL)
- && (_binary_tree_get_right_child(red_black_tree) == NULL)
- && (GET_RED_BLACK_MEMBER(_binary_tree_get_key(red_black_tree), key)
- == NULL);
- }
- int red_black_tree_is_leaf(red_black_tree_t red_black_tree)
- {
- return _binary_tree_leaf(red_black_tree);
- }
- int red_black_tree_get_size(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_size(red_black_tree);
- }
- red_black_tree_t red_black_tree_get_root(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_root(red_black_tree);
- }
- void *red_black_tree_get_key(red_black_tree_t red_black_tree)
- {
- red_black_tree_node_t node;
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, NULL);
- node = _binary_tree_get_key(red_black_tree);
- return node->key;
- }
- unsigned int red_black_tree_get_color(red_black_tree_t red_black_tree)
- {
- red_black_tree_node_t node;
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, BLACK);
- node = _binary_tree_get_key(red_black_tree);
- return node->color;
- }
- red_black_tree_t red_black_tree_get_parent(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_parent(red_black_tree);
- }
- red_black_tree_t red_black_tree_get_left_child(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_left_child(red_black_tree);
- }
- red_black_tree_t red_black_tree_get_right_child(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_right_child(red_black_tree);
- }
- int red_black_tree_get_height(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_height(red_black_tree);
- }
- int red_black_tree_get_depth(red_black_tree_t red_black_tree)
- {
- return _binary_tree_get_depth(red_black_tree);
- }
- red_black_tree_t red_black_tree_search(red_black_tree_t _red_black_tree,
- void *key, int compare(void *x, void *y, void *context), void *context)
- {
- red_black_tree_node_t search_node = _red_black_tree_node_new(key, -1);
- red_black_tree_t aux;
- stack_push(compare_stack, compare);
- aux = _binary_search_tree_search(_red_black_tree, search_node,
- _red_black_tree_internal_compare, context);
- _red_black_tree_node_delete(search_node);
- stack_pop(compare_stack);
- return aux;
- }
- red_black_tree_t red_black_tree_insert(red_black_tree_t *red_black_tree,
- void *key, int compare(void *x, void *y, void *context), void *context,
- int adjust_root)
- {
- red_black_tree_t add = NULL, parent = NULL, aux = NULL, var = NULL, save =
- NULL;
- red_black_tree_node_t add_node = NULL;
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, INVALID_INPUT, NULL);
- stack_push(compare_stack, compare);
- add_node = _red_black_tree_node_new(key, RED);
- aux = add = _binary_search_tree_insert(*red_black_tree, add_node,
- _red_black_tree_internal_compare, context);
- // key already exists - no adding in performed
- if (aux == NULL)
- {
- _red_black_tree_node_delete(add_node);
- return NULL;
- }
- while (add != *red_black_tree && red_black_tree_get_color(add) == RED)
- {
- parent = _binary_tree_get_parent(add);
- if (parent == NULL || add == NULL)
- break;
- if (add == _binary_tree_get_left_child(parent))
- {
- var = _binary_tree_get_right_child(parent);
- if (red_black_tree_get_color(var) == RED)
- {
- _red_black_tree_set_color(add, BLACK);
- _red_black_tree_set_color(var, BLACK);
- _red_black_tree_set_color(parent, RED);
- save = parent;
- add = _binary_tree_get_parent(parent);
- }
- else
- {
- if (save == _binary_tree_get_right_child(add))
- {
- _self_balanced_binary_search_tree_rotate_left(add);
- add = save;
- }
- _red_black_tree_set_color(add, BLACK);
- _red_black_tree_set_color(parent, RED);
- _self_balanced_binary_search_tree_rotate_right(parent);
- }
- }
- else
- {
- var = _binary_tree_get_left_child(parent);
- if (red_black_tree_get_color(var) == RED)
- {
- _red_black_tree_set_color(add, BLACK);
- _red_black_tree_set_color(var, BLACK);
- _red_black_tree_set_color(parent, RED);
- save = parent;
- add = _binary_tree_get_parent(parent);
- }
- else
- {
- if (save == _binary_tree_get_left_child(add))
- {
- _self_balanced_binary_search_tree_rotate_right(add);
- add = save;
- }
- _red_black_tree_set_color(add, BLACK);
- _red_black_tree_set_color(parent, RED);
- _self_balanced_binary_search_tree_rotate_left(parent);
- }
- }
- }
- while (adjust_root && _binary_tree_get_parent(*red_black_tree))
- (*red_black_tree) = _binary_tree_get_parent(*red_black_tree);
- stack_pop(compare_stack);
- return aux;
- }
- int red_black_tree_remove(red_black_tree_t *red_black_tree_, void *key,
- int compare(void *x, void *y, void *context), void *context,
- int adjust_root)
- {
- red_black_tree_t replaced = NULL, my_deleted = NULL, brother = NULL;
- red_black_tree_node_t key_encapsulated = NULL;
- int _end = 0;
- if (compare(key, GET_RED_BLACK_MEMBER((*red_black_tree_)->key, key),
- context) == 0 && (*red_black_tree_)->parent == NULL
- && (*red_black_tree_)->left == NULL && (*red_black_tree_)->right
- == NULL)
- {
- red_black_tree_delete(*red_black_tree_);
- *red_black_tree_ = NULL;
- return 0;
- }
- stack_push(compare_stack, compare);
- // Remove the node as in a binary search tree and then start tree balancing.
- key_encapsulated = _red_black_tree_node_new(key, 0);
- replaced = _binary_search_tree_remove(red_black_tree_, key_encapsulated,
- _red_black_tree_internal_compare, context, &my_deleted);
- _red_black_tree_node_delete(key_encapsulated);
- _ASSERT(my_deleted, ==, NULL, ELEMENT_NOT_FOUND, 0);
- red_black_tree_delete_node(my_deleted);
- /*
- * If the replaced node is red, then the red-black property is preserved
- * so no root adjusting is required.
- */
- if (red_black_tree_get_color(replaced) == BLACK && !_end)
- {
- if (replaced == _binary_tree_get_left_child(_binary_tree_get_parent(
- replaced)))
- {
- brother = _binary_tree_get_right_child(_binary_tree_get_parent(
- replaced));
- if (brother && red_black_tree_get_color(brother) == RED)
- {
- _red_black_tree_set_color(brother, BLACK);
- _red_black_tree_set_color(_binary_tree_get_parent(replaced),
- RED);
- _self_balanced_binary_search_tree_rotate_left(
- _binary_tree_get_parent(replaced));
- }
- if (red_black_tree_get_color(_binary_tree_get_left_child(brother))
- == BLACK && red_black_tree_get_color(
- _binary_tree_get_right_child(brother)) == BLACK)
- {
- _red_black_tree_set_color(brother, RED);
- replaced = _binary_tree_get_parent(replaced);
- }
- else
- {
- if (red_black_tree_get_color(_binary_tree_get_right_child(
- brother)) == BLACK)
- {
- _red_black_tree_set_color(_binary_tree_get_left_child(
- brother), BLACK);
- _red_black_tree_set_color(brother, RED);
- _self_balanced_binary_search_tree_rotate_right(brother);
- brother = _binary_tree_get_right_child(
- _binary_tree_get_parent(replaced));
- }
- _red_black_tree_set_color(brother, red_black_tree_get_color(
- _binary_tree_get_parent(replaced)));
- _red_black_tree_set_color(
- _binary_tree_get_right_child(brother), BLACK);
- _red_black_tree_set_color(_binary_tree_get_parent(replaced),
- BLACK);
- _self_balanced_binary_search_tree_rotate_left(
- _binary_tree_get_parent(replaced));
- _end = 1;
- }
- }
- else
- {
- brother = _binary_tree_get_left_child(_binary_tree_get_parent(
- replaced));
- if (brother && red_black_tree_get_color(brother) == RED)
- {
- _red_black_tree_set_color(brother, BLACK);
- _red_black_tree_set_color(_binary_tree_get_parent(replaced),
- RED);
- _self_balanced_binary_search_tree_rotate_right(
- _binary_tree_get_parent(replaced));
- }
- if (red_black_tree_get_color(_binary_tree_get_right_child(brother))
- == BLACK && red_black_tree_get_color(
- _binary_tree_get_left_child(brother)) == BLACK)
- {
- _red_black_tree_set_color(brother, RED);
- replaced = _binary_tree_get_parent(replaced);
- }
- else
- {
- if (red_black_tree_get_color(_binary_tree_get_left_child(
- brother)) == BLACK)
- {
- _red_black_tree_set_color(_binary_tree_get_right_child(
- brother), BLACK);
- _red_black_tree_set_color(brother, RED);
- _self_balanced_binary_search_tree_rotate_left(brother);
- brother = _binary_tree_get_left_child(
- _binary_tree_get_parent(replaced));
- }
- _red_black_tree_set_color(brother, red_black_tree_get_color(
- _binary_tree_get_parent(replaced)));
- _red_black_tree_set_color(
- _binary_tree_get_right_child(brother), BLACK);
- _red_black_tree_set_color(_binary_tree_get_parent(replaced),
- BLACK);
- _self_balanced_binary_search_tree_rotate_right(
- _binary_tree_get_parent(replaced));
- _end = 1;
- }
- }
- }
- while (adjust_root && _binary_tree_get_parent(*red_black_tree_))
- (*red_black_tree_) = _binary_tree_get_parent(*red_black_tree_);
- stack_pop(compare_stack);
- return 1;
- }
- red_black_tree_t red_black_tree_get_min(red_black_tree_t red_black_tree)
- {
- return _binary_search_tree_get_min(red_black_tree);
- }
- red_black_tree_t red_black_tree_get_max(red_black_tree_t red_black_tree)
- {
- return _binary_search_tree_get_max(red_black_tree);
- }
- void red_black_tree_preorder(red_black_tree_t red_black_tree, void key_handler(
- void *x, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_preorder(red_black_tree, _red_black_tree_internal_handling,
- context);
- stack_pop(iterating_handlers);
- }
- void red_black_tree_inorder(red_black_tree_t red_black_tree, void key_handler(
- void *x, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_inorder(red_black_tree, _red_black_tree_internal_handling,
- context);
- stack_pop(iterating_handlers);
- }
- void red_black_tree_reverse_inorder(red_black_tree_t red_black_tree,
- void key_handler(void *x, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_reverse_inorder(red_black_tree,
- _red_black_tree_internal_handling, context);
- stack_pop(iterating_handlers);
- }
- void red_black_tree_postorder(red_black_tree_t red_black_tree,
- void key_handler(void *x, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_postorder(red_black_tree, _red_black_tree_internal_handling,
- context);
- stack_pop(iterating_handlers);
- }
- void red_black_tree_level_order(red_black_tree_t red_black_tree,
- void key_handler(void *x, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_level_order(red_black_tree, _red_black_tree_internal_handling,
- context);
- stack_pop(iterating_handlers);
- }
- void red_black_tree_show_indented(red_black_tree_t red_black_tree,
- void key_handler(void *x, int level, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_show_indented(red_black_tree,
- _red_black_tree_internal_printing_level, context, 0);
- stack_pop(iterating_handlers);
- }
- static red_black_tree_node_t _red_black_tree_node_new(void *key,
- unsigned int color)
- {
- red_black_tree_node_t red_black_tree;
- red_black_tree = (struct _red_black_tree_node_t *) _new(
- sizeof(struct _red_black_tree_node_t));
- red_black_tree->key = key;
- red_black_tree->color = color;
- return red_black_tree;
- }
- static void _red_black_tree_node_delete(
- red_black_tree_node_t red_black_tree_node)
- {
- _ASSERT(red_black_tree_node, ==, NULL, NULL_POINTER,);
- _delete(red_black_tree_node);
- }
- static void _red_black_tree_internal_handling(void *x, void *context)
- {
- void (*handler)(void *x, void *context);
- handler = stack_top(iterating_handlers);
- _ASSERT(handler, ==, NULL, NULL_POINTER,);
- handler(GET_RED_BLACK_MEMBER(x, key), context);
- }
- static void _red_black_tree_internal_printing_level(void *x, int level,
- void *context)
- {
- void (*user_printing_function_level)(void *, int, void *);
- user_printing_function_level = stack_top(iterating_handlers);
- _ASSERT(user_printing_function_level, ==, NULL, NULL_POINTER,);
- user_printing_function_level(GET_RED_BLACK_MEMBER(x, key), level, context);
- }
- static int _red_black_tree_internal_compare(void *x, void *y, void *context)
- {
- /*
- * This is the callback function and can compare red_black_tree_t tree nodes.
- *
- * For comparing key from nodes, I save the user comparison function in a global pointer.
- */
- int (*user_comparison_function)(void *, void *, void *);
- user_comparison_function = stack_top(compare_stack);
- _ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);
- return user_comparison_function(GET_RED_BLACK_MEMBER(x, key),
- GET_RED_BLACK_MEMBER(y, key), context);
- }
- void _red_black_tree_set_color(red_black_tree_t red_black_tree,
- unsigned int color)
- {
- red_black_tree_node_t node;
- _ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);
- node = _binary_tree_get_key(red_black_tree);
- node->color = color;
- }
|