Mastering Algorithms With C - Kyle Loudon [98]
*****************************************************************************/
if (*position != NULL) {
destroy_left(tree, *position);
destroy_right(tree, *position);
if (tree->destroy != NULL) {
/***********************************************************************
* *
* Call a user-defined function to free dynamically allocated data. *
* *
***********************************************************************/
tree->destroy(((AvlNode *)(*position)->data)->data);
}
/**************************************************************************
* *
* Free the AVL data in the node, then free the node itself. *
* *
**************************************************************************/
free((*position)->data);
free(*position);
*position = NULL;
/**************************************************************************
* *
* Adjust the size of the tree to account for the destroyed node. *
* *
**************************************************************************/
tree->size--;
}
return;
}
/*****************************************************************************
* *
* -------------------------------- insert -------------------------------- *
* *
*****************************************************************************/
static int insert(BisTree *tree, BiTreeNode **node, const void *data, int
*balanced) {
AvlNode *avl_data;
int cmpval,
retval;
/*****************************************************************************
* *
* Insert the data into the tree. *
* *
*****************************************************************************/
if (bitree_is_eob(*node)) {
/**************************************************************************
* *
* Handle insertion into an empty tree. *
* *
**************************************************************************/
if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
return bitree_ins_left(tree, *node, avl_data);
}
else {
/**************************************************************************
* *
* Handle insertion into a tree that is not empty. *
* *
**************************************************************************/
cmpval = tree->compare(data, ((AvlNode *)bitree_data(*node))->data);
if (cmpval < 0) {
/***********************************************************************
* *
* Move to the left. *
* *
***********************************************************************/
if (bitree_is_eob(bitree_left(*node))) {
if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
if (bitree_ins_left(tree, *node, avl_data) != 0)
return -1;
*balanced = 0;
}
else {
if ((retval = insert(tree, &bitree_left(*node), data, balanced))
!= 0) {
return retval;
}
}
/***********************************************************************
* *
* Ensure that the tree remains balanced. *
* *
***********************************************************************/
if (!(*balanced)) {
switch (((AvlNode *)bitree_data(*node))->factor) {
case AVL_LFT_HEAVY:
rotate_left(node);
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
*balanced = 1;
}
}
} /* if (cmpval < 0) */
else if (cmpval > 0) {
/***********************************************************************
* *
* Move to the right. *
* *
***********************************************************************/
if (bitree_is_eob(bitree_right(*node))) {
if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
if (bitree_ins_right(tree, *node, avl_data) != 0)
return -1;