Mastering Algorithms With C - Kyle Loudon [97]
}
else {
/**************************************************************************
* *
* Perform an RL rotation. *
* *
**************************************************************************/
grandchild = bitree_left(right);
bitree_left(right) = bitree_right(grandchild);
bitree_right(grandchild) = right;
bitree_right(*node) = bitree_left(grandchild);
bitree_left(grandchild) = *node;
switch (((AvlNode *)bitree_data(grandchild))->factor) {
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_RGT_HEAVY;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
break;
}
((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
/*****************************************************************************
* *
* ----------------------------- destroy_left ----------------------------- *
* *
*****************************************************************************/
static void destroy_left(BisTree *tree, BiTreeNode *node) {
BiTreeNode **position;
/*****************************************************************************
* *
* Do not allow destruction of an empty tree. *
* *
*****************************************************************************/
if (bitree_size(tree) == 0)
return;
/*****************************************************************************
* *
* Determine where to destroy nodes. *
* *
*****************************************************************************/
if (node == NULL)
position = &tree->root;
else
position = &node->left;
/*****************************************************************************
* *
* Destroy the nodes. *
* *
*****************************************************************************/
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;
}
/*****************************************************************************
* *
* ----------------------------- destroy_right ---------------------------- *
* *
*****************************************************************************/
static void destroy_right(BisTree *tree, BiTreeNode *node) {
BiTreeNode **position;
/*****************************************************************************
* *
* Do not allow destruction of an empty tree. *
* *
*****************************************************************************/
if (bitree_size(tree) == 0)
return;
/*****************************************************************************
* *
* Determine where to destroy nodes. *
* *
*****************************************************************************/
if (node == NULL)
position = &tree->root;
else
position = &node->right;
/*****************************************************************************
* *
* Destroy the nodes. *
* *