www.delorie.com/gnu/docs/avl/libavl_32.html

search

	Buy GNU books!

GNU libavl 2.0.1

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 <@xref{\NODE\, , bst.h.>,24} and an implementation file <@xref{\NODE\, , bst.c.>,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.

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

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "bst.h" <@xref{\NODE\, , BST operations.>,29}

Exercises:

1. What is the purpose of #ifndef BST_H ... #endif in <@xref{\NODE\, , bst.h.>,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