Quanti alberi di ricerca binaria possono essere costruiti da n elementi distinti? E come possiamo trovare una formula matematicamente provata per questo?Numero di alberi di ricerca binaria su n elementi distinti
Esempio: Se abbiamo 3 elementi distinti, dire 1, 2, 3, ci sono 5 alberi binari di ricerca.
Dato n elementi, il numero di alberi binari di ricerca che possono essere fatte da tali elementi è dato dalla ennesimo Catalan number (C denotato n). Questo è uguale a
Intuitivamente, i numeri di Catalan rappresentano il numero di modi in cui è possibile creare una struttura di n elementi che è fatto nel seguente modo:
Questo schema corrisponde perfettamente ai modi in cui è possibile creare un BST da un insieme di n elementi. Scegli un elemento da utilizzare come radice dell'albero. Tutti gli elementi più piccoli devono andare a sinistra e tutti gli elementi più grandi devono andare a destra. Da lì, puoi costruire BST più piccoli dagli elementi a sinistra e a destra, quindi fonderli insieme al nodo radice per formare un BST generale. Il numero di modi in cui è possibile farlo con n elementi è dato da C n, e quindi il numero di possibili BST è dato dall'ennesimo numero Catalano.
Spero che questo aiuti!
Ad esempio per i nodi 10, 10, 10 il numero di alberi di ricerca binari è 1. Ma il numero Catalano è 5. Ma se tutti gli elementi sono diversi, va bene, penso. –
@ SukhanovNiсkolay Il numero di BST è ancora 5 per 10,10,10. La forma dell'albero sarà diversa. – rents
Sia T (n) il numero di valori di n elementi.
Dato n elementi ordinati distinti, numerati da 1 a n, selezioniamo i come radice.
Questo lascia (1..i-1) nella sottostruttura di sinistra per le combinazioni T (i-1) e (i + 1..n) nella sottostruttura di destra per le combinazioni T (n-i).
Pertanto:
T(n) = sum_i=1^n(T(i-1) * T(n-i))
e naturalmente T (1) = 1
Potrebbe essere utile ricordare che questa ricorrenza risolve l'ennesimo numero catalano. – templatetypedef
@templatetypedef: Sai come derivare la formula del numero catalano a partire dalla somma che ho mostrato? –
@ user1131467 Questa somma deve essere esattamente il numero di triangolazioni di un poligono su n + 2 nodi, che è il modo in cui sono stato introdotto ai numeri catalani. Si fissa un bordo e si lascia vagare il perno sugli altri n vertici, che ti lascia con due poligoni di dimensioni i-1 e n-i. –
Sono sicuro che questa domanda non è solo quello di contare con una formula matematica .. Ho preso qualche tempo e ha scritto il programma e la spiegazione o l'idea dietro il calcolo per lo stesso.
Ho provato a risolverlo con ricorsione e programmazione dinamica entrambi. Spero che questo ti aiuti.
La formula è già presente nella risposta precedente:
Quindi, se siete interessati ad imparare la soluzione e la comprensione del suddetto approccio si può sempre controllare il mio articolo Count Binary Search Trees created from N unique elements
Probabilmente [relativo] (http: // stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib). –