Balanced Binary Trees

GLib Reference Manual
<<< Previous Page	Home	Up	Next Page >>>

Details

struct GTree

struct GTree;

The GTree struct is an opaque data structure representing a Balanced Binary Tree. It should be accessed only by using the following functions.

g_tree_new ()

GTree*      g_tree_new                      (GCompareFunc key_compare_func);

Creates a new GTree.

`key_compare_func` :	the function used to order the nodes in the GTree. It should return values similar to the standard `strcmp()` function - 0 if the two arguments are equal, a negative value if the first argument comes before the second, or a positive value if the first argument comes after the second.
Returns :	a new GTree.

g_tree_insert ()

void        g_tree_insert                   (GTree *tree,
                                             gpointer key,
                                             gpointer value);

Inserts a key/value pair into a GTree. If the given key already exists in the GTree it is set to the new value. (If you are using dynamically allocated keys and values you should be careful to ensure that the old values are freed.)

The tree is automatically 'balanced' as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible.

`tree` :	a GTree.
`key` :	the key to insert.
`value` :	the value corresponding to the key.

g_tree_nnodes ()

gint        g_tree_nnodes                   (GTree *tree);

Gets the number of nodes in a GTree.

`tree` :	a GTree.
Returns :	the number of nodes in the GTree.

g_tree_height ()

gint        g_tree_height                   (GTree *tree);

Gets the height of a GTree.

If the GTree contains no nodes, the height is 0. If the GTree contains only one root node the height is 1. If the root node has children the height is 2, etc.

`tree` :	a GTree.
Returns :	the height of the GTree.

g_tree_lookup ()

gpointer    g_tree_lookup                   (GTree *tree,
                                             gpointer key);

Gets the value corresponding to the given key. Since a GTree is automatically balanced as key/value pairs are added, key lookup is very fast.

`tree` :	a GTree.
`key` :	the key to look up.
Returns :	the value corresponding to the key.

g_tree_search ()

gpointer    g_tree_search                   (GTree *tree,
                                             GSearchFunc search_func,
                                             gpointer data);

Searches a GTree using an alternative form of the comparison function.

This function is not as useful as it sounds. It allows you to use a different function for performing the lookup of a key. However, since the tree is ordered according to the key_compare_func function passed to g_tree_new(), the function you pass to g_tree_search() must return exactly the same value as would be returned by the comparison function, for each pair of tree nodes, or the search will not work.

To search for a specific value, you can use g_tree_traverse().

`tree` :	a GTree.
`search_func` :	the comparison function used to search the GTree.
`data` :	the data passed as the second argument to the `search_func` function.
Returns :	the value corresponding to the found key, or NULL if the key is not found.

GSearchFunc ()

gint        (*GSearchFunc)                  (gpointer key,
                                             gpointer data);

Specifies the type of function passed to g_tree_search().

`key` :	a key from a GTree.
`data` :	the data to compare with the key.
Returns :	0 if the desired key has been found, a negative number if the desired key comes before `key` in the sort order of the GTree, or a positive value if the desired key comes after `key`.

g_tree_traverse ()

void        g_tree_traverse                 (GTree *tree,
                                             GTraverseFunc traverse_func,
                                             GTraverseType traverse_type,
                                             gpointer data);

Calls the given function for each node in the GTree.

`tree` :	a GTree.
`traverse_func` :	the function to call for each node visited. If this function returns TRUE, the traversal is stopped.
`traverse_type` :	the order in which nodes are visited, one of `G_IN_ORDER`, `G_PRE_ORDER` and `G_POST_ORDER`.
`data` :	user data to pass to the traverse function.

GTraverseFunc ()

gint        (*GTraverseFunc)                (gpointer key,
                                             gpointer value,
                                             gpointer data);

Specifies the type of function passed to g_tree_traverse(). It is passed the key and value of each node, together with the user_data parameter passed to g_tree_traverse(). If the function returns TRUE, the traversal is stopped.

`key` :	a key of a GTree node.
`value` :	the value corresponding to the key.
`data` :	user data passed to g_tree_traverse().
Returns :	TRUE to stop the traversal.

enum GTraverseType

typedef enum
{
  G_IN_ORDER,
  G_PRE_ORDER,
  G_POST_ORDER,
  G_LEVEL_ORDER
} GTraverseType;

Specifies the type of traveral performed by g_tree_traverse(), g_node_traverse() and g_node_find().

G_PRE_ORDER visits a node, then its children.
G_IN_ORDER vists a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function.
G_POST_ORDER visits the node's children, then the node itself.
G_LEVEL_ORDER is not implemented for Balanced Binary Trees. For N-ary Trees it calls the function for each child of the node, then it recursively visits each child.

g_tree_remove ()

void        g_tree_remove                   (GTree *tree,
                                             gpointer key);

Removes a key/value pair from a GTree. If the key or value is dynamically allocated you must remember to free them yourself.

`tree` :	a GTree.
`key` :	the key to remove.

g_tree_destroy ()

void        g_tree_destroy                  (GTree *tree);

Destroys the GTree, freeing all of the memory allocated. But it doesn't free keys or values.

tree : a GTree.