5
Quali sono il numero massimo e minimo di nodi in un albero di suffisso? E come posso dimostrarlo?Numero massimo e minimo di nodi in un albero suffisso
A
risposta
6
Ipotizzando un testo di input di N caratteri di lunghezza, il numero minimo di nodi, compresi il nodo radice e tutti i nodi foglia, è N+1, il numero massimo di nodi, tra cui la radice e foglie, è 2N-1.
Prova di minimo: Ci deve essere almeno un nodo foglia per ogni suffisso e ci sono i suffissi N. Non c'è bisogno di essere qualsiasi nodo interno, esempio: se il testo è una sequenza di simboli unici, abc$, ci sono rami, quindi nessun nodo interno nella struttura suffisso risultante:
Quindi il minimo è N foglie, 0 nodi interni e il nodo radice 1, nella somma N+1 nodi.
Prova di massima: Il numero di nodi foglia non può mai essere maggiore di N, perché un nodo foglia è dove finisce un suffisso, e non è possibile avere più di N suffissi distinti in una stringa di lunghezza N. (In effetti, hai sempre esattamente i suffissi distinti N, quindi i nodi foglia N esattamente.) Il nodo radice è sempre esattamente 1, quindi la domanda è qual è il numero massimo di nodi interni. Ogni nodo interno introduce un ramo nell'albero (poiché i nodi interni di un albero di suffisso hanno almeno 2 figli). Ogni nuovo ramo deve eventualmente condurre ad almeno un nodo foglia in più, quindi se si dispone di nodi interni K, devono essere presenti almeno i nodi foglia K+1 e la presenza del nodo radice richiede almeno un'ulteriore foglia (a meno che l'albero non sia vuoto). Ma il numero di nodi foglia è limitato da N, quindi il numero massimo di nodi interni è limitato da N-2. Questo produce esattamente N foglie, radice 1 e un massimo di N-2 nodi interni, 2N-1 in totale.
Per vedere che questo non è solo un limite superiore teorico, ma alcuni alberi di suffisso raggiungono effettivamente questo valore massimo, consideriamo come esempio una stringa con un solo carattere ripetuto: 'aaa $'. Confermare che l'albero suffisso per questo ha 7 nodi (compresi radice e foglie):
Sommario: Come evidente, l'unica variabile reale è il numero di nodi interni; il numero di radici e foglie è costante a 1 e N per tutti gli alberi di suffisso, mentre il numero di nodi interni varia tra 0 e N-2.
+0
Grazie! Questo aiuta davvero molto! –
Benvenuti in Stack Overflow e grazie per la pubblicazione. Si prega di includere del codice per mostrare [cosa si è provato] (http://whathaveyoutried.com) e dare un'occhiata a [Come chiedere] (http://stackoverflow.com/questions/how-to-ask). –
Questo è un duplicato di questa domanda: http://stackoverflow.com/questions/12865639/maximum-and-minimum-number-of-edges-in-a-suffix-tree –
Che sono i bordi, voglio saperlo per i nodi. Non c'è nulla da implementare, devo solo sapere quanti nodi ci possono essere in un albero di suffisso. –