Questão 3551358

A árvore ______ é construída a partir da árvore binária de prefixo. Seja um conjunto de chaves {s1, …, sn} de valores binários tais que nenhuma chave seja prefixo de outra. Considere a árvore binária de prefixo correspondente a essas chaves apresentada na figura a seguir. Sabendo que as chaves válidas se encontram nas folhas da árvore, e admitindo-se de início, que a chave procurada z seja uma chave sempre válida. Agora o processo em questão é buscar a chave z = s4 na árvore. A partir do valor binário de z, o algoritmo percorrerá o caminho 11100 na árvore, iniciando pela raiz. Se z é uma chave válida, após se assegurar de que os dois primeiros dígitos de z são 11 não há alternativa para os dois seguintes, pois correspondem a nós com um único filho. Então, neste caso, a busca poderia eliminar o terceiro e o quarto teste de dígitos, pois, certamente será produzido 10. Em outras palavras, do segundo dígito da chave poderia se prosseguir diretamente para o quinto.

Assinale a alternativa que preencha corretamente a lacuna do texto acima.