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 0.
+.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.