B-Tree - Perché non può esserci un nodo con un numero pari di chiavi?

Question

Sto cercando di implementare un B-Tree in base al capitolo "B-Trees" in "Introduzione agli algoritmi".

Quello che non capisco è il "grado minimo". Nel libro si afferma che il grado è un numero che esprime il limite inferiore/superiore per il numero di chiavi che un nodo può contenere. E si dice inoltre che:

1. ogni non-root negozi nodo almeno t - 1 chiavi e ha t figli.
2. Ogni nodo memorizza al massimo 2*t - 1 chiavi e ha 2*t bambini.

in modo da ottenere per t = 2:

1. t - 1 = 1 chiavi e t = 2 bambini
2. 2*t - 1 = 3 chiavi e 4 bambini

Per t = 3

1. t - 1 = 2 tasti e t = 3 ch ildren
2. 2*t - 1 = 5 tasti e 6 bambini

Ora qui è il problema: sembra che i nodi di un B-Tree può memorizzare solo un dispari numero di tasti quando sono pieni.

Perché non può esserci un nodo con, diciamo al massimo 4 tasti e 5 bambini? Ha qualcosa a che fare con la divisione del nodo?

Answer 1

Sembra che i nodi in un B-Tree possano solo memorizzare un numero dispari di chiavi?

Decisamente no. I numeri che hai scritto sono rispettivamente il numero minimo e massimo di tasti, quindi per t = 2, i nodi con 1, 2, 3 tasti sono consentiti. Per t = 3, sono consentiti i nodi con 2, 3, 4, 5 tasti.

Inoltre, la radice dell'albero può contenere solo 1 chiave.

È possibile definire (e implementare) alberi che hanno ad es. 1 o 2 chiavi in ​​un nodo (i cosiddetti 2-3 alberi). Il motivo per cui gli alberi B sono definiti per ospitare un altro, è che questo porta a prestazioni più veloci. In particolare, ciò consente di ammortizzare O(1) (conteggio delle operazioni di divisione e unione) cancellare e inserire operazioni.

Answer 2

non è impossibile ma non ottimale. come si divide un nodo con un numero dispari di bambini?