Mastering Algorithms With C - Kyle Loudon [99]
*balanced = 0;
}
else {
if ((retval = insert(tree, &bitree_right(*node), data, balanced))
!= 0) {
return retval;
}
}
/***********************************************************************
* *
* Ensure that the tree remains balanced. *
* *
***********************************************************************/
if (!(*balanced)) {
switch (((AvlNode *)bitree_data(*node))->factor) {
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
break;
case AVL_RGT_HEAVY:
rotate_right(node);
*balanced = 1;
}
}
} /* if (cmpval > 0) */
else {
/*************************************************************************
* *
* Handle finding a copy of the data. *
* *
*************************************************************************/
if (!((AvlNode *)bitree_data(*node))->hidden) {
/********************************************************************
* *
* Do nothing since the data is in the tree and not hidden. *
* *
return 1;
}
else {
/********************************************************************
* *
* Insert the new data and mark it as not hidden. *
* *
********************************************************************/
if (tree->destroy != NULL) {
/*****************************************************************
* *
* Destroy the hidden data since it is being replaced. *
* *
*****************************************************************/
tree->destroy(((AvlNode *)bitree_data(*node))->data);
}
((AvlNode *)bitree_data(*node))->data = (void *)data;
((AvlNode *)bitree_data(*node))->hidden = 0;
/********************************************************************
* *
* Do not rebalance because the tree structure is unchanged. *
* *
********************************************************************/
*balanced = 1;
}
}
}
return 0;
}
/****************************************************************************
* *
* --------------------------------- hide -------------------------------- *
* *
****************************************************************************/
static int hide(BisTree *tree, BiTreeNode *node, const void *data) {
int cmpval,
retval;
if (bitree_is_eob(node)) {
/**************************************************************************
* *
* Return that the data was not found. *
* *
**************************************************************************/
return -1;
}
cmpval = tree->compare(data, ((AvlNode *)bitree_data(node))->data);
if (cmpval < 0) {
/**************************************************************************
* *
* Move to the left. *
* *
**************************************************************************/
retval = hide(tree, bitree_left(node), data);
}
else if (cmpval > 0) {
/**************************************************************************
* *
* Move to the right. *
* *
**************************************************************************/
retval = hide(tree, bitree_right(node), data);
}
else {
/**************************************************************************
* *
* Mark the node as hidden. *
* *
**************************************************************************/
((AvlNode *)bitree_data(node))->hidden = 1;
retval = 0;
}
return retval;
}
/****************************************************************************
* *
* -------------------------------- lookup ------------------------------- *
* *
****************************************************************************/
static int lookup(BisTree *tree, BiTreeNode *node, void **data) {
int cmpval,
retval;
if (bitree_is_eob(node)) {
/**************************************************************************
* *
* Return that the data was not found. *
* *
**************************************************************************/