AVLTree

 view release on metacpan or  search on metacpan

avltree/avltree.c  view on Meta::CPAN

int avltree_insert ( avltree_t *tree, SV *data )
{
  /* Empty tree case */
  if ( tree->root == NULL ) {
    tree->root = new_node ( tree, data );
    if ( tree->root == NULL )
      return 0;
  }
  else {
    avlnode_t head = {0}; /* Temporary tree root */
    avlnode_t *s, *t;     /* Place to rebalance and parent */
    avlnode_t *p, *q;     /* Iterator and save pointer */
    int dir;

    /* Set up false root to ease maintenance */
    t = &head;
    t->link[1] = tree->root;

    /* Search down the tree, saving rebalance points */
    for ( s = p = t->link[1]; ; p = q ) {
      dir = tree->cmp ( p->data, data ) < 0;

avltree/avltree.c  view on Meta::CPAN

    p->link[dir] = q = new_node ( tree, data );
    if ( q == NULL )
      return 0;

    /* Update balance factors */
    for ( p = s; p != q; p = p->link[dir] ) {
      dir = tree->cmp ( p->data, data ) < 0;
      p->balance += dir == 0 ? -1 : +1;
    }

    q = s; /* Save rebalance point for parent fix */

    /* Rebalance if necessary */
    if ( abs ( s->balance ) > 1 ) {
      dir = tree->cmp ( s->data, data ) < 0;
      insert_balance ( s, dir );
    }

    /* Fix parent */
    if ( q == head.link[1] )
      tree->root = s;
    else
      t->link[q == t->link[1]] = s;
  }

  ++tree->size;

  return 1;
}

avltree/avltree.c  view on Meta::CPAN

      up[top++] = it;

      it = it->link[upd[top - 1]];
    }

    /* Remove the node */
    if ( it->link[0] == NULL || it->link[1] == NULL ) {
      /* Which child is not null? */
      int dir = it->link[0] == NULL;

      /* Fix parent */
      if ( top != 0 )
        up[top - 1]->link[upd[top - 1]] = it->link[dir];
      else
        tree->root = it->link[dir];

      tree->rel ( it->data );
      free ( it );
    }
    else {
      /* Find the inorder successor */

avltree/avltree.c  view on Meta::CPAN

        upd[top] = 0;
        up[top++] = heir;
        heir = heir->link[0];
      }

      /* Swap data */
      save = it->data;
      it->data = heir->data;
      heir->data = save;

      /* Unlink successor and fix parent */
      up[top - 1]->link[up[top - 1] == it] = heir->link[1];

      tree->rel ( heir->data );
      free ( heir );
    }

    /* Walk back up the search path */
    while ( --top >= 0 && !done ) {
      /* Update balance factors */
      up[top]->balance += upd[top] != 0 ? -1 : +1;

      /* Terminate or rebalance as necessary */
      if ( abs ( up[top]->balance ) == 1 )
        break;
      else if ( abs ( up[top]->balance ) > 1 ) {
        remove_balance ( up[top], upd[top], done );

        /* Fix parent */
        if ( top != 0 )
          up[top - 1]->link[upd[top - 1]] = up[top];
        else
          tree->root = up[0];
      }
    }

    --tree->size;
  }