RBTREE(3) | Library Functions Manual | RBTREE(3) |
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
Standard C Library (libc, -lc)
#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);
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:
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).
rbto_compare_nodes_fn rbto_compare_nodes; rbto_compare_key_fn rbto_compare_key; size_t rbto_node_offset; void *rbto_context;
rbtree
interface are meant to
take pointers directly to the rb_node_t
member.)rb_tree_init
(rbt,
ops)rb_tree_init
() always succeeds.rb_tree_insert_node
(rbt,
rb)rb_tree_remove_node
(rbt,
rb)rb_tree_find_node
(rbt,
key)NULL
. Otherwise, return the matching node.rb_tree_find_node_geq
(rbt,
key)NULL
.rb_tree_find_node_leq
(rbt,
key)NULL
.rb_tree_iterate
(rbt,
rb, direction)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)NULL
, 0 is
returned.RB_TREE_MIN
(rbt)NULL
if rbt is
empty.RB_TREE_MAX
(rbt)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.The rbtree
interface first appeared in
NetBSD 6.0.
Matt Thomas
<matt@NetBSD.org>
wrote rbtree
.
Niels Provos
<provos@citi.umich.edu>
wrote the tree(3) manual page. Portions
of this page derive from that page.
August 29, 2016 | macOS 14.6 |