Logo Search packages:      
Sourcecode: ragel version File versions

template<AVLMEL_TEMPDEF >
Element * AvlTree< AVLMEL_TEMPDEF >::detach ( Element *  element  )  [inline]

Detach a element from the tree.

If the element is not in the tree then undefined behaviour results.

Returns:
The element given.

Definition at line 1164 of file avlcommon.h.

{
      Element *replacement, *fixfrom;
      long lheight, rheight;

#ifdef WALKABLE
      /* Remove the element from the ordered list. */
      BASELIST::detach( element );
#endif
      
      /* Update treeSize. */
      treeSize--;

      /* Find a replacement element. */
      if (element->BASE_EL(right))
      {
            /* Find the leftmost element of the right subtree. */
            replacement = element->BASE_EL(right);
            while (replacement->BASE_EL(left))
                  replacement = replacement->BASE_EL(left);

            /* If replacing the element the with its child then we need to start
             * fixing at the replacement, otherwise we start fixing at the
             * parent of the replacement. */
            if (replacement->BASE_EL(parent) == element)
                  fixfrom = replacement;
            else
                  fixfrom = replacement->BASE_EL(parent);

#ifndef WALKABLE
            if ( element == head )
                  head = replacement;
#endif

            removeEl(replacement, replacement->BASE_EL(right));
            replaceEl(element, replacement);
      }
      else if (element->BASE_EL(left))
      {
            /* Find the rightmost element of the left subtree. */
            replacement = element->BASE_EL(left);
            while (replacement->BASE_EL(right))
                  replacement = replacement->BASE_EL(right);

            /* If replacing the element the with its child then we need to start
             * fixing at the replacement, otherwise we start fixing at the
             * parent of the replacement. */
            if (replacement->BASE_EL(parent) == element)
                  fixfrom = replacement;
            else
                  fixfrom = replacement->BASE_EL(parent);

#ifndef WALKABLE
            if ( element == tail )
                  tail = replacement;
#endif

            removeEl(replacement, replacement->BASE_EL(left));
            replaceEl(element, replacement);
      }
      else
      {
            /* We need to start fixing at the parent of the element. */
            fixfrom = element->BASE_EL(parent);

#ifndef WALKABLE
            if ( element == head )
                  head = element->BASE_EL(parent);
            if ( element == tail )
                  tail = element->BASE_EL(parent);
#endif

            /* The element we are deleting is a leaf element. */
            removeEl(element, 0);
      }

      /* If fixfrom is null it means we just deleted
       * the root of the tree. */
      if ( fixfrom == 0 )
            return element;

      /* Fix the heights after the deletion. */
      recalcHeights(fixfrom);

      /* Fix every unbalanced element going up in the tree. */
      Element *ub = findFirstUnbalEl(fixfrom);
      while ( ub )
      {
            /* Find the element to rebalance by moving down from the first unbalanced
             * element 2 levels in the direction of the greatest heights. On the
             * second move down, the heights may be equal ( but not on the first ).
             * In which case go in the direction of the first move. */
            lheight = ub->BASE_EL(left) ? ub->BASE_EL(left)->BASE_EL(height) : 0;
            rheight = ub->BASE_EL(right) ? ub->BASE_EL(right)->BASE_EL(height) : 0;
            assert( lheight != rheight );
            if (rheight > lheight)
            {
                  ub = ub->BASE_EL(right);
                  lheight = ub->BASE_EL(left) ?
                              ub->BASE_EL(left)->BASE_EL(height) : 0;
                  rheight = ub->BASE_EL(right) ? 
                              ub->BASE_EL(right)->BASE_EL(height) : 0;
                  if (rheight > lheight)
                        ub = ub->BASE_EL(right);
                  else if (rheight < lheight)
                        ub = ub->BASE_EL(left);
                  else
                        ub = ub->BASE_EL(right);
            }
            else
            {
                  ub = ub->BASE_EL(left);
                  lheight = ub->BASE_EL(left) ? 
                              ub->BASE_EL(left)->BASE_EL(height) : 0;
                  rheight = ub->BASE_EL(right) ? 
                              ub->BASE_EL(right)->BASE_EL(height) : 0;
                  if (rheight > lheight)
                        ub = ub->BASE_EL(right);
                  else if (rheight < lheight)
                        ub = ub->BASE_EL(left);
                  else
                        ub = ub->BASE_EL(left);
            }


            /* rebalance returns the grandparant of the subtree formed
             * by the element that were rebalanced.
             * We must continue upward from there rebalancing. */
            fixfrom = rebalance(ub);

            /* Find the next unbalaced element. */
            ub = findFirstUnbalEl(fixfrom);
      }

      return element;
}


Generated by  Doxygen 1.6.0   Back to index