Page MenuHomeFreeBSD
Files F143186734

D25480.id73750.diff
No OneTemporary
Actions

D25480.id73750.diff
View Options

Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ share/man/man3/tree.3
@@ -99,7 +99,7 @@
.Nm RB_INSERT ,
.Nm RB_REMOVE ,
.Nm RB_REINSERT
-.Nd "implementations of splay and red-black trees"
+.Nd "implementations of splay and rank-balanced (wavl) trees"
.Sh SYNOPSIS
.In sys/tree.h
.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
@@ -195,7 +195,7 @@
.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
.Sh DESCRIPTION
These macros define data structures for different types of trees:
-splay trees and red-black trees.
+splay trees and rank-balanced (wavl) trees.
.Pp
In the macro definitions,
.Fa TYPE
@@ -364,26 +364,30 @@
The
.Fn SPLAY_EMPTY
macro should be used to check whether a splay tree is empty.
-.Sh 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:
+.Sh RANK-BALANCED TREES
+A rank-balanced tree is a binary search tree with an integer
+rank-difference as an attribute of each pointer from parent to child.
+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
+node is -1.
+.Pp
+Different additional conditions define different sorts of balanced
+trees, including "red-black" and "AVL" trees. The set of conditions
+applied here are the "weak-AVL" conditions of Haeupler, Sen and
+Tarjan:
.Bl -enum -offset indent
.It
-Every search path from the root to a leaf consists of the same number of
-black nodes.
+Every rank-difference is 1 or 2.
.It
-Each red node (except for the root) has a black parent.
-.It
-Each leaf node is black.
+The rank of any leaf is 1.
.El
.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" .
-The maximum height of a red-black tree is
+The maximum height of a rank-balanced tree is
.Fn 2lg "n + 1" .
.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
macro.
A
@@ -488,7 +492,7 @@
macro initializes the tree referenced by
.Fa head .
.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
macro like this:
.Bd -ragged -offset indent
@@ -567,7 +571,7 @@
.Pp
The
.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
The
.Fn RB_REINSERT
@@ -581,7 +585,7 @@
This is a lower overhead alternative to removing the element
and reinserting it again.
.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.
Values are inserted into it and the contents of the tree are printed
in order.

File Metadata

Mime Type
text/plain
Expires
Wed, Jan 28, 3:34 AM (7 h, 13 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
28062866
Default Alt Text
D25480.id73750.diff (2 KB)

Event Timeline