Database Reference
In-Depth Information
Example 7:
Suppose we wish to load the string HBXAM to a BST. We obtain a
BST as follows:
Figure A1-11.
Example of BST
Assuming the conventions of Figure
A1-5
, the algorithms of Figure
A1-6
would still
be applicable but with two extensions: We need to introduce an algorithm for inserting
a node in the tree while preserving its properties. Secondly, we need to be able to search
for a particular value in the tree. Figures
A1-12
and
A1-13
provide the insertion algorithm,
and the search algorithm respectively. Note that the order in which nodes are added to
the BST affects the structure of the tree. In fact, if a sorted list is added to the BST,
it degrades to a linear linked list.
Figure A1-12a.
Algorithm to Insert a Node in the BST
