Trovare il valore minimo di un albero 2-3-4

Question

Prima di tutto, questa domanda non è compiti a casa.Sto leggendo il libro "Data Structures and Algorithms 2nd Edition" di Robert Lafore.Nel capitolo 10, abbiamo imparato a conoscere 2-3-4 alberi e ci viene quindi chiesto di scrivere un metodo per trovare il valore minimo in detto albero.

Da un punto di vista concettuale, capisco dove si trova il valore minimo.È solo l'elemento di dati più a sinistra in una foglia.

Dal punto di vista della programmazione, sono un po ' confuso su come implementare un metodo per trovare questo elemento di dati.Ho un booleano che può dire se il nodo è una foglia.Quindi quello che ho fatto inizialmente era questo:

  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()

Quello che fa (almeno quello che penso dovrebbe fare, è creare un curNode che inizia dal nodo radice.Quindi creare un valore min che memorizza curNode.getMin.getMin () ottiene solo il valore nell'array all'indice 0 (dove dovrebbe essere tenuto il valore più basso).Quindi, mentre il nodo corrente non è una foglia, dovremmo attraversare il figlio successivo dal punto minimo.Una volta che il nodo corrente è una foglia, dovrebbe restituire il valore minimo.

Questo non funziona però.Qualcuno ha un'idea su come implementare questo?Suggerimenti o suggerimenti o qualsiasi altra cosa?

Modificare:Per vedere ciascuna delle classi e come interagiscono, ecco i collegamenti a ciascuna classe separata.Ho inserito il metodo del valore minimo nella mia classe Tree234

Dati, Nodo, Albero234, e dove il programma è eseguito, Tree234App

Answer 1

In primo luogo, per un aiuto migliore prima, postare un SSCCE questo ci dà un'implementazione minima dell'intero programma-qualcosa che possiamo c / p nel nostro IDE ed eseguire noi stessi per vedere cosa sta succedendo.È difficile dire perché "questo non funziona" quando vediamo solo questo bit del tuo codice.

In secondo luogo, è necessario approfondire cosa significa "questo non funziona", ad es.dicci esattamente cosa sta facendo o non facendo che è inaspettato.Al posto di te che lo hai fatto, come potremmo dirti con un certo grado di certezza perché lo sta facendo?

Tuttavia, una cosa salta fuori:Stai istanziando min come il più piccolo (diretto) figlio del nodo radice, quindi (presumibilmente) iterando attraverso l'albero per trovare l'elemento più a sinistra in esso, ma poi stai restituendo lo stesso min valore creato inizialmente.In altre parole, mentre la tua routine iterativa potrebbe fare esattamente quello che vuoi, non stai facendo nulla per il valore restituito come risultato di esso.

Sospetto che tu debba fare qualcosa del genere:

  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;

Si noti che l'unica modifica che ho apportato è stata l'inserimento della riga sopra l'istruzione return, che riassegna min al valore minimo collegato all'elemento più a sinistra nell'albero.

Answer 2

Per ulteriori efficienza, si noti che non è necessario chiamare getNextChild(curNode, min), poiché gli elementi del nodo sono sempre ordinati in ordine crescente in 2-3-4 albero e l'oggetto più piccolo è sempre in indice 0.Anche la dichiarazione di minimo non è necessaria all'inizio.Quindi il tuo programma potrebbe essere così:

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

.