Encontrar el valor mínimo de un árbol 2-3-4

Question

En primer lugar, esta pregunta no es tarea.Actualmente estoy leyendo el libro "Estructuras de datos y algoritmos, segunda edición" de Robert Lafore.En el capítulo 10, aprendimos sobre 2-3-4 árboles y luego se nos pidió que escribiéramos un método para encontrar el valor mínimo en dicho árbol.

Desde el punto de vista conceptual, entiendo dónde está el valor mínimo.Es simplemente el elemento de datos más a la izquierda de una hoja.

Desde el punto de vista de la programación, estoy un poco confundido sobre cómo implementar un método para encontrar este elemento de datos.Tengo un booleano que puede decir si el nodo es una hoja.Entonces lo que hice originalmente fue esto:

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

Lo que esto hace (al menos lo que creo que debería hacer) es crear un curNode que comience en el nodo raíz.Luego cree un valor mínimo que almacene curNode.getMin.getMin() simplemente obtiene el valor de la matriz en el índice 0 (donde se debe mantener el valor más bajo).Luego, aunque el nodo actual no sea una hoja, debemos pasar al siguiente hijo desde el punto mínimo.Una vez que el nodo actual sea una hoja, debería devolver el valor mínimo.

Aunque esto no funciona.¿Alguien tiene una idea sobre cómo implementar esto?¿Consejos o sugerencias o algo más?

Editar:Para ver cada una de las clases y cómo interactúan, aquí hay enlaces a cada clase por separado.Puse el método de valor mínimo en mi clase Tree234

Elemento de datos, Nodo, árbol234, y donde se ejecuta el programa, Árbol234App

Answer 1

Primero, para obtener una mejor ayuda lo antes posible, publique un SSCCE eso nos brinda una implementación mínima de todo su programa, algo que podemos incluir en nuestro propio IDE y ejecutar nosotros mismos para ver qué está pasando.Es difícil saber por qué "esto no funciona" cuando solo vemos esta parte de su código.

En segundo lugar, es necesario explicar qué significa "esto no funciona", es decir,díganos exactamente qué está haciendo o no haciendo que sea inesperado.En lugar de que usted lo haya hecho, ¿cómo podríamos decirle con algún grado de certeza por qué lo está haciendo?

Sin embargo, salta a la vista una cosa:estas instanciando min como el hijo más pequeño (directo) del nodo raíz, luego (presumiblemente) itera a través del árbol para encontrar el elemento más a la izquierda en él, pero luego devuelves lo mismo min valor que creaste inicialmente.En otras palabras, si bien su rutina iterativa puede estar haciendo exactamente lo que usted desea, no está haciendo nada con el valor de retorno como resultado de ello.

Sospecho que necesitas hacer algo como:

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

Tenga en cuenta que el único cambio que hice fue insertar la línea encima de la declaración de devolución, que reasigna min al valor mínimo adjunto al elemento más a la izquierda del árbol.

Answer 2

Para mayor eficiencia, tenga en cuenta que no necesita llamar getNextChild(curNode, min), ya que los elementos del nodo siempre se ordenan en orden ascendente en el árbol 2-3-4 y el elemento más pequeño siempre está en el índice 0.La declaración de min tampoco es necesaria al inicio.Entonces tu programa podría ser así:

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}