Dato n chiavi distinte, quanti diversi alberi 2-3 / Red-black possono essere costruiti?

Question

#1 da (2 voti)

2

Aggiornamento della memoria / La mia comprensione:

Un albero 2-3 è un albero di ricerca bilanciato che consente due tipi di nodi.

2 nodi: nodo normale con due figli.
- LChild < Parent e RChild > Parent
3 nodi: nodo con due genitori e tre figli.
- Parent1 < Parent2
- LChild < Parent1, Parent1 < MChild < Parent2, RChild > Parent2

Un albero 2-3 è sempre bilanciato e cresce quando la radice aumenta di un altezza l'albero.

La mia domanda è quindi la seguente, date n chiavi distinte, quanti 2-3 alberi diversi possono essere costruiti?

Le mie abilità matematiche sono scarse, quindi se qualcuno sa come dovrei "matematica" per avvicinarsi a una risposta, sarebbe fantastico! :)

algorithms

posta user3298921 11.02.2014 - 21:48

fonte

Leggi altre domande sui tag algorithms

score 2 · Answer 1

Lascia che T[n] sia il numero di 2-3 alberi con n chiavi. Abbiamo:

T[n] = somma con k da 1 a n di T[k - 1] * T[n - k] , perché possiamo creare un nodo 2 con la chiave k , con l'albero di sinistra con le chiavi 1, ..., k - 1 e albero giusto con le chiavi k + 1, ..., n . Per ogni disposizione dell'albero di sinistra, abbiamo le disposizioni dell'albero giusto, quindi dobbiamo moltiplicare le due. Questo vale quando abbiamo a che fare con 2 nodi;
T[n] + = somma con k da 1 a n di somma con p da k + 1 a n di T[k - 1] * T[p - k - 1] * T[n - p] . Questo vale quando abbiamo a che fare con i 3 nodi;

Il caso base è T[0] = 1 .