static void rb_delete_fixup(tree_p tr, tnode_p parent, tnode_p node){
	tnode_p sibling;
	while(node != tr->root && rb_color(node) == BLACK){
		if( node == parent->left ){
			sibling = parent->right;
			if(rb_color(sibling) == RED){
				sibling->color = BLACK;
				parent->color = RED;
				left_rotate(tr, parent);
				sibling = parent->right;
			}

			if(rb_color(sibling->left) == BLACK 
					&& rb_color(sibling->right) == BLACK){
				sibling->color = RED;
				node = parent;
				parent = parent->parent;
			} else if(rb_color(sibling->right) == BLACK){
				sibling->left->color = RED;
				right_rotate(tr, sibling);
				sibling = parent->right;
			} else {
				sibling->color = parent->color;
				parent->color = BLACK;
				sibling->right->color = BLACK;
				left_rotate(tr, parent);
				node = tr->root;
				parent = NULL;
			}
		}
		else{
			sibling = parent->left;
			if(rb_color(sibling) == RED){
				sibling->color = BLACK;
				parent->color = RED;
				right_rotate(tr, parent);
				sibling = parent->left;
			}

			if(rb_color(sibling->left) == BLACK 
					&& rb_color(sibling->right) == BLACK){
				sibling->color = RED;
				node = parent;
				parent = parent->parent;
			} else if(rb_color(sibling->left) == BLACK){
				sibling->right->color = RED;
				left_rotate(tr, sibling);
				sibling = parent->left;
			} else {
				sibling->color = parent->color;
				parent->color = BLACK;
				sibling->left->color = BLACK;
				right_rotate(tr, parent);
				node = tr->root;
				parent = NULL;
			}
		}
	}
	if(node != NULL) node->color = BLACK;
}

static void rb_unlink_3(struct rb_tree *t, struct rb_node *n,
                        struct rb_callbacks *cb) {
  if (rb_color(n->parent) == RB_BLACK && rb_color(rb_sibling(n)) == RB_BLACK &&
      rb_color(rb_sibling(n)->left) == RB_BLACK &&
      rb_color(rb_sibling(n)->right) == RB_BLACK) {
    rb_sibling(n)->color = RB_RED;
    rb_unlink_1(t, n->parent, cb);
    return;
  }

  rb_unlink_4(t, n, cb);
}

/* There are two cases handled here which are mirror images of one another:
   * N's sibling S is black, S's right child is red, and N is the left child
   of its parent. We exchange the colors of N's parent and sibling, make S's
   right child black, then rotate left at N's parent.
   * N's sibling S is black, S's left child is red, and N is the right child
   of its parent. We exchange the colors of N's parent and sibling, make S's
   left child black, then rotate right at N's parent.

   This accomplishes three things at once:
   * We add a black node to all paths through N, either by adding a black S to
   those paths or by recoloring N's parent black.
   * We remove a black node from all paths through S's red child, either by
   removing P from those paths or by recoloring S.
   * We recolor S's red child black, adding a black node back to all paths
   through S's red child.

   S's left child has become a child of N's parent during the rotation and so
   is unaffected. */
static void rb_unlink_6(struct rb_tree *t, struct rb_node *n,
                        struct rb_callbacks *cb) {
  rb_sibling(n)->color = rb_color(n->parent);
  n->parent->color = RB_BLACK;
  if (n == n->parent->left) {
    CHECK_EQ(rb_color(rb_sibling(n)->right), RB_RED);
    rb_sibling(n)->right->color = RB_BLACK;
    rb_rotate_left(t, n->parent, cb);
  } else {
    CHECK_EQ(rb_color(rb_sibling(n)->left), RB_RED);
    rb_sibling(n)->left->color = RB_BLACK;
    rb_rotate_right(t, n->parent, cb);
  }
}

/* Every red node has two children, and both are black (or equivalently, the
   parent of every red node is black). */
static void rb_verify_2(struct rb_node *n) {
  if (!n) {
    return;
  }

  if (rb_color(n) == RB_RED) {
    CHECK_EQ(rb_color(n->left), RB_BLACK);
    CHECK_EQ(rb_color(n->right), RB_BLACK);
    CHECK_EQ(rb_color(n->parent), RB_BLACK);
  }

  rb_verify_2(n->left);
  rb_verify_2(n->right);
}

tnode_p rb_insert(tree_p tr, void * data, int size){
	tnode_p node, current, uncle, parent;

	current = node = tree_insert(tr, data, size);
	node->color = RED;

	while(current != tr->root && rb_color(current->parent) == RED){
		parent = current->parent;
		if(parent == parent->parent->left){
			uncle = parent->parent->right;
			if(rb_color(uncle) == RED){
				parent->color = BLACK;
				uncle->color = BLACK;
				current = parent->parent;
				current->color = RED;
			} else if(current == parent->right){
				current = parent;
				left_rotate(tr, current);
			} else {
				parent->color = BLACK;
				parent->parent->color = RED;
				right_rotate(tr, parent->parent);
			}
		} else {
			uncle = parent->parent->left;
			if(rb_color(uncle) == RED){
				parent->color = BLACK;
				uncle->color = BLACK;
				current = parent->parent;
				current->color = RED;
			} else if(current == parent->left){
				current = parent;
				right_rotate(tr, current);
			} else {
				parent->color = BLACK;
				parent->parent->color = RED;
				left_rotate(tr, parent->parent);
			}
		}
	}

	tr->root->color = BLACK;
	
	return node;
}

/* In this case, the new node has a black parent. All the properties are still
   satisfied and we return. */
static void rb_link_2(struct rb_tree *t, struct rb_node *n,
                      struct rb_callbacks *cb) {
  if (rb_color(n->parent) == RB_BLACK) {
    /* tree is still valid */
    return;
  }

  rb_link_3(t, n, cb);
}

void _display(struct rb_node *temp, INFO (*a)[10], int *row, int *col)
{
	if(temp == 0)
		return;
	(*row)++;
	_display(temp->rb_left, a, row,col);
	a[*row][(*col)].color = rb_color(temp);
	a[*row][(*col)++].sid = rb_entry(temp, SAWON,tree)->sid;
	_display(temp->rb_right, a, row, col);
	(*row)--;
}

static void rb_link_3(struct rb_tree *t, struct rb_node *n,
                      struct rb_callbacks *cb) {
  if (rb_color(rb_uncle(n)) == RB_RED) {
    n->parent->color = RB_BLACK;
    rb_uncle(n)->color = RB_BLACK;
    rb_grandparent(n)->color = RB_RED;
    rb_link_1(t, rb_grandparent(n), cb);
    return;
  }

  rb_link_4(t, n, cb);
}

/* N has a red sibling. In this case we exchange the colors of the parent and
   sibling, then rotate about the parent so that the sibling becomes the
   parent of its former parent. This does not restore the tree properties, but
   reduces the problem to one of the remaining cases. */
static void rb_unlink_2(struct rb_tree *t, struct rb_node *n,
                        struct rb_callbacks *cb) {
  if (rb_color(rb_sibling(n)) == RB_RED) {
    n->parent->color = RB_RED;
    rb_sibling(n)->color = RB_BLACK;
    if (n == n->parent->left) {
      rb_rotate_left(t, n->parent, cb);
    } else {
      rb_rotate_right(t, n->parent, cb);
    }
  }

  rb_unlink_3(t, n, cb);
}

void rb_delete(tree_p tr, tnode_p node){
	tnode_p current = pull_out(tr, node);
	tnode_p next;

	if(current->left != NULL)
		next = current->left;
	else next = current->right;

	if(rb_color(current) == BLACK)
		rb_delete_fixup(tr, current->parent, next);

	current->parent = current->left = current->right = NULL;
	free(current);
}

/* All paths from any given node to its leaf nodes contain the same number of
   black nodes. This one is the trickiest to verify; we do it by traversing
   the tree, incrementing a black node count as we go. The first time we reach
   a leaf we save the count. We return the count so that when we subsequently
   reach other leaves, we compare the count to the saved count. */
static int rb_verify_3(struct rb_node *n, int black_count,
                       int path_black_count) {
  if (rb_color(n) == RB_BLACK) {
    black_count++;
  }

  if (!n) {
    if (path_black_count == -1) {
      path_black_count = black_count;
    } else {
      CHECK_EQ(black_count, path_black_count);
    }
    return path_black_count;
  }

  path_black_count = rb_verify_3(n->left, black_count, path_black_count);
  path_black_count = rb_verify_3(n->right, black_count, path_black_count);

  return path_black_count;
}

void rb_unlink(struct rb_tree *t, struct rb_node *n, struct rb_callbacks *cb) {
  CHECK(!rb_empty_node(n));

  /* when deleting a node with two non-leaf children, we swap the node with
     its in-order predecessor (the maximum or rightmost element in the left
     subtree), and then delete the original node which now has only one
     non-leaf child */
  if (n->left && n->right) {
    struct rb_node *pred = rb_max(n->left);
    rb_swap_node(t, n, pred);
  }

  /* a node with at most one non-leaf child can simply be replaced with its
     non-leaf child */
  CHECK(!n->left || !n->right);
  struct rb_node *child = n->right ? n->right : n->left;
  if (rb_color(n) == RB_BLACK) {
    rb_unlink_1(t, n, cb);
  }
  rb_replace_node(t, n, child);

  /* force root to black */
  if (t->root) {
    t->root->color = RB_BLACK;
  }

  /* fix up each node in the parent chain */
  if (cb && cb->propagate) {
    cb->propagate(t, n->parent);
  }

  /* clear node state to support rb_empty_node */
  memset(n, 0, sizeof(*n));

#if VERIFY_TREE
  rb_verify(t->root);
#endif
}

/* There are two cases handled here which are mirror images of one another:
   * N's sibling S is black, S's left child is red, S's right child is black,
   and N is the left child of its parent. We exchange the colors of S and its
   left sibling and rotate right at S.
   * N's sibling S is black, S's right child is red, S's left child is black,
   and N is the right child of its parent. We exchange the colors of S and its
   right sibling and rotate left at S.
   Both of these function to reduce us to the situation described in case 6. */
static void rb_unlink_5(struct rb_tree *t, struct rb_node *n,
                        struct rb_callbacks *cb) {
  if (n == n->parent->left && rb_color(rb_sibling(n)) == RB_BLACK &&
      rb_color(rb_sibling(n)->left) == RB_RED &&
      rb_color(rb_sibling(n)->right) == RB_BLACK) {
    rb_sibling(n)->color = RB_RED;
    rb_sibling(n)->left->color = RB_BLACK;
    rb_rotate_right(t, rb_sibling(n), cb);
  } else if (n == n->parent->right && rb_color(rb_sibling(n)) == RB_BLACK &&
             rb_color(rb_sibling(n)->right) == RB_RED &&
             rb_color(rb_sibling(n)->left) == RB_BLACK) {
    rb_sibling(n)->color = RB_RED;
    rb_sibling(n)->right->color = RB_BLACK;
    rb_rotate_left(t, rb_sibling(n), cb);
  }

  rb_unlink_6(t, n, cb);
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *child, *parent;
	int color;

	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else
	{
		struct rb_node *old = node, *left;

		node = node->rb_right;
		while ((left = node->rb_left) != NULL)
			node = left;
		child = node->rb_right;
		parent = rb_parent(node);
		color = rb_color(node);

		if (child)
			rb_set_parent(child, parent);
		if (parent == old) {
			parent->rb_right = child;
			parent = node;
		} else
			parent->rb_left = child;

		node->rb_parent_color = old->rb_parent_color;
		node->rb_right = old->rb_right;
		node->rb_left = old->rb_left;

		if (rb_parent(old))
		{
			if (rb_parent(old)->rb_left == old)
				rb_parent(old)->rb_left = node;
			else
				rb_parent(old)->rb_right = node;
		} else
			root->rb_node = node;

		rb_set_parent(old->rb_left, node);
		if (old->rb_right)
			rb_set_parent(old->rb_right, node);
		goto color;
	}

	parent = rb_parent(node);
	color = rb_color(node);

	if (child)
		rb_set_parent(child, parent);
	if (parent)
	{
		if (parent->rb_left == node)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	}
	else
		root->rb_node = child;

 color:
	if (color == RB_BLACK)
		__rb_erase_color(child, parent, root);
}

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
			     struct rb_root *root)
{
	struct rb_node *other;

	while ((!node || rb_is_black(node)) && node != root->rb_node)
	{
		if (parent->rb_left == node)
		{
			other = parent->rb_right;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_left(parent, root);
				other = parent->rb_right;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_right || rb_is_black(other->rb_right))
				{
					struct rb_node *o_left;
					if ((o_left = other->rb_left))
						rb_set_black(o_left);
					rb_set_red(other);
					__rb_rotate_right(other, root);
					other = parent->rb_right;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				if (other->rb_right)
					rb_set_black(other->rb_right);
				__rb_rotate_left(parent, root);
				node = root->rb_node;
				break;
			}
		}
		else
		{
			other = parent->rb_left;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_right(parent, root);
				other = parent->rb_left;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_left || rb_is_black(other->rb_left))
				{
					register struct rb_node *o_right;
					if ((o_right = other->rb_right))
						rb_set_black(o_right);
					rb_set_red(other);
					__rb_rotate_left(other, root);
					other = parent->rb_left;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				if (other->rb_left)
					rb_set_black(other->rb_left);
				__rb_rotate_right(parent, root);
				node = root->rb_node;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node);
}

void rb_arreglar_eliminacion(rb_arbol* arbol, rb_nodo* punta, rb_nodo* hermano) {
    rb_nodo* sobrino;
    rb_nodo* sobrino_nieto;
    

    if(rb_izquierdo(punta) == hermano) {
        if(rb_color(punta) == ROJO) {
            /*
                Caso c.1.1:
                Mi padre es rojo. Entonces, mi 
                hermano es negro.
            */ 
            
            /* Mi hermano tiene un hijo rojo? */
            if((rb_izquierdo(hermano) != arbol->nil && rb_color(rb_izquierdo(hermano)) == ROJO)) {
            
                /*
                El arbol tiene esta pinta:
                                P
                              /  \
                            H     z
                          /  \
                        C     y
                      /  \
                    w    x
                P = padre, H = hermano, C es rojo.
                z es donde yo estaba, que pasa de tener
                altura negra h a h-1.
                w, x e y todos tienen altura negra h-1.
                    
                */
                rb_rotar_derecha(arbol, punta);
                
                /*
                El arbol ahora tiene esta pinta:
                            H
                          /  \ 
                        C     P
                      /  \   / \
                    w     x y   z
                
                Es posible que y fuera rojo, entonces tengo
                que cambiarle el color a P. Pero hacer eso
                cambia la altura negra de z e y. Entonces
                pinto también a C de negro. Pero ahora w, x,
                y, z tienen altura h+1, y necesito que sea h.
                Entonces, pinto a H de rojo (no violo nada
                porque si el padre de H es rojo, entonces el
                padre de P antes era rojo, absurdo porque P
                era rojo).
                */
                rb_set_color(punta, NEGRO);
                rb_set_color(hermano, ROJO);
                rb_set_color(rb_izquierdo(hermano), NEGRO);
                
                /*
                    Ahora w, x, y, z tienen altura h. Terminé.
                */
            } else if((rb_derecho(hermano) != arbol->nil && rb_color(rb_derecho(hermano)) == ROJO)) {
                /* El hijo derecho de mi hermano es rojo.
                Entonces, el arbol tiene esta pinta:
                               P
                             /  \
                            H    z
                          /  \
                         w    C
                             | \
                            x   y
                Donde P es punta, H es hermano, C es rojo.
                Yo solía ser z.
                
                Quiero llevarlo a algo de la forma...   
                
                                C
                              /  \ 
                            H     P
                          /  \   / \
                        w     x y   z                 
                */
                
                               
                rb_rotar_izquierda(arbol, hermano); 
                
                /* El arbol ahora se ve así:
                                    P
                                  /  \
                                C     z
                              /  \
                            H     y
                          /  \
                        w    x 
                  
                  El izquierdo de la punta es lo que antes era
                  el derecho del hermano.
                */
                rb_rotar_derecha(arbol, punta);
                
                /* Ahora se vé así:
                                C
                              /  \ 
//.........这里部分代码省略.........

void rb_eliminar_nodo(rb_arbol* arbol, rb_nodo* nodo) {
    /*
        Primero eliminamos el nodo de la misma manera
        que en un arbol binario de búsqueda normal.
        
        Encontramos el nodo a borrar. Si tiene hijos,
        lo swapeamos con su sucesor o predecesor 
        inmediato. Luego, borramos el nodo, que ahora
        va a tener:
            a)  0 hijos, y ser rojo
            b)  0 hijos, y ser negro
            c)  1 hijo, y ser negro, y su hijo
                una hoja roja
                
        Si es rojo, lo sacamos y listo.
        Si es negro con un hijo rojo, y swapeamos los 
        colores de su padre y su hijo.
        
        Si tiene 0 hijos y es negro, la pasamos como 
        el orto, porque al sacar el elemento del arbol 
        estamos cambiando la altura negra de un subarbol.
    */  
    
    
    /*
        Lo que me pasaron acá es un puntero al nodo
        en cuestión - no necesito loopear para buscarlo.
    */
    
    unsigned int hijos = rb_contar_hijos(arbol, nodo);
    rb_nodo* pre;
    rb_nodo* punta;
    rb_nodo* hermano;
    int orig;
    
    orig = rb_datos(nodo);
    if(hijos == 2) {
        pre = rb_predecesor(arbol, nodo);
        rb_swap(arbol, nodo, pre);
        nodo = pre;
    }
    
    if(rb_color(nodo) == ROJO) {
        /*assert(rb_es_hoja(arbol, nodo));*/
        if(!(rb_es_hoja(arbol, nodo))) {
            printf("No lo cambie por su pre. El es: %d. Su predecesor es: %d.\n", orig, rb_datos(nodo));
            rb_dump_arbol(arbol);
            exit(1);
        }
        /*
            Caso a:
            Sin hijos, rojo.
            Sacamos al toque.
        */
        
        rb_eliminar_hijo(arbol, rb_padre(nodo), nodo);
        return;
    }
    
    if( rb_color(nodo) == NEGRO &&
        rb_contar_hijos(arbol, nodo) == 1) {
        
        /*assert(rb_derecho(nodo) == arbol->nil);
        assert(rb_color(rb_izquierdo(nodo)) == ROJO);
        */
        /*
            Caso b:
            Un hijo a la izquierda, rojo.
            Yo negro.
            Cambiamos los valores, y borramos al rojo.
        */
        if(rb_derecho(nodo) == arbol->nil) {            
            rb_set_datos(nodo, rb_datos(rb_izquierdo(nodo)));
            rb_eliminar_hijo(arbol, nodo, rb_izquierdo(nodo));
        } else {            
            rb_set_datos(nodo, rb_datos(rb_derecho(nodo)));
            rb_eliminar_hijo(arbol, nodo, rb_derecho(nodo));
        }
        return;
    }
    
    

    
    if( rb_color(nodo) == NEGRO ) {
        assert(rb_es_hoja(arbol, nodo));
        
        /*
            Caso c:
            Es una hoja negra.
            
            Existe un sub-arbol del arbol tal que
            cambié la altura negra del sub-arbol.
            
            Llamemos punta al nodo padre de este 
            sub-arbol. En este momento, punta es el
            padre del nodo que sacamos. A medida
            que haga correcciones, este sub-arbol
            va a ir creciendo.
        
//.........这里部分代码省略.........

bool rb_is_red(NodeTy *r)
{
	return !rb_color(r);
}

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
    rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *child, *parent;
	int color;
	
	struct mytype *mytype;

	mytype = container_of(node, struct mytype, node);
 		
	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else
	{
		struct rb_node *old = node, *left;

		node = node->rb_right;
		while ((left = node->rb_left) != NULL)
			node = left;

		if (rb_parent(old)) {
			if (rb_parent(old)->rb_left == old)
				rb_parent(old)->rb_left = node;
			else
				rb_parent(old)->rb_right = node;
		} else
			root->rb_node = node;

		child = node->rb_right;
		parent = rb_parent(node);
		color = rb_color(node);

		if (parent == old) {
			parent = node;
		} else {
			if (child)
				rb_set_parent(child, parent);
			parent->rb_left = child;

			node->rb_right = old->rb_right;
			rb_set_parent(old->rb_right, node);
		}

		node->rb_parent_color = old->rb_parent_color;
		node->rb_left = old->rb_left;
		rb_set_parent(old->rb_left, node);

		goto color;
	}

	parent = rb_parent(node);
	color = rb_color(node);

	if (child)
		rb_set_parent(child, parent);
	if (parent)
	{
		if (parent->rb_left == node)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	}
	else
		root->rb_node = child;

 color:  
 	
	if (color == RB_BLACK)
	{
		pr_debug("delete value = %02d, ", mytype->keyvalue);
		__rb_erase_color(child, parent, root);
		
	}
	else 
	{
		pr_debug("delete value = %02d, 对应情况X。\n", mytype->keyvalue);
	}
}