Ion Gaztañaga wrote:
Steven Watanabe wrote:
warning untested:
[snip]
Thanks Steven. If an exception is thrown, new_root is the root of a BST tree so a non-recursive destruction algorithm is possible. I'll test your code ASAP.
I've implemented your algorithm and all Intrusive and Interprocess tree tests run ok. Since the STL-like tree's header node maintains links to the leftmost and rightmost nodes of the tree, I've also added the incremental computation of the rightmost and leftmost nodes of the newly created subtree to your function. The non-recursive tree destruction is based on the following algorithm found on http://eternallyconfuzzled.com: 1 void jsw_destroy ( struct jsw_tree *tree ) 2 { 3 struct jsw_node *it = tree->root; 4 struct jsw_node *save; 5 6 while ( it != NULL ) { 7 if ( it->link[0] != NULL ) { 8 /* Right rotation */ 9 save = it->link[0]; 10 it->link[0] = save->link[1]; 11 save->link[1] = it; 12 } 13 else { 14 save = it->link[1]; 15 free ( it ); 16 } 17 18 it = save; 19 } 20 } which incrementally linearizes the tree using right rotations (forming a singly linked list using the right children pointer) and destroys nodes with no left children. Thanks a lot again! Ion