2009-11-04

Continue from last week the implementation of binary search tree traversal, this time using pointer to pointer (see bst-new.c attached). This approach cannot be efficiently emulated by other languages like Java.

• Review: writing free_bst() recursively. The malloc()/free() pair of functions is how you obtain/relinquish memory. Remember not to free(t) first, otherwise t->left and t->right would become garbage.
• find_pos() takes pointer to pointer to a binary search tree node for argument, and returns pointer to pointer to node where the node with given key would be found. If there is no node with the given key, returns pointer to the NULL pointer. It could either be the original bst_t ** to the root node, or either the memory location of the left or right member of some node that contains the NULL pointer.
• In other words, find_pos() returns the position that can be used to modify the tree, either for insert or remove.
• find() can be written in terms of find_pos().
• insert() can be written in terms of find_pos().
• As an exercise, see if you can write remove() in terms of find_pos() as well. It may involve writing a find_min_pos() function.

Discussion

• The indirect pointer can be seen reflected in the assembly code of bst-new.c. It doesn't increase number of instructions significantly (compared to bst.s, attached, generated from bst.c from last week).
• The insert() function is now tail recursive, and it generates much better code compared to before.
• With -O3, the compiler inlines the definition of find_pos() into find() and insert(), essentially synthesizing new functions based on the one we wrote.