[Algoritmi] contare occorrenze nodi albero binario

[xneo1]

Ciao a tutti,

Dovrei implementare un algoritmo che dato in ingresso un albero binario che contiene nodi con valori interi restituisca un valore intero che è la somma delle occorrenze dei valori che compaiono almeno 2 volte.

Vi faccio un esempio.

Siano i seguenti i valori dei nodi contenuti nell'albero:

1,2,1,1,4,0,4,3

L'algoritmo restituirà 5

Infatti 1 compare 3 volte e 4 compare 2 volte, tutti gli altri (2,0,3 non vanno considerati perchè compaiono meno di 2 volte)

A me è venuta in mente questo tipo di ragionamento:

1) visito l'albero è metto man mano gli elementi in una lista
2) conto le occorrenze per ogni valore nella lista e le sommo opportunamente

Questo tipo di soluzione nel caso peggiore impiega tempo O(n^2)

C'è qualche altra soluzione più elegante e sopratutto più efficiente?

[apatriarca]

L'algoritmo più semplice è probabilmente il seguente:
1. Inserire tutti i valori in un array.
2. Ordinare l'array.
3. Visitare tutti i valori di un array: se il valore corrente è uguale a quello precedente ma diverso da quello ancora prima sommi tale valore al tuo contatore.
La complessità è O(n\,log(n)) o O(n) a seconda della complessità dell'algoritmo di ordinamento usato.

Usando delle hash-table puoi invece fare il seguente. Visiti l'albero inserendo i valori in una hash-table tenendo traccia del numero di volte che l'elemento è comparso. Quando questo valore è uguale a due sommi tale valore al contatore. La complessità di questo è O(n).

[xneo1]

Oppure potrei trovarmi il max all'interno dell'albero, creare un array di dimensione max+1 (suppongo che i nodi siano maggiori o uguali a 0) e visitando l'albero incrementare la cella array[nodo.val]. Al termine della visita sommo i contenuti delle celle solo se sono maggiori o uguali a 2.

Anche se la complessità spaziale potrebbe aumentare molto (se max >> n), per ciò che riguarda la complessità spaziale rimarrebbe lineare.