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 balanced binary search tree in which each | ||||
extra attribute. | tree node has an integer rank, null nodes have rank -1, and rules set | ||||
It fulfills a set of conditions: | limits on the differences between the ranks of a node and its | ||||
children. | |||||
alc: Can you define "rank" for trees in a sentence? I don't think that it's a familiar concept for… | |||||
Nodes store rank differences, not ranks. | |||||
alcUnsubmitted Not Done Inline ActionsThe motivation for this sentence is unclear. alc: The motivation for this sentence is unclear. | |||||
.Pp | |||||
Different rules on rank differences define different sorts of balanced | |||||
trees, including "red-black" and "AVL" trees. | |||||
alcUnsubmitted 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. | |||||
The set of conditions applied here are the "weak AVL" or "wavl" | |||||
conditions: | |||||
.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 0. | ||||
.It | |||||
Each leaf node is black. | |||||
.El | .El | ||||
Wavl trees are a hybrid of AVL and red-black trees, and combine the | |||||
good properties of both. | |||||
A wavl tree built from insertions alone has the same structure as an | |||||
AVL tree, and thus a smaller average search time than a red-black | |||||
tree, in the worst case. | |||||
A red-black tree built by inserting an ascending sequence of nodes | |||||
into an empty tree has twice the height as an AVL or a wavl tree built | |||||
the same way. | |||||
alcUnsubmitted Not Done Inline Actions"For example, ... alc: "For example, ... | |||||
Removing a node from a wavl tree takes no more than two tree | |||||
rotations, where red-black node removal can require three rotations | |||||
and AVL removal can require O(log n) rotations. | |||||
.Pp | .Pp | ||||
Every operation on a red-black tree is bounded as | Every operation on a wavl tree with n nodes, built from m insertions | ||||
and m-n removals 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 min(2lg "n+1", 1.44lg "m+1"). | ||||
alcUnsubmitted 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? | |||||
Not Done Inline Actions"become" -> "becoming" alc: "become" -> "becoming" | |||||
.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 | ||||
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 | ||||
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 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 | ||||
.Rs | |||||
.%A "Bernhard Haeupler" | |||||
.%A "Siddhartha Sen" | |||||
.%A "Robert E. Tarjan" | |||||
.%T "Rank-Balanced Trees" | |||||
Not Done Inline ActionsAdd: .%J "ACM Transactions on Algorithms" alc: Add:
.%J "ACM Transactions on Algorithms"
.%V "11"
.%N "4"
.%D "June 2015" | |||||
.%U "http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf" | |||||
.Re | |||||
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 | ||||
.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.