Trees - osvaldoandrade/ova-lib GitHub Wiki

Trees

Read this page when key order is part of the problem. The tree module is the right tool when you need search by key plus ordered operations such as minimum, maximum, predecessor, successor, range query, or in-order traversal.

Constructor and Variants

The constructor is:

tree *create_tree(tree_type type, comparator cmp);

The 2 variants are:

Variant	Meaning
`TREE_AVL`	AVL tree
`TREE_RED_BLACK`	red-black tree

The public API and ownership rules are the same for both variants. The variant choice changes balancing strategy, not the caller contract.

Core API

Function	Meaning
`insert`	inserts or updates one key-value pair
`search`	returns the stored value for a key or `NULL`
`delete`	removes one key if present
`min`	returns the value at the smallest key
`max`	returns the value at the largest key
`predecessor`	returns the value at the greatest key smaller than the query
`successor`	returns the value at the smallest key larger than the query
`range_query`	returns an allocated list of values in inclusive key range order
`in_order_traverse`	visits `(key, value)` pairs in ascending key order
`size`	returns the current pair count
`free`	frees tree nodes and the tree object

Insert and Update Semantics

The comparator defines key equality.

When insert sees a new key, it stores the key pointer and the value pointer.

When insert sees a key that compares equal to an existing key, it updates the stored value pointer and keeps the original stored key pointer. The new key pointer passed to the second insertion is not stored.

Return Shapes Matter

The tree API returns values, not keys, from:

search

min

max

predecessor

successor

That means if the caller needs both the key and the value, in_order_traverse is the public path that exposes both together.

Range Query and Traversal

t->range_query(t, low, high) returns an allocated list container of values whose keys lie in the inclusive range [low, high].

The values in that list are ordered by key. The values are stored pointers, not copies.

The caller must free the list container with list->free. The caller must not free list elements unless the program owns those payload objects for independent reasons.

Missing-Key Behavior

search returns NULL for a missing key.

delete on a missing key is a no-op.

predecessor and successor work even when the queried key is not stored. They search the order position that the query key would occupy and return the neighboring stored value.

Ownership and Cleanup

The tree owns nodes only. It does not own user keys or user values.

Destroy the tree with t->free(t). Destroy range-result lists with list->free.