123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738 |
- /*!
- Temelia - Binary tree <common part> 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/binary_tree_common.h"
- #include "include/queue.h"
- #include <stdlib.h>
- static binary_search_tree_t __binary_search_tree_remove(
- binary_search_tree_t *bst, binary_search_tree_t deleted);
- /*
- * Forward declaration
- *
- * common.c: line 166
- */
- extern int temelia_inited;
- void temelia_init();
- _binary_tree_t _binary_tree_new(void *key)
- {
- _binary_tree_t tree;
- if (!temelia_inited)
- temelia_init();
- tree = (struct _bt_node_t *) _new(sizeof(struct _bt_node_t));
- /*
- * Encapsulates the key into a node with NULL children.
- */
- tree->key = key;
- tree->parent = tree->left = tree->right = NULL;
- return tree;
- }
- void _binary_tree_delete_node(_binary_tree_node_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER,);
- /*
- * Sets the internal pointers to NULL.
- */
- node->key = node->parent = node->left = node->right = NULL;
- _delete(node);
- }
- void _binary_tree_delete(_binary_tree_t tree)
- {
- _ASSERT(tree, ==, NULL, NULL_POINTER,);
- /*
- * delete(node)
- * delete the left child
- * delete the right child
- * delete the current node
- */
- _binary_tree_delete(tree->left);
- _binary_tree_delete(tree->right);
- _binary_tree_delete_node(tree);
- }
- int _binary_tree_compare_trees(_binary_tree_t bt1, _binary_tree_t bt2,
- int compare(void *x, void *y, void *context), void *context)
- {
- int left, right, aux;
- /*
- * Two NULL trees are equal.
- */
- if (bt1 == NULL && bt2 == NULL)
- return 0;
- /*
- * If the first tree is NULL then
- * return compare(NULL, root key of the second tree)
- * else if the second tree is NULL then
- * return compare(root key of the first tree, NULL)
- * else
- * left = compare(left1, left2);
- * right = compare(left1, right2);
- * if left trees differ
- * return left;
- * if root's keys differ
- * return comparison result of the keys
- * return the right
- */
- _ASSERT(bt1, ==, NULL, NULL_POINTER,
- /* compare(NULL, _binary_tree_get_key(bt2), context) */ -1);
- _ASSERT (bt2, ==, NULL, NULL_POINTER,
- /* compare(_binary_tree_get_key(bt1), NULL, context) */ 1);
- _ASSERT(compare, ==, NULL, NULL_POINTER, 0);
- left = right = aux = 0;
- left = _binary_tree_compare_trees(bt1->left, bt1->left, compare, context);
- right
- = _binary_tree_compare_trees(bt1->right, bt2->right, compare,
- context);
- if (left)
- return left;
- aux = compare(bt1->key, bt2->key, context);
- if (aux)
- return aux;
- return right;
- }
- int _binary_tree_is_empty(_binary_tree_t tree)
- {
- _ASSERT(tree, ==, NULL, NULL_POINTER, -1);
- /*
- * An empty tree has all it's internal pointers equal to NULL
- */
- return ((tree->left == NULL) && (tree->parent == NULL) && (tree->right
- == NULL) && (tree->key == NULL));
- }
- int _binary_tree_leaf(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER, -1);
- /*
- * A node is leaf only if it's children are NULL.
- */
- return ((node->left == NULL) && (node->right == NULL));
- }
- int _binary_tree_get_size(_binary_tree_t tree)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION, 0);
- /*
- * size(NULL) = 0
- * size(node) = 1 + size(left child) + size(right child)
- */
- return _binary_tree_get_size(tree->left) + _binary_tree_get_size(
- tree->right) + 1;
- }
- _binary_tree_t _binary_tree_get_root(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER, NULL);
- while (node->parent != NULL)
- node = node->parent;
- return node;
- }
- void *_binary_tree_get_key(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER, NULL);
- return node->key;
- }
- void _binary_tree_set_key(_binary_tree_t node, void *key)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER,);
- node->key = key;
- }
- _binary_tree_t _binary_tree_get_parent(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER, NULL);
- return node->parent;
- }
- void _binary_tree_set_parent(_binary_tree_t node, _binary_tree_t parent,
- int dir)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER,);
- _ASSERT(parent, ==, NULL, NULL_POINTER,);
- if (dir == -1)
- _binary_tree_set_left_child(parent, node);
- else if (dir == 1)
- _binary_tree_set_right_child(parent, node);
- else
- temelia_errno = INVALID_INPUT;
- }
- _binary_tree_t _binary_tree_get_left_child(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER, NULL);
- return node->left;
- }
- void _binary_tree_set_left_child(_binary_tree_t node, _binary_tree_t child)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER,);
- node->left = child;
- // If NULL left child is given, don't set the parent link.
- if (child)
- child->parent = node;
- }
- _binary_tree_t _binary_tree_get_right_child(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER, NULL);
- return node->right;
- }
- void _binary_tree_set_right_child(_binary_tree_t node, _binary_tree_t child)
- {
- _ASSERT(node, ==, NULL, NULL_POINTER,);
- node->right = child;
- // If NULL right child is given, don't set the parent link.
- if (child)
- child->parent = node;
- }
- void _binary_tree_join(_binary_tree_t parent, _binary_tree_t left,
- _binary_tree_t right)
- {
- _ASSERT(right, ==, NULL, NULL_POINTER,);
- _ASSERT(left, ==, NULL, NULL_POINTER,);
- _ASSERT(parent, ==, NULL, NULL_POINTER,);
- /*
- * Creates links between parent<->left and parent<->right
- * parent
- * parent, left, right => / \
- * left right
- */
- _binary_tree_set_left_child(parent, left);
- _binary_tree_set_right_child(parent, right);
- _binary_tree_set_parent(left, parent, -1);
- _binary_tree_set_parent(right, parent, 1);
- }
- void _binary_tree_split(_binary_tree_t parent, _binary_tree_t *left,
- _binary_tree_t *right)
- {
- _ASSERT(parent, ==, NULL, NULL_POINTER,);
- _ASSERT(left, ==, NULL, NULL_POINTER,);
- _ASSERT(right, ==, NULL, NULL_POINTER,);
- /*
- * Splits the tree into 3 trees
- * parent
- * / \ => parent, left, right
- * left right
- */
- *left = parent->left;
- parent->left = NULL;
- *right = parent->right;
- parent->right = NULL;
- }
- _binary_tree_t _binary_tree_create_node(_binary_tree_t parent,
- _binary_tree_t left, _binary_tree_t right, void *key, int dir)
- {
- _binary_tree_t new_node = _binary_tree_new(key);
- _ASSERT(parent, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(new_node, ==, NULL, NULL_POINTER, NULL);
- #ifndef RELEASE
- if (left && _binary_tree_get_parent(left) != parent)
- LOGGER(
- "[_binary_tree_create_node] invalid parent pointer %p for left child %p\n",
- parent, left);
- if (right && _binary_tree_get_parent(right) != parent)
- LOGGER(
- "[_binary_tree_create_node] invalid parent pointer %p for left child %p\n",
- parent, right);
- #endif
- _binary_tree_set_left_child(new_node, left);
- _binary_tree_set_right_child(new_node, right);
- /*
- * dir == -1
- * parent, left, right, key => parent
- * /
- * new_node(key)
- * / \
- * left right
- *
- * dir == 1
- * parent, left, right, key => parent
- * \
- * new_node(key)
- * / \
- * left right
- */
- if (dir == -1)
- _binary_tree_set_left_child(parent, new_node);
- else if (dir == 1)
- _binary_tree_set_right_child(parent, new_node);
- else
- {
- temelia_errno = INVALID_INPUT;
- return NULL;
- }
- return new_node;
- }
- int _binary_tree_get_height(_binary_tree_t tree)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION, 0);
- return 1 + MAX(_binary_tree_get_height(tree->left),
- _binary_tree_get_height(tree->right));
- }
- int _binary_tree_get_depth(_binary_tree_t node)
- {
- _ASSERT(node, ==, NULL, NOT_EXCEPTION, -1);
- return 1 + _binary_tree_get_depth(_binary_tree_get_parent(node));
- }
- void _binary_tree_preorder(_binary_tree_t tree, void key_handler(void *key,
- void *context), void *context)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- key_handler(tree->key, context);
- _binary_tree_preorder(tree->left, key_handler, context);
- _binary_tree_preorder(tree->right, key_handler, context);
- }
- void _binary_tree_inorder(_binary_tree_t tree, void key_handler(void *key,
- void *context), void *context)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _binary_tree_inorder(tree->left, key_handler, context);
- key_handler(tree->key, context);
- _binary_tree_inorder(tree->right, key_handler, context);
- }
- void _binary_tree_reverse_inorder(_binary_tree_t tree, void key_handler(
- void *key, void *context), void *context)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _binary_tree_reverse_inorder(tree->right, key_handler, context);
- key_handler(tree->key, context);
- _binary_tree_reverse_inorder(tree->left, key_handler, context);
- }
- void _binary_tree_postorder(_binary_tree_t tree, void key_handler(void *key,
- void *context), void *context)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _binary_tree_postorder(tree->left, key_handler, context);
- _binary_tree_postorder(tree->right, key_handler, context);
- key_handler(tree->key, context);
- }
- void _binary_tree_level_order(_binary_tree_t tree, void key_handler(void *key,
- void *context), void *context)
- {
- queue_t Q = queue_new(DEFAULT_SIZE);
- _binary_tree_node_t current_node;
- queue_push_back(Q, tree);
- while (!queue_is_empty(Q))
- {
- current_node = queue_get_front(Q);
- queue_pop_front(Q);
- key_handler(current_node->key, context);
- if (current_node->left)
- queue_push_back(Q, current_node->left);
- if (current_node->right)
- queue_push_back(Q, current_node->right);
- }
- queue_delete(Q);
- }
- void _binary_tree_show_indented(_binary_tree_t tree, void key_handler(
- void *key, int level, void *context), void *context, int level)
- {
- _ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _binary_tree_show_indented(tree->right, key_handler, context, level + 1);
- key_handler(tree->key, level, context);
- _binary_tree_show_indented(tree->left, key_handler, context, level + 1);
- }
- _binary_search_tree_node_t _binary_search_tree_search(binary_search_tree_t bst,
- void *key, int compare(void *x, void *y, void *context), void *context)
- {
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- // If the key is in the current tree node, return node's reference.
- if (!compare(bst->key, key, context))
- return bst;
- // If the current key is greater then root's key, search the key in the left sub-tree
- if (compare(key, bst->key, context) < 0)
- return _binary_search_tree_search(bst->left, key, compare, context);
- // Else search in the right sub-tree.
- return _binary_search_tree_search(bst->right, key, compare, context);
- }
- _binary_search_tree_node_t _binary_search_tree_insert(binary_search_tree_t bst,
- void *key, int compare(void *x, void *y, void *context), void *context)
- {
- int direction = 0;
- _binary_search_tree_node_t aux, pred;
- LOGGER(
- "[{internal} binary search tree insert] bst %p, key %p, compare %p, context %p\n",
- bst, key, compare, context);
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- if (_binary_tree_is_empty(bst))
- return NULL;
- aux = bst;
- while (aux)
- {
- pred = aux;
- // If key already exists, return NULL.
- if (!compare(key, aux->key, context))
- return NULL;
- // If key is lower than node's key then go to left node.
- if (compare(key, aux->key, context) < 0)
- {
- aux = aux->left;
- direction = -1;
- }
- // Else go to right node.
- else
- {
- aux = aux->right;
- direction = 1;
- }
- }
- /*
- * Creates the new node in the computed direction; set it a parent and NULL children.
- */
- return _binary_tree_create_node(pred, NULL, NULL, key, direction);
- }
- _binary_search_tree_node_t _binary_search_tree_remove(
- binary_search_tree_t *bst, void *key, int compare(void *x, void *y,
- void *context), void *context, binary_search_tree_t *my_deleted)
- {
- void *aux;
- binary_tree_node_t deleted, replaced;
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- _ASSERT (*bst, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- deleted = _binary_search_tree_search(*bst, key, compare, context);
- *my_deleted = NULL;
- _ASSERT(deleted, ==, NULL, ELEMENT_NOT_FOUND, NULL);
- // There are 4 cases :
- // 1) deleted node is leaf : simply remove it.
- // 2) deleted node has 1 child : change child's parent to deleted node's parent.
- // 3) deleted node has 2 children : swap between the right child and parent; and rebuild the links.
- // 4) deleted node is the root.
- if (deleted->left != NULL && deleted->right != NULL)
- {
- replaced = _binary_search_tree_next(*bst, deleted);
- aux = deleted->key;
- deleted->key = replaced->key;
- replaced->key = aux;
- *my_deleted = replaced;
- return __binary_search_tree_remove(bst, replaced);
- }
- *my_deleted = deleted;
- return __binary_search_tree_remove(bst, deleted);
- }
- _binary_search_tree_node_t _binary_search_tree_get_min(binary_search_tree_t bst)
- {
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- // The minimum key is in the most left node of tree.
- while (bst->left)
- bst = bst->left;
- return bst;
- }
- _binary_search_tree_node_t _binary_search_tree_get_max(binary_search_tree_t bst)
- {
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- // The minimum key is in the most right node of tree.
- while (bst->right)
- bst = bst->right;
- return bst;
- }
- _binary_search_tree_node_t _binary_search_tree_next(binary_search_tree_t bst,
- _binary_search_tree_node_t node)
- {
- _binary_search_tree_node_t parent;
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(node, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(node->key, ==, _binary_search_tree_get_max(bst), INVALID_INPUT, NULL);
- /*
- * If the current node has a right child
- * then the next key is the minimum key of the right child tree.
- * Else move to the tree until node == parent(node)->right
- * and then return the parent; that's because it would have node as
- * left child and the next key would be in the parent.
- */
- if (node->right)
- return _binary_search_tree_get_min(node->right);
- parent = node->parent;
- while (parent->right == node)
- {
- node = parent;
- parent = parent->parent;
- }
- return parent;
- }
- _binary_search_tree_node_t _binary_search_tree_prev(binary_search_tree_t bst,
- _binary_search_tree_node_t node)
- {
- _binary_search_tree_node_t parent;
- _ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(node, ==, node, NULL_POINTER, NULL);
- _ASSERT(node, ==, _binary_search_tree_get_max(bst), INVALID_INPUT, NULL);
- /*
- * If the current node has a left child
- * then the prev (previous) key is the maximum key of the left child tree.
- * Else move to the tree until node == parent(node)->left
- * and then return the parent; that's because it would have node as
- * right child and the previous key would be in the parent.
- */
- if (node->left)
- return _binary_search_tree_get_max(node->left);
- parent = node->parent;
- while (parent->left == node)
- {
- node = parent;
- parent = parent->parent;
- }
- return parent;
- }
- static binary_search_tree_t __binary_search_tree_remove(
- binary_search_tree_t *bst, binary_search_tree_t deleted)
- {
- int dir = 0;
- binary_search_tree_t parent = NULL, replaced = NULL;
- parent = deleted->parent;
- if (deleted->left)
- replaced = deleted->left;
- else
- replaced = deleted->right;
- if (parent)
- {
- if (parent->left == deleted)
- dir = -1;
- else
- dir = 1;
- }
- else if (replaced)
- {
- replaced->parent = NULL;
- *bst = replaced;
- }
- if (replaced)
- _binary_tree_set_parent(replaced, parent, dir);
- else if (parent)
- {
- if (dir == -1)
- parent->left = NULL;
- else
- parent->right = NULL;
- }
- return replaced;
- }
- _binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left(
- _binary_search_tree_node_t x)
- {
- _binary_search_tree_node_t y, px, b;
- _ASSERT(x, ==, NULL, NULL_POINTER, NULL);
- /* Y X
- * / \ / \
- * X a <= c Y
- * / \ / \
- * c b b a
- */
- y = x->right;
- _ASSERT(y, ==, NULL, NULL_POINTER, x);
- b = y->left;
- x->right = b;
- y->left = x;
- px = x->parent;
- x->parent = y;
- if (b)
- b->parent = x;
- y->parent = px;
- if (px != NULL)
- {
- if (px->left == x)
- px->left = y;
- else
- px->right = y;
- }
- return y;
- }
- _binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_right(
- _binary_search_tree_node_t x)
- {
- _binary_search_tree_node_t y, px, b;
- _ASSERT(x, ==, NULL, NULL_POINTER, NULL);
- /* X Y
- * / \ / \
- * Y a => c X
- * / \ / \
- * c b b a
- */
- y = x->left;
- _ASSERT(y, ==, NULL, NULL_POINTER, x);
- b = y->right;
- x->left = b;
- y->right = x;
- px = x->parent;
- x->parent = y;
- if (b)
- b->parent = x;
- y->parent = px;
- if (px != NULL)
- {
- if (px->left == x)
- px->left = y;
- else
- px->right = y;
- }
- return y;
- }
- _binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left_double(
- _binary_search_tree_node_t x)
- {
- _ASSERT(x, ==, NULL, INVALID_INPUT, NULL);
- x->right = _self_balanced_binary_search_tree_rotate_right(x->right);
- return _self_balanced_binary_search_tree_rotate_left(x);
- }
- _binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_right_double(
- _binary_search_tree_node_t x)
- {
- _ASSERT(x, ==, NULL, INVALID_INPUT, NULL);
- x->left = _self_balanced_binary_search_tree_rotate_left(x->left);
- return _self_balanced_binary_search_tree_rotate_right(x);
- }
|