Skiena del libro en el Algoritmo contiene la siguiente pregunta:

1) Evaluar la expresión dada como árbol binario en O(n) en el tiempo, dado n nodos.

2) Evaluar la expresión dada como DAG en O(n+m), el tiempo, dado n nodos y m de los bordes en la DAG.

La evaluación de la expresión de los árboles

Podía pensar en una forma para la primera pregunta:

evaluate(node) {
     if(node has children){
          left_val = evaluate(node->left);
          right_val = evaluate(node->right);

          //find operation symbol for node and use it as
          //val = left_val operation right_val

          return val;
     }
     else {
          return node_value;
     }
}

Desde que nos visita cada nodo de una vez, va a tomar O(n) tiempo.

Ya que el libro no tiene soluciones, puede alguien por favor decirme si esto es correcto ?

También puede alguien sugerir una solución para la segunda pregunta.

Gracias.

InformationsquelleAutor Jake | 2012-05-26

1 Comentario

  1. 5

    Primera forma en la que se ve bien para mí.

    Para el DAG, si puedes modificar el árbol para agregar valores almacenados en la caché para cada nodo, se puede utilizar el mismo algoritmo con un pequeño retoque a no recurse si un operador nodo tiene un valor almacenado en caché. Este debe ser O(n+m) tiempo (en la mayoría de una operación aritmética por nodo y a más de un puntero de búsqueda por el borde). Explícitamente:

    evaluate(node) {
         if (node has value) {
              return node->value;
         } else {
              left = evaluate(node->left);
              right = evaluate(node->right);
    
              //find operation symbol for node and use it as
              //val = left_val operation right_val
    
              node->value = val;
              return val;
         }
    }
    

Dejar respuesta

Please enter your comment!
Please enter your name here