A binary-sorted tree is a container where each node has maximally two `child' nodes, termed the `left' child and the `right' child. It is guaranteed that the data in the left child is less than (according to a user-supplied comparison function) the node's own data, while the data in the right child is greater. This means that an arbitrary existing node or the correct place for insertion of a new node can be found in logarithmic time.1 Since an ordering exists over all the nodes throughout the lifetime of the structure, that ordering relation (comparison function) must be defined at the time the structure is created. For Libretto, a binary-sorted tree is a ‘struct bstree’ (with a ‘typedef’ name of ‘Bstree’) whose members are private.
User data is not stored directly in an object of type ‘Bstree’, but in an intermediate type called a ‘Bstnode’. These objects are not allocated explicitly by the user. The procedure for retrieving data from a bstree is to call a function on the bstree which returns a bstnode, and then to call a function on the bstnode which yields the stored data. User data is stored as generic pointers (‘void *’).
Given a ‘Bstnode *’, the user can use the following function to retrieve the data stored in that chainlink:
Returns the user-supplied pointer stored in the bstnode node.
As stated above, all insertions must be done in accordance with a user-supplied comparison function:
int (*) (void *
a, void *
b, void *
paramsThe type of a function defining an ordering on objects in a bstree. The function is passed a pointer to each of two each objects, a and b, as well as a pointer to user-supplied parameters params. It should return a negative value if a precedes b, zero if the two objects are equal, and a positive value if b precedes a. If such a function returns different orderings for the same two objects at different times, then the behaviour is undefined.
All the ‘Bstree’ and ‘Bstnode’ functions are declared in libretto/bstree.h.
[1] Strictly speaking, this is the case only if the tree is balanced. For a tree with n members and depth d, where g is the logarithm (base 2) of n, as the ratio d/g approaches 1, the time complexity for lookups approaches O(n). Future releases of Libretto may provide types for self-balancing trees, which can avoid problems caused by potential degradation of trees into lists.