InfinityUtils/RedBlackTree.h
void fixInsert(Node* k) {
		Node* u;
		while (k->parent->color == 1) {
			if (k->parent == k->parent->parent->right) {
				u = k->parent->parent->left; // uncle
				if (u->color == 1) {
					// case 3.1
					u->color = 0;
					k->parent->color = 0;
					k->parent->parent->color = 1;
					k = k->parent->parent;
				} else {
					if (k == k->parent->left) {
						// case 3.2.2
						k = k->parent;
						rightRotate(k);
					}
					// case 3.2.1
					k->parent->color = 0;
					k->parent->parent->color = 1;
					leftRotate(k->parent->parent);
				}
			} else {
				u = k->parent->parent->right; // uncle

				if (u->color == 1) {
					// mirror case 3.1
					u->color = 0;
					k->parent->color = 0;
					k->parent->parent->color = 1;
					k = k->parent->parent;
				} else {
					if (k == k->parent->right) {
						// mirror case 3.2.2
						k = k->parent;
						leftRotate(k);
					}
					// mirror case 3.2.1
					k->parent->color = 0;
					k->parent->parent->color = 1;
					rightRotate(k->parent->parent);
				}
			}
			if (k == root) {
				break;
			}
		}
		root->color = 0;
	}
// fix the red-black tree

fix the red-black tree
fix the red - black tree
void fixInsert(Node* k) {
		Node* u;
		while (k->parent->color == 1) {
			if (k->parent == k->parent->parent->right) {
				u = k->parent->parent->left; 
				if (u->color == 1) {
					u->color = 0;
					k->parent->color = 0;
					k->parent->parent->color = 1;
					k = k->parent->parent;
				} else {
					if (k == k->parent->left) {
						k = k->parent;
						rightRotate(k);
					}
					k->parent->color = 0;
					k->parent->parent->color = 1;
					leftRotate(k->parent->parent);
				}
			} else {
				u = k->parent->parent->right; 
				if (u->color == 1) {
					u->color = 0;
					k->parent->color = 0;
					k->parent->parent->color = 1;
					k = k->parent->parent;
				} else {
					if (k == k->parent->right) {
						k = k->parent;
						leftRotate(k);
					}
					k->parent->color = 0;
					k->parent->parent->color = 1;
					rightRotate(k->parent->parent);
				}
			}
			if (k == root) {
				break;
			}
		}
		root->color = 0;
	}
void fixInsert ( Node * k ) { Node * u ; while ( k -> parent -> color == 1 ) { if ( k -> parent == k -> parent -> parent -> right ) { u = k -> parent -> parent -> left ; if ( u -> color == 1 ) { u -> color = 0 ; k -> parent -> color = 0 ; k -> parent -> parent -> color = 1 ; k = k -> parent -> parent ; } else { if ( k == k -> parent -> left ) { k = k -> parent ; rightRotate ( k ) ; } k -> parent -> color = 0 ; k -> parent -> parent -> color = 1 ; leftRotate ( k -> parent -> parent ) ; } } else { u = k -> parent -> parent -> right ; if ( u -> color == 1 ) { u -> color = 0 ; k -> parent -> color = 0 ; k -> parent -> parent -> color = 1 ; k = k -> parent -> parent ; } else { if ( k == k -> parent -> right ) { k = k -> parent ; leftRotate ( k ) ; } k -> parent -> color = 0 ; k -> parent -> parent -> color = 1 ; rightRotate ( k -> parent -> parent ) ; } } if ( k == root ) { break ; } } root -> color = 0 ; }
fix the red-black tree
fix the red - black tree
// uncle
 // case 3.1
 // case 3.2.2
 // case 3.2.1
 // uncle
 // mirror case 3.1
 // mirror case 3.2.2
 // mirror case 3.2.1
