[C] Nodo Random da BST

[L\'Esecutore]

Come da titolo, partendo da un albero mi serve una funzione che peschi un nodo a caso. Come faccio?

[yorkeiser]

Basta un semplice algoritmo di visita (simmetrica, in preordine o postordine) che in più incrementa un contatore ad ogni nodo visitato e si ferma quando il contatore è pari a un numero che avrai inizializzato randomicamente, stando attento a non farlo eccedere la dimensione effettiva dell'albero (se non è nota, questa la calcoli ugualmente con qualunque un algoritmo di visita). Una volta che ottieni l'eguaglianza contatore-numero preinizializzato, ritorni il nodo che stai visitando.

[L\'Esecutore]

Ma l'albero dovrebbe essere bilanciato, purtroppo non lo è

[yorkeiser]

O sono arrugginito o non ho capito il problema, cosa cambia se l'albero è bilanciato o meno ? Con gli algoritmi di visita visiti ogni nodo una volta sola, quindi hai le stesse probabilità di beccare qualsiasi nodo a prescindere del bilanciamento (ovviamente, avendo l'accortezza di scegliere un randomico minore uguale della effettiva dimensione dell'albero)

[L\'Esecutore]

Non centra nulla :doh: scusami, colpa mia che ho letto di fretta e ho capito tutt'altro.
Dovrebbe andare bene, grazie mille

[yorkeiser]

Tranquillo, ero io a non essere sicuro di aver capito bene il problema ;)
Di niente, figurati ;)