Un problema particolare con l'inserimento btree

Question

Ho giocato con l'applet btree molto fresco a slady.net. Ho difficoltà a capire un particolare comportamento. Dai un'occhiata a questo stato di partenza:

alt text http://www.freeimagehosting.net/uploads/db2931c7da.jpg

Questo stato particolare è stata raggiunta inserendo la seguente sequenza: 10, 15, 30, 16, 70, 1, 9, 27, 45, 50, 55 .

mia domanda riguarda ciò che accade al nodo [45,] quando inserisco il valore successivo nella sequenza, 65.

alt text http://www.freeimagehosting.net/uploads/3b70c1d302.jpg

la [55,70] nodo verrà diviso da il 65, e essendo il valore medio, t egli 65 tornerà indietro e quindi dividerà anche il nodo [30,50]. La mia domanda è: perché il nodo [45,] finisce con un figlio del nodo [30,]? Originariamente il genitore aveva 3 figli, il più a sinistra e quello a destra diventavano nuovi nodi separati. Il 45 era tra quei valori e sembra che avrebbe potuto finire sotto il nodo [65,] altrettanto bene ... Perché?

Answer 1

Un'immagine vale più di mille parole; un'animazione vale un milione:

http://constellationmedia.com/~funsite/static/btree-insert-animation.gif

La cosa fondamentale da notare qui è che quando il nodo centrale 50 è tirato su, deve buttare via il suo figlio destro perché è troppo in basso. Tuttavia, 65 ha bisogno di un nuovo figlio di sinistra, quindi 50 mani da 45 a 65. 50 ora ha bisogno di un nuovo figlio destro, e il nodo contenente 65 deve essere childed, quindi prende il neo formato 65 al suo posto.

regole di inserimento dei B-tree Qui sono illustrate (in cui dimensione massima nodo è 4 oggetti, 5 nodi figli):

http://constellationmedia.com/~funsite/static/btree-insertion-rules.png

Il xr non esisterà e non importa se sei inserendo in una foglia (che fai prima). Tuttavia, se devi dividere un nodo a metà, il nuovo x è l'elemento centrale che hai estratto e il nuovo xr è il figlio corretto di x.

Answer 2

Non ha senso che il nodo 45 sia un figlio del nodo 65 nel secondo diagramma poiché il ramo più a destra è per valori> 50 (in base al valore più a destra del nodo radice) - quindi 45 deve andare nel ramo centrale da qualche parte.

Answer 3

Ogni nodo ha sempre n + 1 bambini, dove n è il numero di chiavi in ​​quel nodo.

Prima divisione, il nodo [30, 50] ha due chiavi e tre bambini, come previsto. Quando lo dividi, finisci con un nodo [30, -] e un nodo [65, -] (e spingi il 50 su un livello).

Al livello successivo in basso, si hanno i nodi [16, 27] e [45, -] precedentemente esistenti [55, -] e [70, -].

Hai due nodi padre e quattro bambini. Ogni genitore deve avere due figli perché ha una sola chiave. Pertanto, date le regole di ordinamento, [45, -] deve essere un figlio di [30, -] perché altrimenti (1) [30, -] non avrebbe abbastanza bambini, e (2) [65, -] avrebbe troppi bambini [EDIT - non illegalmente troppi per un nodo, ma la divisione dovrebbe essere bilanciata].

Anche A è corretto. Questa è una conseguenza della scelta di premere il tasto 50 durante la divisione del nodo del livello intermedio, ma questa non era una scelta. La divisione per produrre [-, -] e [50, 65] spingendo verso l'alto 30, o [30, 50] e [-, -] spingendo verso l'alto 65 violerebbe la regola che ogni nodo deve essere almeno mezzo pieno.