www.delorie.com/gnu/docs/avl/libavl_229.html   search  
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

14.2 Operations

When we added parent pointers to BST nodes, we did not change the interpretation of any of the node members. This means that any function that examines PBSTs without modifying them will work without change. We take advantage of that for tree search. We also get away with it for destruction, since there's no problem with failing to update parent pointers in that case. Although we could, technically, do the same for traversal, that would negate much of the advantage of parent pointers, so we reimplement them. Here is the overall outline:

&#60;@xref{\NODE\, , TBST creation function; tbst =>.&#62; pbst,252}
&#60;@xref{\NODE\, , BST search function; bst =>.&#62; pbst,31}
&#60;@xref{\NODE\, , PBST item insertion function.&#62;,490}
&#60;@xref{\NODE\, , Table insertion convenience functions; tbl =>.&#62; pbst,592}
&#60;@xref{\NODE\, , PBST item deletion function.&#62;,493}
&#60;@xref{\NODE\, , PBST traversal functions.&#62;,502}
&#60;@xref{\NODE\, , PBST copy function.&#62;,509}
&#60;@xref{\NODE\, , BST destruction function; bst =>.&#62; pbst,84}
&#60;@xref{\NODE\, , PBST balance function.&#62;,511}
&#60;@xref{\NODE\, , Default memory allocation functions; tbl =>.&#62; pbst,6}
&#60;@xref{\NODE\, , Table assertion functions; tbl =>.&#62; pbst,594}
This code is included in @refalso{487

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003