平衡红黑树
当有序容器在运行时可能变得很大时，链表的搜索开销会成为问题。为此，Zephyr 提供了平衡树实现：对于大小为 N 的树，搜索和删除操作的时间复杂度上界为 O(log2(N))。该实现采用多种学术资料中描述的传统红黑树。
红黑树的管理结构体 rbtree 可以放在任意用户可访问的内存中。首次使用前，其内容应全部清零，不需要专门的初始化 API。
链表中节点的位置是显式的，而红黑树中节点的顺序必须由用户提供的判定函数确定。在执行任何树操作前，应将 rb_lessthan_t() 类型的函数赋给 rbtree 结构体的 lessthan_fn 字段。顾名思义，如果按照期望的顺序，第一个节点参数“小于”第二个，该函数应返回布尔值 True。注意，不允许出现“相等”：树内节点必须具有唯一、固定的顺序，算法才能正确工作。
与 slist 和 dlist 容器一样，红黑树中的节点由 rbnode 结构体表示，位于用户管理的内存中，通常嵌入被树跟踪的数据结构。与链表不同，rbnode 内的数据完全不透明。用户无法提取二叉树的拓扑结构，像操作链表那样“手动”遍历。
可以使用 rb_insert() 插入节点，使用 rb_remove() 删除节点。按照比较函数定义的顺序，rb_get_min() 和 rb_get_max() 分别提供对树中“第一个”和“最后一个”节点的访问。判定函数 rb_contains() 在给定节点指针确实对应树中元素时返回布尔值 True。如前所述，这些函数的时间复杂度均保证不超过树大小的对数级。
枚举红黑树全部元素有两种机制。第一种是 rb_walk()，采用简单的回调实现：调用者指定一个 C 函数指针和一个传给它的无类型参数，树代码按顺序对每个节点调用该函数。优点是实现简单，代价是用户使用 API 时略显繁琐，与 ISO C 的 bsearch() 类似。不过，它采用递归实现，因此在禁止递归等无界栈使用方式的环境中不一定可用。
还提供了 RB_FOR_EACH 迭代器，与链表的类似 API 一样，使用嵌套代码块代替回调，以更自然的方式遍历。它不使用递归，但默认需要对数大小的栈空间；如需避免动态分配，也可以配置为使用固定的、按最大需求确定大小的缓冲区。与链表一样，它还提供 RB_FOR_EACH_CONTAINER 变体，枚举时使用包含节点的结构体指针，而非原始节点指针。
树的内部实现
如前所述，Zephyr 的 rbtree 实现采用学术资料中常见的传统红黑树。算法底层细节遵循既有惯例，不在本文讨论范围内。这里只介绍 Zephyr 实现中特有或值得注意的细节。
树保证的核心不变量是：从根节点到任意叶节点的路径长度，不超过到其他任意叶节点路径长度的两倍。为此，每个节点关联一位“颜色”信息，非红即黑，并强制规定红节点不能有红色子节点：从任意叶节点到根的路径上，黑节点数量必须相同，额外的红节点数量不能超过该数量。修改树后，会通过一组旋转规则进行“修复”，维持此约束。
从概念上说，这些旋转建立在一个“交换”两个节点位置的原语之上。典型实现只需交换节点内部的“data”指针，但 Zephyr 的 rbnode 是侵入式节点，无法这样处理。Zephyr 必须使用更复杂的代码应对边界情况，例如其中一个被交换节点是根节点，或两个节点已存在父子关系。
Zephyr 红黑树的 rbnode 结构体仅包含两个指针，表示二叉树节点的“左”和“右”子节点。不过，修改后为重新平衡而遍历树时，通常还需要从节点“向上”遍历。业界的红黑树实现常为此存储第三个“父节点”指针。Zephyr 在向下遍历时于局部构建节点指针“栈”，并在修改时相应更新，从而避免这一需求。因此，Zephyr 红黑树的运行时存储开销不超过 dlist。
每个节点仅用两个指针、且无需任何内存分配 API 就能工作的平衡树数据结构，在业界较为少见，也是 Zephyr 实现的一个特色。