---
name: "rbtree"
section: "3"
platform: "macos"
package: "Libc"
version: "1752.120.2"
release: "macOS 26.5"
platforms: ["macos"]
url: "https://new.carta.tech/rbtree"
---

# rbtree(3)

red-black tree

## NAME

**rbtree**, **rb\_tree\_init**, **rb\_tree\_insert\_node**, **rb\_tree\_remove\_node**, **rb\_tree\_find\_node**, **rb\_tree\_find\_node\_geq**, **rb\_tree\_find\_node\_leq**, **rb\_tree\_iterate**, **rb\_tree\_count**, **RB\_TREE\_MIN**, **RB\_TREE\_MAX**, **RB\_TREE\_FOREACH**, **RB\_TREE\_FOREACH\_SAFE**, **RB\_TREE\_FOREACH\_REVERSE**, **RB\_TREE\_FOREACH\_REVERSE\_SAFE** – red-black tree

## LIBRARY

Standard C Library (libc, -lc)

## SYNOPSIS

**#include \<sys/rbtree.h\>**

*void*\

**rb\_tree\_init**(*rb\_tree\_t \*rbt*, *const rb\_tree\_ops\_t \*ops*);

*void* *\**\

**rb\_tree\_insert\_node**(*rb\_tree\_t \*rbt*, *void \*rb*);

*void*\

**rb\_tree\_remove\_node**(*rb\_tree\_t \*rbt*, *void \*rb*);

*void* *\**\

**rb\_tree\_find\_node**(*rb\_tree\_t \*rbt*, *const void \*key*);

*void* *\**\

**rb\_tree\_find\_node\_geq**(*rb\_tree\_t \*rbt*, *const void \*key*);

*void* *\**\

**rb\_tree\_find\_node\_leq**(*rb\_tree\_t \*rbt*, *const void \*key*);

*void* *\**\

**rb\_tree\_iterate**(*rb\_tree\_t \*rbt*, *void \*rb*, *const unsigned int direction*);

*size\_t*\

**rb\_tree\_count**(*rb\_tree\_t \*rbt*);

*void* *\**\

**RB\_TREE\_MIN**(*rb\_tree\_t \*rbt*);

*void* *\**\

**RB\_TREE\_MAX**(*rb\_tree\_t \*rbt*);

**RB\_TREE\_FOREACH**(*void \*rb*, *rb\_tree\_t \*rbt*);

**RB\_TREE\_FOREACH\_SAFE**(*void \*rb*, *rb\_tree\_t \*rbt*, *void \*tmp*);

**RB\_TREE\_FOREACH\_REVERSE**(*void \*rb*, *rb\_tree\_t \*rbt*);

**RB\_TREE\_FOREACH\_REVERSE\_SAFE**(*void \*rb*, *rb\_tree\_t \*rbt*, *void \*tmp*);

## DESCRIPTION

**rbtree** provides red-black trees. A red-black tree is a binary search tree with the node color as an extra attribute. It fulfills a set of conditions:

1. Every search path from the root to a leaf consists of the same number of black nodes.

2. Each red node (except for the root) has a black parent.

3. Each leaf node is black.

Every operation on a red-black tree is bounded as O(lg n). The maximum height of a red-black tree is 2lg (n+1).

## TYPES

- *rb\_tree\_t*

  A red-black tree.

- *typedef* *signed* *int* *(\** *rbto\_compare\_nodes\_fn)(void* *\*context,* *const* *void* *\*node1,* *const* *void* *\*node2);*

  The node-comparison function. Defines an ordering on nodes. Returns a negative value if the first node *node1* precedes the second node *node2*. Returns a positive value if the first node *node1* follows the second node *node2*. Returns 0 if the first node *node1* and the second node *node2* are identical according to the ordering.

- *typedef* *signed* *int* *(\** *rbto\_compare\_key\_fn)(void* *\*context,* *const* *void* *\*node,* *const* *void* *\*key);*

  The node-key comparison function. Defines the order of nodes and keys. Returns a negative value if the node *node* precedes the key *key*. Returns a positive value if the node *node* follows the key *key*. Returns 0 if the node *node* is identical to the key *key* according to the ordering.

- *rb\_tree\_ops\_t*

  Defines the function for comparing two nodes in the same tree, the function for comparing a node in the tree with a key, the offset of member *rb\_node\_t* within the node type, and the opaque context pointer passed to the comparison functions. Members of *rb\_tree\_ops\_t* are

  ```
          rbto_compare_nodes_fn rbto_compare_nodes;
          rbto_compare_key_fn rbto_compare_key;
          size_t rbto_node_offset;
          void *rbto_context;
  ```

- *rb\_node\_t*

  A node in a red-black tree has this structure as a member. The offset of the *rb\_node\_t* member in the caller's node structure should be provided as *rbto\_node\_offset*. (None of the functions in the **rbtree** interface are meant to take pointers directly to the *rb\_node\_t* member.)

## FUNCTIONS

- **rb\_tree\_init**(*rbt*, *ops*)

  Initialize the red-black tree *rbt*. Let the comparison functions given by *ops* define the order of nodes in the tree for the purposes of insertion, search, and iteration. **rb\_tree\_init**() always succeeds.

- **rb\_tree\_insert\_node**(*rbt*, *rb*)

  Insert the node *rb* into the tree *rbt*. Return inserted node on success, already existing node on failure.

- **rb\_tree\_remove\_node**(*rbt*, *rb*)

  Remove the node *rb* from the tree *rbt*.

- **rb\_tree\_find\_node**(*rbt*, *key*)

  Search the tree *rbt* for a node exactly matching *key*. If no such node is in the tree, return NULL. Otherwise, return the matching node.

- **rb\_tree\_find\_node\_geq**(*rbt*, *key*)

  Search the tree *rbt* for a node that exactly matches *key* and return it. If no such node is present, return the first node following *key* or, if no such node is in the tree, return NULL.

- **rb\_tree\_find\_node\_leq**(*rbt*, *key*)

  Search the tree *rbt* for a node that exactly matches *key* and return it. If no such node is present, return the first node preceding *key* or, if no such node is in the tree, return NULL.

- **rb\_tree\_iterate**(*rbt*, *rb*, *direction*)

  If *direction* is RB\_DIR\_LEFT, return the node in the tree *rbt* immediately preceding the node *rb* or, if *rb* is NULL, return the first node in *rbt* or, if the tree is empty, return NULL.

  If *direction* is RB\_DIR\_RIGHT, return the node in the tree *rbt* immediately following the node *rb* or, if *rb* is NULL, return the last node in *rbt* or, if the tree is empty, return NULL.

- **rb\_tree\_count**(*rbt*)

  Return the number of nodes in the tree *rbt*. If *rbt* is NULL, 0 is returned.

- **RB\_TREE\_MIN**(*rbt*)

  Return the first node in *rbt*, i.e. the node with the least key, or NULL if *rbt* is empty.

- **RB\_TREE\_MAX**(*rbt*)

  Return the last node in *rbt*, i.e. the node with the greatest key, or NULL if *rbt* is empty.

- **RB\_TREE\_FOREACH**(*rb*, *rbt*)

  **RB\_TREE\_FOREACH** is a macro to be used in the place of a for header preceding a statement to traverse the nodes in *rbt* from least to greatest, assigning *rb* to each node in turn and executing the statement.

- **RB\_TREE\_FOREACH\_SAFE**(*rb*, *rbt*, *tmp*)

  **RB\_TREE\_FOREACH\_SAFE** is a macro to be used like **RB\_TREE\_FOREACH** but which uses a temporary variable to permit safe modification or deletion of *rb* in the body of the loop.

- **RB\_TREE\_FOREACH\_REVERSE**(*rb*, *rbt*)

  **RB\_TREE\_FOREACH\_REVERSE** is a macro to be used in the place of a for header preceding a statement to traverse the nodes in *rbt* from greatest to least, assigning *rb* to each node in turn and executing the statement.

- **RB\_TREE\_FOREACH\_REVERSE\_SAFE**(*rb*, *rbt*, *tmp*)

  **RB\_TREE\_FOREACH\_REVERSE\_SAFE** is a macro to be used like **RB\_TREE\_FOREACH\_REVERSE** but which uses a temporary variable to permit safe modification or deletion of *rb* in the body of the loop.

## SEE ALSO

[queue(3)](/queue/3.md), [tree(3)](/tree/3.md)

## HISTORY

The **rbtree** interface first appeared in NetBSD 6.0.

## AUTHORS

Matt Thomas ⟨*matt@NetBSD.org*⟩ wrote **rbtree**.

Niels Provos ⟨*provos@citi.umich.edu*⟩ wrote the [tree(3)](/tree/3.md) manual page. Portions of this page derive from that page.