Numero massimo e minimo di nodi in un albero suffisso

Question

Quali sono il numero massimo e minimo di nodi in un albero di suffisso? E come posso dimostrarlo?

Answer 1

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.