Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -388,7 +388,6 @@
 	RB_SWAP_CHILD(head, elm, tmp, field);				\
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
-	RB_AUGMENT(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
@@ -399,7 +398,6 @@
 	RB_SWAP_CHILD(head, elm, tmp, field);				\
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
-	RB_AUGMENT(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 /* Generates prototypes and inline functions */
@@ -490,12 +488,21 @@
 			if (!RB_RED_RIGHT(elm, field)) {		\
 				/* coverity[uninit_use] */		\
 				RB_ROTATE_LEFT(head, elm, child, field);\
-				if (RB_RED_RIGHT(child, field))		\
+				switch (RB_BITS(child, field) &		\
+				    RB_RED_MASK) {			\
+				case RB_RED_R:				\
 					RB_FLIP_LEFT(parent, field);	\
-				if (RB_RED_LEFT(child, field))		\
-					RB_FLIP_ALL(elm, field);	\
-				else					\
 					RB_FLIP_LEFT(elm, field);	\
+					RB_AUGMENT(elm);		\
+					break;				\
+				default:				\
+					RB_FLIP_LEFT(elm, field);	\
+					break;				\
+				case RB_RED_L:				\
+					RB_FLIP_ALL(elm, field);	\
+					RB_AUGMENT(elm);		\
+					break;				\
+				}					\
 				elm = child;				\
 			}						\
 			RB_ROTATE_RIGHT(head, parent, elm, field);	\
@@ -513,17 +520,27 @@
 			if (!RB_RED_LEFT(elm, field)) {			\
 				/* coverity[uninit_use] */		\
 				RB_ROTATE_RIGHT(head, elm, child, field);\
-				if (RB_RED_LEFT(child, field))		\
+				switch (RB_BITS(child, field) &		\
+				    RB_RED_MASK) {			\
+				case RB_RED_L:				\
 					RB_FLIP_RIGHT(parent, field);	\
-				if (RB_RED_RIGHT(child, field))		\
-					RB_FLIP_ALL(elm, field);	\
-				else					\
 					RB_FLIP_RIGHT(elm, field);	\
+					RB_AUGMENT(elm);		\
+					break;				\
+				default:				\
+					RB_FLIP_RIGHT(elm, field);	\
+					break;				\
+				case RB_RED_R:				\
+					RB_FLIP_ALL(elm, field);	\
+					RB_AUGMENT(elm);		\
+					break;				\
+				}					\
 				elm = child;				\
 			}						\
 			RB_ROTATE_LEFT(head, parent, elm, field);	\
 		}							\
 		RB_BITS(elm, field) &= ~RB_RED_MASK;			\
+		RB_AUGMENT(parent);					\
 		break;							\
 	}								\
 }
@@ -571,18 +588,19 @@
 				elm = parent;				\
 				continue;				\
 			case RB_RED_R:					\
-				elm = RB_LEFT(sib, field);		\
-				RB_ROTATE_RIGHT(head, sib, elm, field);	\
-				if (RB_RED_LEFT(elm, field))		\
+				elm = sib;				\
+				sib = RB_LEFT(elm, field);		\
+				RB_ROTATE_RIGHT(head, elm, sib, field);	\
+				if (RB_RED_LEFT(sib, field))		\
 					RB_FLIP_ALL(parent, field);	\
 				else					\
 					RB_FLIP_LEFT(parent, field);	\
-				if (RB_RED_RIGHT(elm, field))		\
-					RB_FLIP_ALL(sib, field);	\
+				if (RB_RED_RIGHT(sib, field))		\
+					RB_FLIP_ALL(elm, field);	\
 				else					\
-					RB_FLIP_RIGHT(sib, field);	\
-				RB_BITS(elm, field) |= RB_RED_MASK;	\
-				sib = elm;				\
+					RB_FLIP_RIGHT(elm, field);	\
+				RB_BITS(sib, field) |= RB_RED_MASK;	\
+				RB_AUGMENT(elm);			\
 				break;					\
 			case RB_RED_L:					\
 				if (RB_STRICT_HST && elm != NULL) {	\
@@ -614,18 +632,19 @@
 				elm = parent;				\
 				continue;				\
 			case RB_RED_L:					\
-				elm = RB_RIGHT(sib, field);		\
-				RB_ROTATE_LEFT(head, sib, elm, field);	\
-				if (RB_RED_RIGHT(elm, field))		\
+				elm = sib;				\
+				sib = RB_RIGHT(elm, field);		\
+				RB_ROTATE_LEFT(head, elm, sib, field);	\
+				if (RB_RED_RIGHT(sib, field))		\
 					RB_FLIP_ALL(parent, field);	\
 				else					\
 					RB_FLIP_RIGHT(parent, field);	\
-				if (RB_RED_LEFT(elm, field))		\
-					RB_FLIP_ALL(sib, field);	\
+				if (RB_RED_LEFT(sib, field))		\
+					RB_FLIP_ALL(elm, field);	\
 				else					\
-					RB_FLIP_LEFT(sib, field);	\
-				RB_BITS(elm, field) |= RB_RED_MASK;	\
-				sib = elm;				\
+					RB_FLIP_LEFT(elm, field);	\
+				RB_BITS(sib, field) |= RB_RED_MASK;	\
+				RB_AUGMENT(elm);			\
 				break;					\
 			case RB_RED_R:					\
 				if (RB_STRICT_HST && elm != NULL) {	\
@@ -678,11 +697,13 @@
 	RB_SWAP_CHILD(head, old, elm, field);				\
 	if (child != NULL)						\
 		RB_SET_PARENT(child, parent, field);			\
-	if (parent != NULL)						\
+	if (parent != NULL) {						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
-	while (parent != NULL) {					\
-		RB_AUGMENT(parent);					\
-		parent = RB_PARENT(parent, field);			\
+		if (parent == elm && RB_LEFT(parent, field) == NULL)	\
+			parent = RB_PARENT(parent, field);		\
+		do							\
+			RB_AUGMENT(parent);				\
+		while ((parent = RB_PARENT(parent, field)) != NULL);	\
 	}								\
 	return (old);							\
 }
@@ -714,10 +735,9 @@
 	else								\
 		RB_RIGHT(parent, field) = elm;				\
 	name##_RB_INSERT_COLOR(head, elm);				\
-	while (elm != NULL) {						\
+	do								\
 		RB_AUGMENT(elm);					\
-		elm = RB_PARENT(elm, field);				\
-	}								\
+	while ((elm = RB_PARENT(elm, field)) != NULL);			\
 	return (NULL);							\
 }