Top 
Balanced Binary TreesBalanced Binary Trees — a sorted collection of key/value pairs optimized for searching and traversing in order 
GTree *  g_tree_new () 
GTree *  g_tree_ref () 
void  g_tree_unref () 
GTree *  g_tree_new_with_data () 
GTree *  g_tree_new_full () 
GTreeNode *  g_tree_node_first () 
GTreeNode *  g_tree_node_last () 
GTreeNode *  g_tree_node_previous () 
GTreeNode *  g_tree_node_next () 
GTreeNode *  g_tree_insert_node () 
void  g_tree_insert () 
GTreeNode *  g_tree_replace_node () 
void  g_tree_replace () 
gpointer  g_tree_node_key () 
gpointer  g_tree_node_value () 
gint  g_tree_nnodes () 
gint  g_tree_height () 
GTreeNode *  g_tree_lookup_node () 
gpointer  g_tree_lookup () 
gboolean  g_tree_lookup_extended () 
void  g_tree_foreach_node () 
void  g_tree_foreach () 
void  g_tree_traverse () 
gboolean  (*GTraverseFunc) () 
gboolean  (*GTraverseNodeFunc) () 
GTreeNode *  g_tree_search_node () 
gpointer  g_tree_search () 
GTreeNode *  g_tree_lower_bound () 
GTreeNode *  g_tree_upper_bound () 
gboolean  g_tree_remove () 
gboolean  g_tree_steal () 
void  g_tree_remove_all () 
void  g_tree_destroy () 
The GTree structure and its associated functions provide a sorted collection of key/value pairs optimized for searching and traversing in order. This means that most of the operations (access, search, insertion, deletion, ...) on GTree are O(log(n)) in average and O(n) in worst case for time complexity. But, note that maintaining a balanced sorted GTree of n elements is done in time O(n log(n)).
To create a new GTree use g_tree_new()
.
To insert a key/value pair into a GTree use g_tree_insert()
(O(n log(n))).
To remove a key/value pair use g_tree_remove()
(O(n log(n))).
To look up the value corresponding to a given key, use
g_tree_lookup()
and g_tree_lookup_extended()
.
To find out the number of nodes in a GTree, use g_tree_nnodes()
. To
get the height of a GTree, use g_tree_height()
.
To traverse a GTree, calling a function for each node visited in
the traversal, use g_tree_foreach()
.
To destroy a GTree, use g_tree_destroy()
.
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 
GTree *
g_tree_ref (GTree *tree
);
Increments the reference count of tree
by one.
It is safe to call this function from any thread.
Since: 2.22
void
g_tree_unref (GTree *tree
);
Decrements the reference count of tree
by one.
If the reference count drops to 0, all keys and values will
be destroyed (if destroy functions were specified) and all
memory allocated by tree
will be released.
It is safe to call this function from any thread.
Since: 2.22
GTree * g_tree_new_with_data (GCompareDataFunc key_compare_func
,gpointer key_compare_data
);
Creates a new GTree with a comparison function that accepts user data.
See g_tree_new()
for more details.
GTree * g_tree_new_full (GCompareDataFunc key_compare_func
,gpointer key_compare_data
,GDestroyNotify key_destroy_func
,GDestroyNotify value_destroy_func
);
Creates a new GTree like g_tree_new()
and allows to specify functions
to free the memory allocated for the key and value that get called when
removing the entry from the GTree.
key_compare_func 
qsort()style comparison function 

key_compare_data 
data to pass to comparison function 

key_destroy_func 
a function to free the memory allocated for the key
used when removing the entry from the GTree or 

value_destroy_func 
a function to free the memory allocated for the
value used when removing the entry from the GTree or 
GTreeNode *
g_tree_node_first (GTree *tree
);
Returns the first inorder node of the tree, or NULL
for an empty tree.
Since: 2.68
GTreeNode *
g_tree_node_last (GTree *tree
);
Returns the last inorder node of the tree, or NULL
for an empty tree.
Since: 2.68
GTreeNode *
g_tree_node_previous (GTreeNode *node
);
Returns the previous inorder node of the tree, or NULL
if the passed node was already the first one.
Since: 2.68
GTreeNode *
g_tree_node_next (GTreeNode *node
);
Returns the next inorder node of the tree, or NULL
if the passed node was already the last one.
Since: 2.68
GTreeNode * g_tree_insert_node (GTree *tree
,gpointer key
,gpointer value
);
Inserts a key/value pair into a GTree.
If the given key already exists in the GTree its corresponding value
is set to the new value. If you supplied a value_destroy_func
when
creating the GTree, the old value is freed using that function. If
you supplied a key_destroy_func
when creating the GTree, the passed
key is freed using that function.
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. The cost of maintaining a balanced tree while inserting new key/value result in a O(n log(n)) operation where most of the other operations are O(log(n)).
Since: 2.68
void g_tree_insert (GTree *tree
,gpointer key
,gpointer value
);
Inserts a key/value pair into a GTree.
Inserts a new key and value into a GTree as g_tree_insert_node()
does,
only this function does not return the inserted or set node.
GTreeNode * g_tree_replace_node (GTree *tree
,gpointer key
,gpointer value
);
Inserts a new key and value into a GTree similar to g_tree_insert_node()
.
The difference is that if the key already exists in the GTree, it gets
replaced by the new key. If you supplied a value_destroy_func
when
creating the GTree, the old value is freed using that function. If you
supplied a key_destroy_func
when creating the GTree, the old key is
freed using that function.
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.
Since: 2.68
void g_tree_replace (GTree *tree
,gpointer key
,gpointer value
);
Inserts a new key and value into a GTree as g_tree_replace_node()
does,
only this function does not return the inserted or set node.
gpointer
g_tree_node_key (GTreeNode *node
);
Gets the key stored at a particular tree node.
Since: 2.68
gpointer
g_tree_node_value (GTreeNode *node
);
Gets the value stored at a particular tree node.
Since: 2.68
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.
GTreeNode * g_tree_lookup_node (GTree *tree
,gconstpointer key
);
Gets the tree node corresponding to the given key. Since a GTree is automatically balanced as key/value pairs are added, key lookup is O(log n) (where n is the number of key/value pairs in the tree).
the tree node corresponding to
the key, or NULL
if the key was not found.
[nullable][transfer none]
Since: 2.68
gpointer g_tree_lookup (GTree *tree
,gconstpointer key
);
Gets the value corresponding to the given key. Since a GTree is automatically balanced as key/value pairs are added, key lookup is O(log n) (where n is the number of key/value pairs in the tree).
gboolean g_tree_lookup_extended (GTree *tree
,gconstpointer lookup_key
,gpointer *orig_key
,gpointer *value
);
Looks up a key in the GTree, returning the original key and the
associated value. This is useful if you need to free the memory
allocated for the original key, for example before calling
g_tree_remove()
.
tree 
a GTree 

lookup_key 
the key to look up 

orig_key 
returns the original key. 
[out][optional][nullable] 
value 
returns the value associated with the key. 
[out][optional][nullable] 
void g_tree_foreach_node (GTree *tree
,GTraverseNodeFunc func
,gpointer user_data
);
Calls the given function for each of the nodes in the GTree.
The function is passed the pointer to the particular node, and the given
data
parameter. The tree traversal happens inorder.
The tree may not be modified while iterating over it (you can't add/remove items). To remove all items matching a predicate, you need to add each item to a list in your GTraverseFunc as you walk over the tree, then walk the list and remove each item.
Since: 2.68
void g_tree_foreach (GTree *tree
,GTraverseFunc func
,gpointer user_data
);
Calls the given function for each of the key/value pairs in the GTree.
The function is passed the key and value of each pair, and the given
data
parameter. The tree is traversed in sorted order.
The tree may not be modified while iterating over it (you can't add/remove items). To remove all items matching a predicate, you need to add each item to a list in your GTraverseFunc as you walk over the tree, then walk the list and remove each item.
void g_tree_traverse (GTree *tree
,GTraverseFunc traverse_func
,GTraverseType traverse_type
,gpointer user_data
);
g_tree_traverse
has been deprecated since version 2.2 and should not be used in newlywritten code.
The order of a balanced tree is somewhat arbitrary.
If you just want to visit all nodes in sorted order, use
g_tree_foreach()
instead. If you really need to visit nodes in
a different order, consider using an nary tree.
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 

traverse_type 
the order in which nodes are visited, one of 

user_data 
user data to pass to the function 
gboolean (*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 
gboolean (*GTraverseNodeFunc) (GTreeNode *node
,gpointer data
);
Specifies the type of function passed to g_tree_foreach_node()
. It is
passed each node, together with the user_data
parameter passed to
g_tree_foreach_node()
. If the function returns TRUE
, the traversal is
stopped.
Since: 2.68
GTreeNode * g_tree_search_node (GTree *tree
,GCompareFunc search_func
,gconstpointer user_data
);
Searches a GTree using search_func
.
The search_func
is called with a pointer to the key of a key/value
pair in the tree, and the passed in user_data
. If search_func
returns
0 for a key/value pair, then the corresponding node is returned as
the result of g_tree_search()
. If search_func
returns 1, searching
will proceed among the key/value pairs that have a smaller key; if
search_func
returns 1, searching will proceed among the key/value
pairs that have a larger key.
the node corresponding to the
found key, or NULL
if the key was not found.
[nullable][transfer none]
Since: 2.68
gpointer g_tree_search (GTree *tree
,GCompareFunc search_func
,gconstpointer user_data
);
Searches a GTree using search_func
.
The search_func
is called with a pointer to the key of a key/value
pair in the tree, and the passed in user_data
. If search_func
returns
0 for a key/value pair, then the corresponding value is returned as
the result of g_tree_search()
. If search_func
returns 1, searching
will proceed among the key/value pairs that have a smaller key; if
search_func
returns 1, searching will proceed among the key/value
pairs that have a larger key.
GTreeNode * g_tree_lower_bound (GTree *tree
,gconstpointer key
);
Gets the lower bound node corresponding to the given key,
or NULL
if the tree is empty or all the nodes in the tree
have keys that are strictly lower than the searched key.
The lower bound is the first node that has its key greater than or equal to the searched key.
the tree node corresponding to
the lower bound, or NULL
if the tree is empty or has only
keys strictly lower than the searched key.
[nullable][transfer none]
Since: 2.68
GTreeNode * g_tree_upper_bound (GTree *tree
,gconstpointer key
);
Gets the upper bound node corresponding to the given key,
or NULL
if the tree is empty or all the nodes in the tree
have keys that are lower than or equal to the searched key.
The upper bound is the first node that has its key strictly greater than the searched key.
the tree node corresponding to the
upper bound, or NULL
if the tree is empty or has only keys
lower than or equal to the searched key.
[nullable][transfer none]
Since: 2.68
gboolean g_tree_remove (GTree *tree
,gconstpointer key
);
Removes a key/value pair from a GTree.
If the GTree was created using g_tree_new_full()
, the key and value
are freed using the supplied destroy functions, otherwise you have to
make sure that any dynamically allocated values are freed yourself.
If the key does not exist in the GTree, the function does nothing.
The cost of maintaining a balanced tree while removing a key/value result in a O(n log(n)) operation where most of the other operations are O(log(n)).
gboolean g_tree_steal (GTree *tree
,gconstpointer key
);
Removes a key and its associated value from a GTree without calling the key and value destroy functions.
If the key does not exist in the GTree, the function does nothing.
void
g_tree_remove_all (GTree *tree
);
Removes all nodes from a GTree and destroys their keys and values,
then resets the GTree’s root to NULL
.
Since: 2.70
void
g_tree_destroy (GTree *tree
);
Removes all keys and values from the GTree and decreases its
reference count by one. If keys and/or values are dynamically
allocated, you should either free them first or create the GTree
using g_tree_new_full()
. In the latter case the destroy functions
you supplied will be called on all keys and values before destroying
the GTree.
typedef struct _GTree GTree;
The GTree struct is an opaque data structure representing a balanced binary tree. It should be accessed only by using the following functions.