Encontrando o valor mínimo de uma árvore 2-3-4

Question

Em primeiro lugar, esta questão não é lição de casa.Atualmente estou lendo o livro "Estruturas de Dados e Algoritmos 2ª Edição" de Robert Lafore.No capítulo 10, aprendemos sobre árvores 2-3-4 e então fomos solicitados a escrever um método para encontrar o valor mínimo nessa árvore.

Do ponto de vista conceitual, entendo onde está o valor mínimo.É apenas o item de dados mais à esquerda de uma folha.

Do ponto de vista da programação, estou um pouco confuso sobre como implementar um método para encontrar esse item de dados.Eu tenho um booleano que pode dizer se o nó é uma folha.Então o que eu fiz originalmente foi isso:

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

O que isso faz (pelo menos o que eu acho que deveria fazer) é criar um curNode que começa no nó raiz.Em seguida, crie um valor mínimo que armazene curNode.getMin.getMin() apenas obtém o valor do array no índice 0 (onde o valor mais baixo deve ser mantido).Então, embora o nó atual não seja uma folha, devemos passar para o próximo filho a partir do ponto mínimo.Uma vez que o nó atual seja uma folha, ele deverá retornar o valor mínimo.

Mas isso não funciona.Alguém tem uma idéia de como implementar isso?Dicas ou sugestões ou qualquer outra coisa?

Editar:Para ver cada uma das classes e como elas interagem, aqui estão os links para cada classe separada.Coloquei o método de valor mínimo na minha classe Tree234

Item de dados, Nó, Árvore234, e onde o programa é executado, Tree234App

Answer 1

Primeiro, para melhor ajuda mais cedo, poste um SSCCE isso nos dá uma implementação mínima de todo o seu programa - algo que podemos colocar em nosso próprio IDE e executar para ver o que está acontecendo.É difícil dizer por que "isso não funciona" quando vemos apenas esta parte do seu código.

Em segundo lugar, você precisa explicar o que significa "isso não está funcionando" - ou seja,diga-nos exatamente o que está fazendo ou não de inesperado.Em vez de você ter feito isso, como poderíamos dizer com algum grau de certeza por que isso está acontecendo?

No entanto, uma coisa salta à vista:Você está instanciando min como o menor filho (direto) do nó raiz, então (presumivelmente) iterando pela árvore para encontrar o elemento mais à esquerda nela, mas então você está retornando o mesmo min valor que você criou inicialmente.Em outras palavras, embora sua rotina iterativa possa estar fazendo exatamente o que você deseja, você não está fazendo nada no valor de retorno como resultado disso.

Eu suspeito que você precisa fazer 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;

Observe que a única alteração que fiz foi inserir a linha acima da instrução return, que reatribui min ao valor mínimo anexado ao elemento mais à esquerda na árvore.

Answer 2

Para maior eficiência, observe que você não precisa ligar getNextChild(curNode, min), já que os itens no nó são sempre classificados em ordem crescente na árvore 2-3-4 e o menor item está sempre no índice 0.A declaração de min também não é necessária no início.Então seu programa poderia ser assim:

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