Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -569,27 +569,36 @@
 	else if (RB_RIGHT(elm, field) == NULL)				\
 		child = RB_LEFT(elm, field);				\
 	else {								\
-		elm = RB_RIGHT(old, field);				\
-		if ((child = RB_LEFT(elm, field)) == NULL) {		\
-			child = RB_RIGHT(elm, field);			\
-			RB_RIGHT(old, field) = child;			\
-			RB_PARENT(elm, field) = elm;			\
-		} else {						\
-			do						\
-				elm = child;				\
-			while ((child = RB_LEFT(elm, field)) != NULL);	\
-			child = RB_RIGHT(elm, field);			\
-			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
-		}							\
-		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
-		parent = RB_PARENT(old, field);				\
-		if (parent != NULL) {					\
-			if (RB_LEFT(parent, field) == old)		\
-				RB_LEFT(parent, field) = elm;		\
+		struct type *left;					\
+		elm = RB_RIGHT(elm, field);				\
+		while ((left = RB_LEFT(elm, field)) != NULL)		\
+			elm = left;					\
+		child = RB_RIGHT(elm, field);				\
+		parent = RB_PARENT(elm, field);				\
+		color = RB_COLOR(elm, field);				\
+		if (child)						\
+			RB_PARENT(child, field) = parent;		\
+		if (parent) {						\
+			if (RB_LEFT(parent, field) == elm)		\
+				RB_LEFT(parent, field) = child;		\
 			else						\
-				RB_RIGHT(parent, field) = elm;		\
+				RB_RIGHT(parent, field) = child;	\
 		} else							\
+			RB_ROOT(head) = child;				\
+		if (RB_PARENT(elm, field) == old)			\
+			parent = elm;					\
+		(elm)->field = (old)->field;				\
+		if (RB_PARENT(old, field)) {				\
+			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+				RB_LEFT(RB_PARENT(old, field), field) = elm;\
+			else						\
+				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+		} else							\
 			RB_ROOT(head) = elm;				\
+		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
+		if (RB_RIGHT(old, field))				\
+			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
+		goto color;						\
 	}								\
 	parent = RB_PARENT(elm, field);					\
 	color = RB_COLOR(elm, field);					\
@@ -602,8 +611,7 @@
 			RB_RIGHT(parent, field) = child;		\
 	} else								\
 		RB_ROOT(head) = child;					\
-	if (elm != old)							\
-		(elm)->field = (old)->field;				\
+color:									\
 	if (color == RB_BLACK)						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
 	while (parent != NULL) {					\