А>Грубовато. Вы же просите всё таки, не так ли?

int delete_symbol( struct symbol_table *table, char *id, FREE_NODE_DATA free_data )
{
   int           remove_flag = 1;
   struct node  *x, *y,   *z = lookup( table, id );

   /* delete node z tree */
   if( !z || z == NIL ) return( 0 ); /* Not found */

   if( z->left == NIL || z->right == NIL )
   {
      /* y has a NIL node as a child */
      y = z;
   }
   else
   {
      /* find tree successor with a NIL node as a child */
      y = z->right;
      while( y->left != NIL ) y = y->left;
   }

   /* x is y's only child */
   if( y->left != NIL ) x = y->left;
   else                 x = y->right;

   /* remove y from the parent chain */
   x->parent = y->parent;
   if( y->parent )
   {
      if( y == y->parent->left ) y->parent->left  = x;
      else                       y->parent->right = x;
   }
   else
   {
      table->root = x;
   }
   if( y != z )
   {
      /******************************************************
        Здесь мы делаем перенос данных.
       ******************************************************/
      if( z->id ) free( z->id );
      if( free_data ) free_data( z->data );

      z->id   = y->id;
      z->data = y->data;

      remove_flag = 0;
   }

   if( y->color == BLACK ) delete_fixup( table, x );

   if( remove_flag )
   {
      if( y->id ) free( y->id );
      if( free_data ) free_data( y->data );
      free( y ); 
   }
   else
   {
      /**************************************************
        А здесь делаем подмену узлов.
       **************************************************/
      y->left          = z->left;
      y->left->parent  = y;

      y->right         = z->right;
      y->right->parent = y;

      y->parent = z->parent;
      if( y->parent->left  == z ) y->parent->left  = y;
      if( y->parent->right == z ) y->parent->right = y;

      y->color  = z->color;

      free( z ); 
   }

   return( 1 );

} /* End of delete_symbol() */

Покоцано излишнее цитирование и отформатирован код. С надеждой на понимание — Odi$$ey

  If (nodeParent != node) Then
  Begin
    node.key = nodeParent.key;
    node.color = nodeParent.color;
    { копирование дополнительных данных }
  End

  If (nodeParent != node) Then
  Begin
    If (node.parent.left == node)
     swap(node.parent.left, nodeParent);
    Else
     swap(node.parent.right, nodeParent);
  End

lpCTree->key = lpCDelete->key;
lpCTree->data = lpCDelete->data;

if (C_Node::IsNull(lpCTree->lpCParent))
{
    lpCTree->key = lpCDelete->key;
    lpCTree->data = lpCDelete->data;
}
else
{
    if (lpCTree->lpCParent->lpCLeft == lpCTree)
    {
        lpCTree->lpCParent->lpCLeft = (C_Node *)&C_Node::nil;
    }
    else
    {
        lpCTree->lpCParent->lpCRight = (C_Node *)&C_Node::nil;
    }
    lpCDelete = lpCTree;    
}

W>Хотелось бы посмотреть на графики, то есть таблицы , 7-12 когда в массиве хранят не сами элементы, а указатели на них.

class node
 {
  KEY key;
  DATA data;
  node * left;
  node * right;
  node * parent;
 };

class node
 {
  KEY key;
  DATA * data;
  node * left;
  node * right;
  node * parent;
 };

class autoptr
 {
        private:
            char * ptr;
        public:
            autoptr()
                {
                    ptr = new char[256];
                }
            autoptr(unsigned int)
                {
                    ptr = new char[256];
                }
            autoptr(const autoptr & ap)
                {
                    ptr = new char[256];
                    memmove(ptr, ap.ptr, 256);
                }
            ~autoptr()
                {
                    delete [] ptr;
                }
            autoptr & operator = (const autoptr & ap)
                {
                    delete [] ptr;
                    ptr = new char[256];
                    memmove(ptr, ap.ptr, 256);
                    return *this;
                }
 };

W>>Хотелось бы посмотреть на графики, то есть таблицы , 7-12 когда в массиве хранят не сами элементы, а указатели на них.

A>class node
A> {
A>  KEY key;
A>  DATA data;
A>  node * left;
A>  node * right;
A>  node * parent;
A> };
A>

A>class node
A> {
A>  KEY key;
A>  DATA * data;
A>  node * left;
A>  node * right;
A>  node * parent;
A> };
A>

A>Плюс ко всему добавятся тормоза из-за того, что вы будете выделять на каждую вершину по два блока памяти. Для всего кроме данных и для данных. Ну даладно, это уже домыслы

typedef int KEY;
typedef float DATA;

class node
{
  friend class pnode;
  KEY key;
  DATA data;
  //node * left;
  //node * right;
  //node * parent;
public:
    node( KEY k, DATA d ): key( k ), data( d ) {}
};

class pnode
{
    node * m_pNode;
public:
    pnode( node * pn ): m_pNode( pn ){}
    bool operator < ( const pnode& pn )const
    {
        return m_pNode->key < pn.m_pNode->key;
    }
};

void TestArrayWithPostSort( unsigned int number )
{
  std::vector< pnode > vec;
  vec.reserve( number );
  for( unsigned int index = 0; index < number; index++ )
  {
    vec.push_back( pnode( new node( KEY( index ), DATA( index ) ) ) );
  }
  std::sort( vec.begin(), vec.end() );
    // далее тесты
}