The binary tree as implemented already allows inserting and deleting elements, but it doesn't promise that iterators will remain valid after an insertion or deletion. So the simplest way to use insertion and deletion is to avoid insert/delete while an iterator is defined for the tree. As the example code (Listing 8) shows, you should always call reset on any existing iterator after insertion or deletion; this reinitializes the iterator to a valid state.
The second simplest method to support inserts/deletes with iterators is to block inserts and deletes whenever at least one iterator exists for the binary tree. To support this method, my binary tree class has an additional data member, a simple counter. This counter is incremented whenever an iterator for that binary tree is created, and decremented when an iterator is deleted. Both insert and delete operations check for a counter value of zero before they modify the binary tree. The insert code can throw an exception (it is declared void); the delete can also throw an exception or return failure whenever the operation is blocked.
My first attempt to support inserts and deletes used a strategy similar to the one in reference [4]. Listing 9 shows the changes made to the binary tree insert, remove, and clear functions. When an iterator is created, it registers itself with the underlying data structure, a binary tree in this case. Then every time an insert or delete is executed, the internal list of iterators (stored in the binary tree) is scanned and each iterator is updated to reflect the insert or delete. The update to an iterator consists of saving the current location (node) for the iterator, then resetting the iterator and stepping through the binary tree with the increment operator until the old location is found. If the old location was deleted, then the next node in the traversal is used.
At first this technique appears to work and it is fairly simple to implement. However, I ran into a problematic test case for postorder traversal. Consider the following binary tree before and after the letter s is deleted.
s i / \ / \ f t f t / \ \ / \ \ d h w d h w / \ \ / \ g i z g z before delete after delete of sThe post order traversal of the tree before deleting the letter s is given by: d g i h f z w t s. After s is deleted the postorder traversal is: : d g h f z w t i. Now suppose a post-order iterator exists and it is currently pointing to the letter h in the tree before the delete. Next we delete the letter s. The iterator is modified to reflect the deletion of the letter s and it is reset to point to the letter h as before. Now if traversal is continued the letter i will be traversed twice! In the original tree, the letter i was visited just before the letter h. In the new tree, i is the last letter to be visited. If behavior such as this poses a problem, you should probably reject this strategy.
The final implementation I tried (not listed or provided on the ftp site) involves using reference-counted binary tree nodes. The implementation stores the complete traversal path in a linked list by storing pointers to the binary tree nodes in the order that they must be traversed. This circumvents the problem of inserts and deletes since once the path is generated and stored in a link list, it is never affected by inserts or deletes in the binary tree. The reference counted node prevents the data from being deleted until all references to it are deleted, that is, until the last iterator referring to it is deleted.