Mastering Algorithms With C - Kyle Loudon [100]
return -1;
}
cmpval = tree->compare(*data, ((AvlNode *)bitree_data(node))->data);
if (cmpval < 0) {
/**************************************************************************
* *
* Move to the left. *
retval = lookup(tree, bitree_left(node), data);
}
else if (cmpval > 0) {
/**************************************************************************
* *
* Move to the right. *
* *
**************************************************************************/
retval = lookup(tree, bitree_right(node), data);
}
else {
if (!((AvlNode *)bitree_data(node))->hidden) {
/***********************************************************************
* *
* Pass back the data from the tree. *
* *
***********************************************************************/
*data = ((AvlNode *)bitree_data(node))->data;
retval = 0;
}
else {
/***********************************************************************
* *
* Return that the data was not found. *
* *
***********************************************************************/
return -1;
}
}
return retval;
}
/****************************************************************************
* *
* ----------------------------- bistree_init ---------------------------- *
* *
****************************************************************************/
void bistree_init(BisTree *tree, int (*compare)(const void *key1, const void
*key2), void (*destroy)(void *data)) {
/****************************************************************************
* *
* Initialize the tree. *
* *
****************************************************************************/
bitree_init(tree, destroy);
tree->compare = compare;
return;
}
/****************************************************************************
* *
* ---------------------------- bistree_destroy -------------------------- *
* *
****************************************************************************/
void bistree_destroy(BisTree *tree) {
/****************************************************************************
* *
* Destroy all nodes in the tree. *
* *
****************************************************************************/
destroy_left(tree, NULL);
/****************************************************************************
* *
* No operations are allowed now, but clear the structure as a precaution. *
* *
****************************************************************************/
memset(tree, 0, sizeof(BisTree));
return;
}
/****************************************************************************
* *
* ---------------------------- bistree_insert --------------------------- *
* *
****************************************************************************/
int bistree_insert(BisTree *tree, const void *data) {
int balanced = 0;
return insert(tree, &bitree_root(tree), data, &balanced);
}
/****************************************************************************
* *
* ---------------------------- bistree_remove --------------------------- *
* *
****************************************************************************/
int bistree_remove(BisTree *tree, const void *data) {
return hide(tree, bitree_root(tree), data);
}
/****************************************************************************
* *
* ---------------------------- bistree_lookup --------------------------- *
* *
****************************************************************************/
int bistree_lookup(BisTree *tree, void **data) {
return lookup(tree, bitree_root(tree), data);
}
Questions and Answers
Q: Akin to doubly-linked lists, some trees maintain pointers from child nodes back to their parents in addition to the normal pointers from parents to their children. Some trees maintain pointers between sibling nodes as well. Why might we do this?
A: In general, maintaining additional pointers gives us greater flexibility in how we traverse a tree. For example, maintaining