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


GNU libavl 2.0.1

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

5. Binary Search Trees

The previous chapter motivated the need for binary search trees. This chapter implements a table ADT backed by a binary search tree. Along the way, we'll see how binary search trees are constructed and manipulated in abstract terms as well as in concrete C code.

The library includes a header file &#60;@xref{\NODE\, , bst.h.&#62;,24} and an implementation file &#60;@xref{\NODE\, , bst.c.&#62;,25}, outlined below. We borrow most of the header file from the generic table headers designed a couple of chapters back, simply replacing tbl by bst, the prefix used in this table module.

 
&#60;@xref{\NODE\, , License.&#62;,1}
#ifndef BST_H
#define @cindex BST_H macro
BST_H 1
#include &#60;stddef.h&#62;
&#60;@xref{\NODE\, , Table types; tbl =>.&#62; bst,14}
&#60;@xref{\NODE\, , BST maximum height.&#62;,28}
&#60;@xref{\NODE\, , BST table structure.&#62;,27}
&#60;@xref{\NODE\, , BST node structure.&#62;,26}
&#60;@xref{\NODE\, , BST traverser structure.&#62;,61}
&#60;@xref{\NODE\, , Table function prototypes; tbl =>.&#62; bst,15}
&#60;@xref{\NODE\, , BST extra function prototypes.&#62;,88}
#endif /* bst.h */
&#60;@xref{\NODE\, , Table assertion function control directives; tbl =>.&#62; bst,593}

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include &#60;string.h&#62;
#include "bst.h"
&#60;@xref{\NODE\, , BST operations.&#62;,29}

Exercises:

1. What is the purpose of #ifndef BST_H ... #endif in &#60;@xref{\NODE\, , bst.h.&#62;,24} above? [answer]

5.1 Vocabulary  
5.2 Data Types  
5.3 Rotations  
5.4 Operations  
5.5 Creation  
5.6 Search  
5.7 Insertion  
5.8 Deletion  
5.9 Traversal  
5.10 Copying  
5.11 Destruction  
5.12 Balance  
5.13 Aside: Joining BSTs  
5.14 Testing  
5.15 Additional Exercises  


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

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