Changeset View
Changeset View
Standalone View
Standalone View
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 | A rank-balanced tree is a binary search tree with an integer | ||||
extra attribute. | rank-difference as an attribute of each pointer from parent to child. | ||||
It fulfills a set of conditions: | The sum of the rank-differences on any path from a node down to null | ||||
is the same, and defines the rank of that node. The rank of the null | |||||
alc: Can you define "rank" for trees in a sentence? I don't think that it's a familiar concept for… | |||||
node is 0. | |||||
Not Done Inline ActionsThe motivation for this sentence is unclear. alc: The motivation for this sentence is unclear. | |||||
.Pp | |||||
Different additional conditions define different sorts of balanced | |||||
trees, including "red-black" and "AVL" trees. The set of conditions | |||||
Not Done Inline ActionsI think that this sentence belongs in the previous paragraph, probably as the second sentence. alc: I think that this sentence belongs in the previous paragraph, probably as the second sentence. | |||||
applied here are the "weak-AVL" conditions of Haeupler, Sen and | |||||
Tarjan: | |||||
.Bl -enum -offset indent | .Bl -enum -offset indent | ||||
.It | .It | ||||
Every search path from the root to a leaf consists of the same number of | Every rank-difference is 1 or 2. | ||||
black nodes. | |||||
.It | .It | ||||
Each red node (except for the root) has a black parent. | The rank of any leaf is 1. | ||||
.It | |||||
Each leaf node is black. | |||||
.El | .El | ||||
.Pp | .Pp | ||||
Every operation on a red-black tree is bounded as | Every operation on a rank-balanced tree is bounded as | ||||
.Fn O "lg n" . | .Fn O "lg n" . | ||||
The maximum height of a red-black tree is | The maximum height of a rank-balanced tree is | ||||
.Fn 2lg "n + 1" . | .Fn 2lg "n + 1" . | ||||
.Pp | .Pp | ||||
Not Done Inline ActionsFor most people who read this, you will need to explain what this means. Is this a good thing? alc: For most people who read this, you will need to explain what this means. Is this a good thing? | |||||
A red-black tree is headed by a structure defined by the | A rank-balanced tree is headed by a structure defined by the | ||||
Done Inline ActionsI would include a sentence clarifying that wavl trees can be used for the same purposes as red-black trees. markj: I would include a sentence clarifying that wavl trees can be used for the same purposes as red… | |||||
.Fn RB_HEAD | .Fn RB_HEAD | ||||
Not Done Inline Actions"For example, ... alc: "For example, ... | |||||
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 | ||||
.Pp | .Pp | ||||
where | where | ||||
Not Done Inline Actions"become" -> "becoming" alc: "become" -> "becoming" | |||||
.Fa HEADNAME | .Fa HEADNAME | ||||
is the name of the structure to be defined, and struct | is the name of the structure to be defined, and struct | ||||
.Fa TYPE | .Fa TYPE | ||||
is the type of the elements to be inserted into the tree. | is the type of the elements to be inserted into the tree. | ||||
.Pp | .Pp | ||||
The | The | ||||
.Fn RB_ENTRY | .Fn RB_ENTRY | ||||
macro declares a structure that allows elements to be connected in the tree. | macro declares a structure that allows elements to be connected in the tree. | ||||
▲ Show 20 Lines • Show All 78 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 98 Lines • ▼ Show 20 Lines | |||||
.Fn RB_REMOVE | .Fn RB_REMOVE | ||||
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 | ||||
Done Inline ActionsYou might consider adding a link to the original paper here. See share/man/man4/cc_cubic.4 for a formatting example. markj: You might consider adding a link to the original paper here. See share/man/man4/cc_cubic.4 for… | |||||
.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 | ||||
Not Done Inline ActionsAdd: .%J "ACM Transactions on Algorithms" alc: Add:
.%J "ACM Transactions on Algorithms"
.%V "11"
.%N "4"
.%D "June 2015" | |||||
.An Niels Provos . | .An Niels Provos . |
Can you define "rank" for trees in a sentence? I don't think that it's a familiar concept for most people who would read this.