# Red/Black Tree API

- [API reference](https://docs.qualcomm.com/doc/80-41102-2/topic/_doxygen_rst_file__doxygen_sources_include_le_redBlackTree_h.html#file-le-redblacktree-h)

A Red-Black Tree is a data structure representing a self-balancing binary search tree. Tree consists of nodes maintaining links to the parent, left and right nodes. Advantage over a linked-list is faster search based on the key comparison. Advantage over a hashtable is simplified memory management (no additional allocation within the library), better scalability up and down, and possibility to easily iterate the set in ascending/descending order.

## Creating and Initializing Red-Black Trees

To create and initialize an RB Tree the user must create an [le\_rbtree\_Tree\_t](https://docs.qualcomm.com/doc/80-41102-2/topic/struct_a00848.html#Documentationa00848) typed object and initialize it using [le\_rbtree\_InitTree()](https://docs.qualcomm.com/doc/80-41102-2/topic/function_a00101_1accb91a387364f9e762c2c394e650af13.html#Documentationa00101_1accb91a387364f9e762c2c394e650af13) routine. At this time the user has to provide a pointer to the comparator function, that provides a way to perform a comparison between objects. The tree **must** be initialized before it can be used.

// provide the comparator function
    static int compare(const void* a, const void* b)
    {
       // return negative, 0, or positive value
    }
    
    // Create the tree.
    le_rbtree_Tree_t MyTree;
    
    // Initialize the tree.
    le_rbtree_InitTree(&MyTree, compare);
    Copy to clipboard

**Elements of  MUST NOT be accessed directly by the user.**

## Creating and Accessing Nodes

Nodes can contain any data in any format and is defined and created by the user. The only requirement for nodes is that it must contain an `le_rbtree_Node_t` link member. The link member must be initialized by calling `le_rbtree_InitNode()` before it is added to the tree; at this time, pointer to the key of this object must be provided. The node can be added to the tree using the function `le_rbtree_Insert()`.

// The node may be defined like this.
    typedef struct
    {
         MyKeyType key;
         dataType someUserData;
         ...
         le_rbtree_Node_t myLink;
    }
    MyNodeClass_t;
    
    void foo (void)
    {
        // Create the node.  Get the memory from a memory pool previously created.
        MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
    
        // Initialize the node's link.
        le_rbtree_InitNode(&MyTree, &myNodePtr->key);
    
        // Add the node to the tree by passing in the node's link.
        le_rbtree_Insert(&MyTree, &myNodePtr->myLink);
    }
    Copy to clipboard

## Finding node in a Tree

To find the node in the tree by the given key, use `le_rbtree_Find()` function. To obtain the object itself, use the `CONTAINER_OF` macro defined in le\_basics.h. Here’s a code sample using `CONTAINER_OF` to obtain the node:

// declare and initialize the key
    MyKeyType key = <...>;
    // Assuming MyTree has been created and initialized and is not empty.
    le_rbtree_Node_t* linkPtr = le_rbtree_Find(&MyTree, &key);
    
    // Now we have the link but still need the node to access user data.
    // We use CONTAINER_OF to get a pointer to the node given the node's link.
    if (linkPtr != NULL)
    {
        MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
    }
    Copy to clipboard

The user is responsible for creating and freeing memory for all nodes; the RB Tree module only manages the links in the nodes. The node must be removed from all trees before its memory can be freed.

**The elements of  MUST NOT be accessed directly by the user.**

## Traversing a Tree

Tree can be traversed in an ascending or descending order (in the sense of greater/lesser provided by the comparator function):

// Ascending order
    le_rbtree_Node_t* linkPtr;
    for (linkPtr = le_rbtree_GetFirst(&MyTree);
         linkPtr != NULL;
         linkPtr = le_rbtree_GetNext(&MyTree, linkPtr))
    {
        MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
    }
    
    // Descending order
    le_rbtree_Node_t* linkPtr;
    for (linkPtr = le_rbtree_GetLast(&MyTree);
         linkPtr != NULL;
         linkPtr = le_rbtree_GetPrev(&MyTree, linkPtr))
    {
        MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
    }
    Copy to clipboard

## Removing node from a Tree

To remove a node from a Tree, use [le\_rbtree\_RemoveByKey()](https://docs.qualcomm.com/doc/80-41102-2/topic/function_a00101_1a3948cb60518077253a1bc15c5ea2b714.html#Documentationa00101_1a3948cb60518077253a1bc15c5ea2b714) function:

// Remove the node
    le_rbtree_RemoveByKey(&MyTree, &(myNodePtr->key));
    // Free the object
    le_mem_Release(myNodePtr);
    Copy to clipboard

or [le\_rbtree\_Remove()](https://docs.qualcomm.com/doc/80-41102-2/topic/function_a00101_1ab80711e4cb2c43ca1f60a398805a9834.html#Documentationa00101_1ab80711e4cb2c43ca1f60a398805a9834) function:

// Remove the node
    le_rbtree_Remove(&MyTree, &(myNodePtr->myLink));
    // Free the object
    le_mem_Release(myNodePtr);
    Copy to clipboard

## Thread Safety and Re-Entrancy

All Red-Black Tree function calls are re-entrant and thread safe themselves, but if the nodes and/or Tree object are shared by multiple threads, explicit steps must be taken to maintain mutual exclusion of access. If you’re accessing the same tree from multiple threads, you *must* use a [mutex](https://docs.qualcomm.com/doc/80-41102-2/topic/page_c_mutex.html#Documentationa01163) or some other form of thread synchronization to ensure only one thread accesses the tree at a time.

Copyright (C) Sierra Wireless Inc.

Last Published: Jul 29, 2026

[Previous Topic
Process API](https://docs.qualcomm.com/bundle/publicresource/80-41102-2/topics/process.md) [Next Topic
Call Stack Backtrace Functionality](https://docs.qualcomm.com/bundle/publicresource/80-41102-2/topics/call_stack_backtrace.md)