Page MenuHomeFreeBSD
Differential D25480 Diff 74847 head/share/man/man3/tree.3

Changeset View

Standalone View

View Options

head/share/man/man3/tree.3

Show First 20 Lines • Show All 93 Lines • ▼ Show 20 Lines
.Nm RB_FOREACH_SAFE , .Nm RB_FOREACH_SAFE ,
.Nm RB_FOREACH_REVERSE , .Nm RB_FOREACH_REVERSE ,
.Nm RB_FOREACH_REVERSE_FROM , .Nm RB_FOREACH_REVERSE_FROM ,
.Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_FOREACH_REVERSE_SAFE ,
.Nm RB_INIT , .Nm RB_INIT ,
.Nm RB_INSERT , .Nm RB_INSERT ,
.Nm RB_REMOVE , .Nm RB_REMOVE ,
.Nm RB_REINSERT .Nm RB_REINSERT
.Nd "implementations of splay and red-black trees" .Nd "implementations of splay and rank-balanced (wavl) trees"
.Sh SYNOPSIS .Sh SYNOPSIS
.In sys/tree.h .In sys/tree.h
.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
.Fn SPLAY_GENERATE NAME TYPE FIELD CMP .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
.Fn SPLAY_ENTRY TYPE .Fn SPLAY_ENTRY TYPE
.Fn SPLAY_HEAD HEADNAME TYPE .Fn SPLAY_HEAD HEADNAME TYPE
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head" .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
▲ Show 20 Lines • Show All 79 Lines • ▼ Show 20 Lines
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
.Sh DESCRIPTION .Sh DESCRIPTION
These macros define data structures for different types of trees: These macros define data structures for different types of trees:
splay trees and red-black trees. splay trees and rank-balanced (wavl) trees.
.Pp .Pp
In the macro definitions, In the macro definitions,
.Fa TYPE .Fa TYPE
is the name tag of a user defined structure that must contain a field of type is the name tag of a user defined structure that must contain a field of type
.Vt SPLAY_ENTRY , .Vt SPLAY_ENTRY ,
or or
.Vt RB_ENTRY , .Vt RB_ENTRY ,
named named
▲ Show 20 Lines • Show All 152 Lines • ▼ Show 20 Lines
macro: macro:
.Bd -ragged -offset indent .Bd -ragged -offset indent
.Fn SPLAY_FOREACH np NAME head .Fn SPLAY_FOREACH np NAME head
.Ed .Ed
.Pp .Pp
The The
.Fn SPLAY_EMPTY .Fn SPLAY_EMPTY
macro should be used to check whether a splay tree is empty. macro should be used to check whether a splay tree is empty.
.Sh RED-BLACK TREES .Sh RANK-BALANCED TREES
A red-black tree is a binary search tree with the node color as an Rank-balanced (RB) trees are a framework for defining height-balanced
extra attribute. binary search trees, including AVL and red-black trees.
It fulfills a set of conditions: Each tree node has an associated rank.
.Bl -enum -offset indent Balance conditions are expressed by conditions on the differences in
.It rank between any node and its children.
Every search path from the root to a leaf consists of the same number of Rank differences are stored in each tree node.
black nodes.
.It
Each red node (except for the root) has a black parent.
.It
Each leaf node is black.
.El
.Pp .Pp
Every operation on a red-black tree is bounded as The balance conditions implemented by the RB macros lead to weak AVL
.Fn O "lg n" . (wavl) trees, which combine the best aspects of AVL and red-black
The maximum height of a red-black tree is trees.
.Fn 2lg "n + 1" . Wavl trees rebalance after an insertion in the same way AVL trees do,
with the same worst-case time as red-black trees offer, and with
better balance in the resulting tree.
Wavl trees rebalance after a removal in a way that requires less
restructuring, in the worst case, than either AVL or red-black trees
do. Removals can lead to a tree almost as unbalanced as a red-black
tree; insertions lead to a tree becoming as balanced as an AVL tree.
.Pp .Pp
A red-black tree is headed by a structure defined by the A rank-balanced tree is headed by a structure defined by the
.Fn RB_HEAD .Fn RB_HEAD
macro. macro.
A A
structure is declared as follows: structure is declared as follows:
.Bd -ragged -offset indent .Bd -ragged -offset indent
.Fn RB_HEAD HEADNAME TYPE .Fn RB_HEAD HEADNAME TYPE
.Va head ; .Va head ;
.Ed .Ed
▲ Show 20 Lines • Show All 88 Lines • ▼ Show 20 Lines
The compare The compare
function defines the order of the tree elements. function defines the order of the tree elements.
.Pp .Pp
The The
.Fn RB_INIT .Fn RB_INIT
macro initializes the tree referenced by macro initializes the tree referenced by
.Fa head . .Fa head .
.Pp .Pp
The red-black tree can also be initialized statically by using the The rank-balanced tree can also be initialized statically by using the
.Fn RB_INITIALIZER .Fn RB_INITIALIZER
macro like this: macro like this:
.Bd -ragged -offset indent .Bd -ragged -offset indent
.Fn RB_HEAD HEADNAME TYPE .Fn RB_HEAD HEADNAME TYPE
.Va head .Va head
= =
.Fn RB_INITIALIZER &head ; .Fn RB_INITIALIZER &head ;
.Ed .Ed
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines
in a forward or reverse direction respectively. in a forward or reverse direction respectively.
The head pointer is not required. The head pointer is not required.
The pointer to the node from where to resume the traversal The pointer to the node from where to resume the traversal
should be passed as their last argument, should be passed as their last argument,
and will be overwritten to provide safe traversal. and will be overwritten to provide safe traversal.
.Pp .Pp
The The
.Fn RB_EMPTY .Fn RB_EMPTY
macro should be used to check whether a red-black tree is empty. macro should be used to check whether a rank-balanced tree is empty.
.Pp .Pp
The The
.Fn RB_REINSERT .Fn RB_REINSERT
macro updates the position of the element macro updates the position of the element
.Fa elm .Fa elm
in the tree. in the tree.
This must be called if a member of a This must be called if a member of a
.Nm tree .Nm tree
is modified in a way that affects comparison, such as by modifying is modified in a way that affects comparison, such as by modifying
a node's key. a node's key.
This is a lower overhead alternative to removing the element This is a lower overhead alternative to removing the element
and reinserting it again. and reinserting it again.
.Sh EXAMPLES .Sh EXAMPLES
The following example demonstrates how to declare a red-black tree The following example demonstrates how to declare a rank-balanced tree
holding integers. holding integers.
Values are inserted into it and the contents of the tree are printed Values are inserted into it and the contents of the tree are printed
in order. in order.
Lastly, the internal structure of the tree is printed. Lastly, the internal structure of the tree is printed.
.Bd -literal -offset 3n .Bd -literal -offset 3n
#include <sys/tree.h> #include <sys/tree.h>
#include <err.h> #include <err.h>
#include <stdio.h> #include <stdio.h>
▲ Show 20 Lines • Show All 99 Lines • ▼ Show 20 Lines
and and
.Fn SPLAY_REMOVE .Fn SPLAY_REMOVE
return the pointer to the removed element otherwise they return return the pointer to the removed element otherwise they return
.Dv NULL .Dv NULL
to indicate an error. to indicate an error.
.Sh SEE ALSO .Sh SEE ALSO
.Xr arb 3 , .Xr arb 3 ,
.Xr queue 3 .Xr queue 3
.Rs
.%A "Bernhard Haeupler"
.%A "Siddhartha Sen"
.%A "Robert E. Tarjan"
.%T "Rank-Balanced Trees"
.%U "http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf"
.%J "ACM Transactions on Algorithms"
.%V "11"
.%N "4"
.%D "June 2015"
.Re
.Sh HISTORY .Sh HISTORY
The tree macros first appeared in The tree macros first appeared in
.Fx 4.6 . .Fx 4.6 .
.Sh AUTHORS .Sh AUTHORS
The author of the tree macros is The author of the tree macros is
.An Niels Provos . .An Niels Provos .