Vai al contenuto principale
← OlimpiApp Olimpico

Informatica · Strutture dati

Parole la cui rimozione riduce i nodi di un trie

Si costruisce un trie (albero dei prefissi) inserendo, una alla volta, le parole PORTA, PORTALE, PORTIERE, PORCO, PORRO, PORTATILE (partendo da una radice vuota; ogni carattere non ancora presente sul cammino crea un nuovo nodo figlio, i caratteri già presenti vengono riutilizzati).

Si considera ora, per ciascuna delle $6$ parole, l'operazione di rimozione di quella sola parola dal trie (ripartendo ogni volta dall'insieme completo delle $6$ parole, e rimuovendo un nodo solo se non è più necessario per nessun'altra delle parole rimanenti). Per quante delle $6$ parole questa rimozione fa diminuire il numero totale di nodi del trie?

La tua risposta

Vanno bene sia 3,14 sia 3.14.