hmmer-3.3/easel/esl_red_black.c
// Performs the rebalancings required to restore the red-black invariant in tree when node and its parent are both red
// returns the balanced tree.  Assumes that someone else has checked to make sure that such a violation exists.
Performs the rebalancings required to restore the red-black invariant in tree when node and its parent are both red
returns the balanced tree.  Assumes that someone else has checked to make sure that such a violation exists.
Performs the rebalancings required to restore the red - black invariant in tree when node and its parent are both red returns the balanced tree . Assumes that someone else has checked to make sure that such a violation exists .
static ESL_RED_BLACK_DOUBLEKEY *esl_red_black_doublekey_rebalance(ESL_RED_BLACK_DOUBLEKEY *tree, ESL_RED_BLACK_DOUBLEKEY *node){
  ESL_RED_BLACK_DOUBLEKEY *parent, *grandparent, *root, *uncle;
  root = tree;  
  parent = node->parent;
  if (parent == NULL){
    esl_fatal("Root node of tree passed to esl_red_black_doublekey_insert\n");
  }
  uint64_t parent_sibling_color;
  grandparent = parent->parent;
  if(grandparent == NULL){
    esl_fatal("red-black violation: inserted node's parent was both red and graph root\n");
  }
  if(grandparent->large == parent){
    uncle = grandparent->small;
    if(grandparent->small != NULL){
      parent_sibling_color = grandparent->small->color;
    }
    else{
      parent_sibling_color = ESL_RED_BLACK_COLOR_BLACK;  
    }
  }
  else{
    if(grandparent->large != NULL){
      uncle = grandparent->large;
      parent_sibling_color = grandparent->large->color;
    }
    else{
      parent_sibling_color = ESL_RED_BLACK_COLOR_BLACK;  
    }
  }
  if(parent_sibling_color == ESL_RED_BLACK_COLOR_RED){
    parent->color = ESL_RED_BLACK_COLOR_BLACK;
    uncle->color = ESL_RED_BLACK_COLOR_BLACK;
    grandparent->color = ESL_RED_BLACK_COLOR_RED;
    if(grandparent->parent == NULL){
      grandparent->color = ESL_RED_BLACK_COLOR_BLACK;
      return tree;
    }
    else{
      if(grandparent->parent->color == ESL_RED_BLACK_COLOR_RED){
        return esl_red_black_doublekey_rebalance(tree, grandparent);
      }
    }
  }
  else{
    if(parent->small == node){
      if(grandparent->small == parent){
        grandparent->small = parent->large;
        if(grandparent->small != NULL){
          grandparent->small->parent = grandparent;
        }
        parent->large = grandparent;          
        if(grandparent->parent == NULL){
          root = parent;
        }
        else{
          if(grandparent->parent->small == grandparent){
            grandparent->parent->small = parent;
          }
          else{
            grandparent->parent->large = parent;
          }
        }
        parent->parent = grandparent->parent;
        grandparent->parent = parent;
        parent->color = ESL_RED_BLACK_COLOR_BLACK;
        grandparent->color = ESL_RED_BLACK_COLOR_RED;
        node->color = ESL_RED_BLACK_COLOR_RED;
      }
      else{
        if(grandparent->parent == NULL){
          root = node;
        }
        else{
          if(grandparent->parent->small == grandparent){
            grandparent->parent->small = node;
          }
          else{
            grandparent->parent->large = node;
          }
        }
        node->parent = grandparent->parent;
        grandparent->large = node->small;
        if(grandparent->large != NULL){
          grandparent->large->parent = grandparent;
        } 
        parent->small = node->large; 
        if(parent->small != NULL){
          parent->small->parent = parent;
        }
        node->small = grandparent;
        grandparent->parent = node;
        node->large = parent;
        parent->parent = node;
        node->color = ESL_RED_BLACK_COLOR_BLACK;
        parent->color = ESL_RED_BLACK_COLOR_RED;
        grandparent->color = ESL_RED_BLACK_COLOR_RED;
      }
    }
    else{
      if(grandparent->small == parent){
        if(grandparent->parent == NULL){
          root = node;
        }
        else{
          if(grandparent->parent->small == grandparent){
            grandparent->parent->small = node;
          }
          else{
            grandparent->parent->large = node;
          }
        }
        node->parent = grandparent->parent;
        grandparent->small = node->large;
        if(grandparent->small != NULL){
          grandparent->small->parent = grandparent;
        }
        parent->large = node->small;
        if(parent->large != NULL){
          parent->large->parent = parent;
        }
        node->large = grandparent;
        grandparent->parent = node;
        node->small = parent;
        parent->parent = node;
        node->color = ESL_RED_BLACK_COLOR_BLACK;
        parent->color = ESL_RED_BLACK_COLOR_RED;
        grandparent->color = ESL_RED_BLACK_COLOR_RED;
      }
      else{
        if(grandparent->parent == NULL){
          root = parent;
        }
        else{
          if(grandparent->parent->small == grandparent){
            grandparent->parent->small = parent;
          }
          else{
            grandparent->parent->large = parent;
          }
        }
        parent->parent = grandparent->parent;
        grandparent->large = parent->small;
        if(parent->small != NULL){
          parent->small->parent = grandparent;
        }
        parent->small = grandparent;
        grandparent->parent = parent;
        parent->color = ESL_RED_BLACK_COLOR_BLACK;
        grandparent->color = ESL_RED_BLACK_COLOR_RED;
        node->color = ESL_RED_BLACK_COLOR_RED;
      }
    }
  }
#ifdef P7_CHECK_RED_BLACK
  if(esl_red_black_doublekey_check_invariants(root) != eslOK){
    printf("Red-black tree failed invariant check in esl_red_black_doublekey_insert\n");
  } 
#endif
  return root;  
}
static ESL_RED_BLACK_DOUBLEKEY * esl_red_black_doublekey_rebalance ( ESL_RED_BLACK_DOUBLEKEY * tree , ESL_RED_BLACK_DOUBLEKEY * node ) { ESL_RED_BLACK_DOUBLEKEY * parent , * grandparent , * root , * uncle ; root = tree ; parent = node -> parent ; if ( parent == NULL ) { esl_fatal ( " \n " ) ; } uint64_t parent_sibling_color ; grandparent = parent -> parent ; if ( grandparent == NULL ) { esl_fatal ( " \n " ) ; } if ( grandparent -> large == parent ) { uncle = grandparent -> small ; if ( grandparent -> small != NULL ) { parent_sibling_color = grandparent -> small -> color ; } else { parent_sibling_color = ESL_RED_BLACK_COLOR_BLACK ; } } else { if ( grandparent -> large != NULL ) { uncle = grandparent -> large ; parent_sibling_color = grandparent -> large -> color ; } else { parent_sibling_color = ESL_RED_BLACK_COLOR_BLACK ; } } if ( parent_sibling_color == ESL_RED_BLACK_COLOR_RED ) { parent -> color = ESL_RED_BLACK_COLOR_BLACK ; uncle -> color = ESL_RED_BLACK_COLOR_BLACK ; grandparent -> color = ESL_RED_BLACK_COLOR_RED ; if ( grandparent -> parent == NULL ) { grandparent -> color = ESL_RED_BLACK_COLOR_BLACK ; return tree ; } else { if ( grandparent -> parent -> color == ESL_RED_BLACK_COLOR_RED ) { return esl_red_black_doublekey_rebalance ( tree , grandparent ) ; } } } else { if ( parent -> small == node ) { if ( grandparent -> small == parent ) { grandparent -> small = parent -> large ; if ( grandparent -> small != NULL ) { grandparent -> small -> parent = grandparent ; } parent -> large = grandparent ; if ( grandparent -> parent == NULL ) { root = parent ; } else { if ( grandparent -> parent -> small == grandparent ) { grandparent -> parent -> small = parent ; } else { grandparent -> parent -> large = parent ; } } parent -> parent = grandparent -> parent ; grandparent -> parent = parent ; parent -> color = ESL_RED_BLACK_COLOR_BLACK ; grandparent -> color = ESL_RED_BLACK_COLOR_RED ; node -> color = ESL_RED_BLACK_COLOR_RED ; } else { if ( grandparent -> parent == NULL ) { root = node ; } else { if ( grandparent -> parent -> small == grandparent ) { grandparent -> parent -> small = node ; } else { grandparent -> parent -> large = node ; } } node -> parent = grandparent -> parent ; grandparent -> large = node -> small ; if ( grandparent -> large != NULL ) { grandparent -> large -> parent = grandparent ; } parent -> small = node -> large ; if ( parent -> small != NULL ) { parent -> small -> parent = parent ; } node -> small = grandparent ; grandparent -> parent = node ; node -> large = parent ; parent -> parent = node ; node -> color = ESL_RED_BLACK_COLOR_BLACK ; parent -> color = ESL_RED_BLACK_COLOR_RED ; grandparent -> color = ESL_RED_BLACK_COLOR_RED ; } } else { if ( grandparent -> small == parent ) { if ( grandparent -> parent == NULL ) { root = node ; } else { if ( grandparent -> parent -> small == grandparent ) { grandparent -> parent -> small = node ; } else { grandparent -> parent -> large = node ; } } node -> parent = grandparent -> parent ; grandparent -> small = node -> large ; if ( grandparent -> small != NULL ) { grandparent -> small -> parent = grandparent ; } parent -> large = node -> small ; if ( parent -> large != NULL ) { parent -> large -> parent = parent ; } node -> large = grandparent ; grandparent -> parent = node ; node -> small = parent ; parent -> parent = node ; node -> color = ESL_RED_BLACK_COLOR_BLACK ; parent -> color = ESL_RED_BLACK_COLOR_RED ; grandparent -> color = ESL_RED_BLACK_COLOR_RED ; } else { if ( grandparent -> parent == NULL ) { root = parent ; } else { if ( grandparent -> parent -> small == grandparent ) { grandparent -> parent -> small = parent ; } else { grandparent -> parent -> large = parent ; } } parent -> parent = grandparent -> parent ; grandparent -> large = parent -> small ; if ( parent -> small != NULL ) { parent -> small -> parent = grandparent ; } parent -> small = grandparent ; grandparent -> parent = parent ; parent -> color = ESL_RED_BLACK_COLOR_BLACK ; grandparent -> color = ESL_RED_BLACK_COLOR_RED ; node -> color = ESL_RED_BLACK_COLOR_RED ; } } } #ifdef P7_CHECK_RED_BLACK if ( esl_red_black_doublekey_check_invariants ( root ) != eslOK ) { printf ( " \n " ) ; } #endif return root ; }
Performs the rebalancings required to restore the red-black invariant in tree when node and its parent are both red
returns the balanced tree.
Performs the rebalancings required to restore the red - black invariant in tree when node and its parent are both red returns the balanced tree .
// root starts out at the base of the original tree, but may change // parent is the large child of its grandparent; // Null parent-sibling counts as  //black //parent is the small child of its grandparent // Null parent-sibling counts as  //black //see http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/ //for an explanation of the operations to restore red-black balance //This code uses small = to the left on that page, large = to the right // We need to push red to restore the red-black property // grandparent is the top of the tree, so change its color back to black // to maintain invariants //we've introduced a new red-red violation that we need to resolve // need to do rotations //We're on the small side of our parent // our parent was on the small side of our grandparent // grandparent was the original root of the tree //parent becomes the new child of great-grandparent // done rotating, set the colors // our parent was on the large side of our grandparent // grandparent was the root of the tree, so the node we're inserting // becomes the new root // current node replaces its grandparent as its great-grandparent's  // child //We're on the large side of our parent // our parent was on the small side of our grandparent // grandparent was the root of the tree, so the node we're inserting // becomes the new root // current node replaces its grandparent as its great-grandparent's  // child // our parent was on the large side of our grandparent // grandparent was the root of the tree //parent becomes the new child of great-grandparent //return the modified tree