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.
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -36,7 +36,7 @@
 
 /*
  * This file defines data structures for different types of trees:
- * splay trees and red-black trees.
+ * splay trees and rank-balanced trees.
  *
  * A splay tree is a self-organizing data structure.  Every operation
  * on the tree causes a splay to happen.  The splay moves the requested
@@ -50,15 +50,24 @@
  * and n inserts on an initially empty tree as O((m + n)lg n).  The
  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
  *
- * A red-black tree is a binary search tree with the node color as an
- * extra attribute.  It fulfills a set of conditions:
- *	- every search path from the root to a leaf consists of the
- *	  same number of black nodes,
- *	- each red node (except for the root) has a black parent,
- *	- each leaf node is black.
+ * 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.
  *
- * Every operation on a red-black tree is bounded as O(lg n).
- * The maximum height of a red-black tree is 2lg (n+1).
+ * 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:
+ *	- every rank-difference is 1 or 2.
+ *	- the rank of any leaf is 1.
+ *
+ * For historical reasons, rank differences that are even are associated
+ * with the color red (Rank-Even-Difference), and the child that a red edge
+ * points to is called a red child.
+ *
+ * Every operation on a rank-balanced tree is bounded as O(lg n).
+ * The maximum height of a rank-balanced tree is 2lg (n+1).
  */
 
 #define SPLAY_HEAD(name, type)						\
@@ -294,7 +303,7 @@
 	     (x) != NULL;						\
 	     (x) = SPLAY_NEXT(name, head, x))
 
-/* Macros that define a red-black tree */
+/* Macros that define a rank-balanced tree */
 #define RB_HEAD(name, type)						\
 struct name {								\
 	struct type *rbh_root; /* root of the tree */			\
@@ -422,7 +431,8 @@
 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\
 	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
-	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
+	attr void name##_RB_REMOVE_COLOR(struct name *,			\
+	    struct type *, struct type *)
 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\
 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
 #define RB_PROTOTYPE_INSERT(name, type, attr)				\
@@ -464,123 +474,141 @@
 attr void								\
 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 {									\
-	struct type *gparent, *parent;					\
+	struct type *child, *parent;					\
 	while ((parent = RB_PARENT(elm, field)) != NULL) {		\
-		if (RB_LEFT(parent, field) == elm)			\
-			RB_FLIP_LEFT(parent, field);			\
-		else							\
+		if (RB_LEFT(parent, field) == elm) {			\
+			if (RB_RED_LEFT(parent, field)) {		\
+				RB_FLIP_LEFT(parent, field);		\
+				return;					\
+			}						\
 			RB_FLIP_RIGHT(parent, field);			\
-		if ((gparent = RB_PARENT(parent, field)) == NULL)	\
-			break;						\
-		if (RB_RED_LEFT(gparent, field) &&			\
-		    RB_RED_RIGHT(gparent, field)) {			\
-			RB_FLIP_LEFT(gparent, field);			\
-			RB_FLIP_RIGHT(gparent, field);			\
-			elm = gparent;					\
-			continue;					\
-		}							\
-		if (RB_RED_LEFT(gparent, field) &&			\
-		    parent == RB_LEFT(gparent, field)) { 		\
-			if (RB_RIGHT(parent, field) == elm) {		\
-				RB_ROTATE_LEFT(head, parent, elm, field);\
+			if (RB_RED_RIGHT(parent, field)) {		\
+				elm = parent;				\
+				continue;				\
+			}						\
+			if (RB_RED_RIGHT(elm, field))			\
+				RB_FLIP_RIGHT(elm, field);		\
+			else {						\
+				RB_ROTATE_LEFT(head, elm, child, field);\
+				RB_FLIP_LEFT(elm, field);		\
+				if (RB_RED_LEFT(child, field)) {	\
+					RB_FLIP_LEFT(child, field);	\
+					RB_FLIP_RIGHT(elm, field);	\
+				} else if (RB_RED_RIGHT(child, field)) {\
+					RB_FLIP_RIGHT(child, field);	\
+					RB_FLIP_LEFT(parent, field);	\
+				}					\
+				elm = child;				\
+			}						\
+			RB_ROTATE_RIGHT(head, parent, elm, field);	\
+		} else {						\
+			if (RB_RED_RIGHT(parent, field)) {		\
 				RB_FLIP_RIGHT(parent, field);		\
+				return;					\
+			}						\
+			RB_FLIP_LEFT(parent, field);			\
+			if (RB_RED_LEFT(parent, field)) {		\
+				elm = parent;				\
+				continue;				\
+			}						\
+			if (RB_RED_LEFT(elm, field))			\
 				RB_FLIP_LEFT(elm, field);		\
-				parent = elm;				\
-			}						\
-			RB_ROTATE_RIGHT(head, gparent, parent, field);	\
-			RB_FLIP_LEFT(gparent, field);			\
-			RB_FLIP_RIGHT(parent, field);			\
-		} else if (RB_RED_RIGHT(gparent, field) &&		\
-		    parent == RB_RIGHT(gparent, field)) {		\
-			if (RB_LEFT(parent, field) == elm) {		\
-				RB_ROTATE_RIGHT(head, parent, elm, field);\
-				RB_FLIP_LEFT(parent, field);		\
+			else {						\
+				RB_ROTATE_RIGHT(head, elm, child, field);\
 				RB_FLIP_RIGHT(elm, field);		\
-				parent = elm;				\
+				if (RB_RED_RIGHT(child, field)) {	\
+					RB_FLIP_RIGHT(child, field);	\
+					RB_FLIP_LEFT(elm, field);	\
+				} else if (RB_RED_LEFT(child, field)) {	\
+					RB_FLIP_LEFT(child, field);	\
+					RB_FLIP_RIGHT(parent, field);	\
+				}					\
+				elm = child;				\
 			}						\
-			RB_ROTATE_LEFT(head, gparent, parent, field);	\
-			RB_FLIP_RIGHT(gparent, field);			\
-			RB_FLIP_LEFT(parent, field);			\
+			RB_ROTATE_LEFT(head, parent, elm, field);	\
 		}							\
-		break;							\
+		break;					\
 	}								\
 }
 
 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
 attr void								\
-name##_RB_REMOVE_COLOR(struct name *head, struct type *par)		\
+name##_RB_REMOVE_COLOR(struct name *head,				\
+    struct type *parent, struct type *elm)				\
 {									\
-	struct type *gpr, *sib, *nec;					\
-	RB_BOOL left_elm, left_par, red_gpr;				\
-	left_par = (RB_LEFT(par, field) == NULL);			\
-	do {								\
-		left_elm = left_par;					\
-		if (left_elm ?						\
-		    !RB_RED_RIGHT(par, field) :				\
-		    !RB_RED_LEFT(par, field)) {				\
-			gpr = RB_PARENT(par, field);			\
-			left_par = gpr != NULL &&			\
-			    RB_LEFT(gpr, field) == par;			\
-			red_gpr = gpr == NULL ?				\
-				RB_TRUE: RB_COLOR(par, field);		\
-		}							\
-		if (left_elm) {						\
-			if (RB_RED_RIGHT(par, field)) {			\
-				red_gpr = RB_TRUE;			\
-				RB_ROTATE_LEFT(head, par, gpr, field);	\
-				RB_FLIP_RIGHT(par, field);		\
-				RB_FLIP_LEFT(gpr, field);		\
+	struct type *nec, *sib;						\
+	do  {								\
+		if (RB_LEFT(parent, field) == elm) {			\
+			if (!RB_RED_LEFT(parent, field)) {		\
+				RB_FLIP_LEFT(parent, field);		\
+				return;					\
 			}						\
-			sib = RB_RIGHT(par, field);			\
-			if (RB_RED_RIGHT(sib, field)) {			\
-				if (RB_RED_LEFT(sib, field)) {		\
-					RB_FLIP_LEFT(sib, field);	\
-					RB_FLIP_RIGHT(par, field);	\
-				}					\
-				RB_FLIP_RIGHT(sib, field);		\
-			} else if (RB_RED_LEFT(sib, field)) {		\
-				RB_ROTATE_RIGHT(head, sib, nec, field);	\
+			if (RB_RED_RIGHT(parent, field)) {		\
+				RB_FLIP_RIGHT(parent, field);		\
+				elm = parent;				\
+				continue;				\
+			}						\
+			sib = RB_RIGHT(parent, field);			\
+			RB_FLIP_RIGHT(sib, field);			\
+			if (RB_RED_LEFT(sib, field) &&			\
+			    !RB_RED_RIGHT(sib, field)) {		\
 				RB_FLIP_LEFT(sib, field);		\
-				sib = nec;				\
-			} else {					\
-				RB_FLIP_RIGHT(par, field);		\
-				par = gpr;				\
+				elm = parent;				\
 				continue;				\
 			}						\
-			RB_ROTATE_LEFT(head, par, sib, field);		\
-			return;						\
+			if (RB_RED_LEFT(sib, field))			\
+				RB_FLIP_LEFT(parent, field);		\
+			if (!RB_RED_RIGHT(sib, field)) {		\
+				RB_FLIP_LEFT(parent, field);		\
+				RB_ROTATE_RIGHT(head, sib, nec, field);	\
+				if (RB_RED_RIGHT(nec, field))		\
+					RB_FLIP_LEFT(sib, field);	\
+				else					\
+					RB_FLIP_RIGHT(nec, field);	\
+				if (RB_RED_LEFT(nec, field))		\
+					RB_FLIP_RIGHT(parent, field);	\
+				else					\
+					RB_FLIP_LEFT(nec, field);	\
+				sib = nec;				\
+			}						\
+			RB_ROTATE_LEFT(head, parent, sib, field);	\
 		} else {						\
-			if (RB_RED_LEFT(par, field)) {			\
-				red_gpr = RB_TRUE;			\
-				RB_ROTATE_RIGHT(head, par, gpr, field); \
-				RB_FLIP_LEFT(par, field);		\
-				RB_FLIP_RIGHT(gpr, field);		\
+			if (!RB_RED_RIGHT(parent, field)) {		\
+				RB_FLIP_RIGHT(parent, field);		\
+				return;					\
 			}						\
-			sib = RB_LEFT(par, field);			\
-			if (RB_RED_LEFT(sib, field)) {			\
-				if (RB_RED_RIGHT(sib, field)) {		\
-					RB_FLIP_RIGHT(sib, field);	\
-					RB_FLIP_LEFT(par, field);	\
-				}					\
-				RB_FLIP_LEFT(sib, field);		\
-			} else if (RB_RED_RIGHT(sib, field)) {		\
-				RB_ROTATE_LEFT(head, sib, nec, field);	\
+			if (RB_RED_LEFT(parent, field)) {		\
+				RB_FLIP_LEFT(parent, field);		\
+				elm = parent;				\
+				continue;				\
+			}						\
+			sib = RB_LEFT(parent, field);			\
+			RB_FLIP_LEFT(sib, field);			\
+			if (RB_RED_RIGHT(sib, field) &&			\
+			    !RB_RED_LEFT(sib, field)) {			\
 				RB_FLIP_RIGHT(sib, field);		\
-				sib = nec;				\
-			} else {					\
-				RB_FLIP_LEFT(par, field);		\
-				par = gpr;				\
+				elm = parent;				\
 				continue;				\
 			}						\
-			RB_ROTATE_RIGHT(head, par, sib, field);		\
-			return;						\
+			if (RB_RED_RIGHT(sib, field))			\
+				RB_FLIP_RIGHT(parent, field);		\
+			if (!RB_RED_LEFT(sib, field)) {			\
+				RB_FLIP_RIGHT(parent, field);		\
+				RB_ROTATE_LEFT(head, sib, nec, field);	\
+				if (RB_RED_LEFT(nec, field))		\
+					RB_FLIP_RIGHT(sib, field);	\
+				else					\
+					RB_FLIP_LEFT(nec, field);	\
+				if (RB_RED_RIGHT(nec, field))		\
+					RB_FLIP_LEFT(parent, field);	\
+				else					\
+					RB_FLIP_RIGHT(nec, field);	\
+				sib = nec;				\
+			}						\
+			RB_ROTATE_RIGHT(head, parent, sib, field);	\
 		}							\
-	} while (!red_gpr);						\
-	if (gpr == NULL);						\
-	else if (left_par)						\
-		RB_FLIP_LEFT(gpr, field);				\
-	else								\
-		RB_FLIP_RIGHT(gpr, field);				\
+		break;							\
+	} while ((parent = RB_PARENT(elm, field)) != NULL);		\
 }
 
 #define RB_GENERATE_REMOVE(name, type, field, attr)			\
@@ -601,7 +629,7 @@
 		if ((child = RB_LEFT(right, field)) == NULL) {		\
 			child = RB_RIGHT(right, field);			\
 			red = RB_RED_RIGHT(old, field);			\
-			if (red)					\
+			if (!red)					\
 				RB_FLIP_RIGHT(old, field);		\
 			RB_RIGHT(old, field) = child;			\
 			parent = elm = right;				\
@@ -612,7 +640,7 @@
 			child = RB_RIGHT(elm, field);			\
 			parent = RB_PARENT(elm, field);			\
 			red = RB_RED_LEFT(parent, field);		\
-			if (red)					\
+			if (!red)					\
 				RB_FLIP_LEFT(parent, field);		\
 			RB_LEFT(parent, field) = child;			\
 			RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \
@@ -622,7 +650,7 @@
 	}								\
 	if (elm == child) {						\
 		red = RB_COLOR(old, field);				\
-		if (!red);						\
+		if (red);						\
 		else if (RB_LEFT(parent, field) == old)			\
 			RB_FLIP_LEFT(parent, field);			\
 		else							\
@@ -631,8 +659,18 @@
 	RB_SWAP_CHILD(head, old, elm, field);				\
 	if (child != NULL)						\
 		RB_SET_PARENT(child, parent, field);			\
-	else if (!red && parent != NULL)				\
-		name##_RB_REMOVE_COLOR(head, parent);			\
+	else if (parent != NULL &&					\
+		 RB_LEFT(parent, field) == NULL &&			\
+		 RB_RIGHT(parent, field) == NULL) {			\
+		RB_FLIP_LEFT(parent, field);				\
+		RB_FLIP_RIGHT(parent, field);				\
+		child = parent;						\
+		RB_AUGMENT(parent);					\
+		parent = RB_PARENT(child, field);			\
+		red = RB_TRUE;						\
+	}								\
+	if (red && parent != NULL)					\
+		name##_RB_REMOVE_COLOR(head, parent, child);		\
 	while (parent != NULL) {					\
 		RB_AUGMENT(parent);					\
 		parent = RB_PARENT(parent, field);			\