Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
2-3 BTree
Copyright © 2006-2009 by Claudio Salati.
Lez. 14
1
Rappresentazione di alberi
• Negli esercizi si e' visto come, aumentando le informazioni
presenti in un un nodo di albero binario,
 aggiungendo una informazione di dimensione del sottoalbero
sia possibile inserire nuovi elementi in un albero binario
mantenendolo bilanciato.
 N.B.: la procedura di inserimento bilanciato vista negli
esercizi non consente pero' di mantenere ordinato l'albero!
• Negli esercizi si e' anche visto come una infomazione di nodo
arricchita
 l'informazione sull'identita' del proprio genitore
consenta anche una navigazione piu' efficiente nell'albero.
 consente ad esempio di localizzare facilmente nell'insieme
l'elemento immediatamente successivo ad un elemento dato.
2
Cosa si vorrebbe
• quello che si vorrebbe e' potere effettuare inserimenti, rimozioni,
ricerche in un albero ordinato (in termini di valori o in termini di
posizione degli elementi) mantenendolo anche bilanciato
 in realta': mantenendo l'altezza dell'albero logaritmica nel
numero di nodi in esso contenuti.
• notare che un albero potrebbe anche essere visto come una
struttura di indiciamento di un vettore di dimensione dinamica:
 consentendoci in tempo logaritmico di:
• leggere il k-esimo elemento del vettore, se questo elemento
esiste.
• scrivere il k-esimo elemento del vettore, se questo
elemento esiste.
• inserire un nuovo elemento in una qualunque posizione del
vettore (in particolare in fondo al vettore), estendendo cosi’
il vettore.
• eliminare un elemento in una qualunque posizione del
vettore, riducendone cosi' la dimensione.
3
 in realta' e' proprio quello che succede nel file system Unix!
La risposta: BTree
• Un 2-3 BTree e' un albero ordinato con le seguenti proprieta':
• i dati (l'informazione inserita nell'albero) sono contenuti solo
nelle foglie dell'albero (questa e' in realta' una semplificazione).
• tutte le foglie dell'albero si trovano alla stessa profondita'.
• ogni nodo non terminale (che non e' una foglia) ha 2 o 3 figli.
• i nodi non terminali dell'albero mantengono la strutturazione
della base dati.
• Per mantenere la strutturazione della base dati i nodi non terminali
possono/devono contenere informazioni strutturali addizionali.
• Le informazioni mantenute dai nodi non terminali dipendono
dall'ADT che si vuole realizzare tramite il BTree, e.g.:
• un vettore di dimensioni variabili
• una tabella associativa (una mappa chiaveinformazione)
• l'efficienza del BTree e' legata all'informazione strutturale
mantenuta nei nodi non terminali.
4
Informazione strutturale
• Informazione strutturale che puo' essere mantenuta sui nodi non
terminali
• tipo del nodo: non-terminale (per una foglia sarebbe: terminale).
• altezza del nodo (N.B.: sostituisce l’informazione precedente, in
quanto e’ =0 per una foglia, 0 per un nodo non terminale).
• numero di foglie (elementi di informazione) sotteso dal nodo
 per un ADT vettore.
• elemento di informazione minimo e/o massimo contenuto nel
nodo
 per un ADT tabella asoociativa.
• N.B.: ogni nodo mantiene (deve mantenere) informazioni solo sul
proprio sotto-albero.
• E' ovvio che l'informazione mantenuta in un nodo deve essere
aggionata congruentemente quando la struttura del suo sottoalbero viene modificata.
 perche’ aggiungo o cancello una foglia
5
Informazione strutturale
• In quanto appartenenti ad un albero tutti i nodi, terminali o meno,
devono mantenere le relazioni caratteristiche dell'albero stesso:
• relazione padre  figli
• 2 o 3 in caso di nodo non terminale, e ovviamente occorre
anche sapere quanti figli ha il nodo
• 0 in caso di foglia
• relazione figlio  padre
6
BTree: una possibile definizione
struct header {
elemento
int
struct node
max;
size;
*child; };
struct inode {
int
struct header
kidsNo;
children[3]; };
struct node {
int
tipo;
#define ELEMENTO 0
#define NODO
1
union {elemento
val;
struct inode inodo;
}
choice; };
#define STRUCT_NODE (sizeof(struct node))
typedef struct node *bTree;
7
Esempio
• 2-3 BTree in cui viene mantenuta l'informazione sul numero di
foglie (elementi di informazione) sotteso dal nodo.
n0 - 12
n1 - 7
n3 - 2
n4 - 2
e1
e3
e2
n2 - 5
n5 - 3
e4
e5
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
8
Esempio: come si trova il k-esimo elemento?
1
• Supponiamo di volere trovare il valore del k-esimo elemento
informativocontenuto nel BTree, con k=9.
 L’elemento v[9] del vettore v concretamente rappresentato dal
BTree
• parto dal nodo radice n0, e voglio l'elemento di indice 9 nel relativo
sotto-albero
• 9  12: l'elemento esiste
• 9 > 7: l'elemento non e' nel primo sotto-albero di n0
• 9  (7+5): l'elemento e' nel secondo sotto-albero di n0, cioe' n2,
ed e' l'elemento (9-7), cioe' 2, di questo sottoalbero
• Continua alla pagina seguente
9
Esempio: come si trova il k-esimo elemento?
2
• Continua dalla pagina precedente
• vado dal nodo n2, e voglio l'elemento di indice 2 nel relativo sottoalbero
• 2  5: l'elemento esiste
• 2  2 : l'elemento e' nel primo sotto-albero di n2, cioe' n6, ed e'
l'elemento (2-0), cioe' 2, di questo sottoalbero
• vado dal nodo n6, e voglio l'elemento di indice 2 nel relativo sottoalbero
• 2  2: l'elemento esiste
• i figli sono foglie: l'elemento e' la secoda foglia di questo
sottoalbero, cioe' l'elemento e9
10
Complessita' delle operazioni su un 2-3 BTree
• Durante l'operazione abbiamo visitato solo i nodi che vanno dalla
radice alla foglia desiderata.
• cioe' un numero di nodi pari all'altezza dell'albero.
• l'altezza di un 2-3 BTree e'  del logaritmo in base 2 del numero delle
sue foglie, in quanto ogni nodo non terminale ha almeno 2 foglie.
• pertanto, se le operazioni sul BTree coinvolgono solo nodi sul
percorso dalla radice alla foglia selezionata, queste operazioni hanno
complessita O(log(n)) rispetto al numero n di elementi informativi
contenuti nell'albero.
• notare che il numero complessivo di nodi dell'albero puo' arrivare fino
a 2*n-1, essendo che i nodi non terminali sono al piu' n-1.
• Esercizio:
• Quanti nodi ci sono un un 2-3 Btree di altezza h?
• Dualmente, quanto e’ alto un 2-3 Btree che ha n foglie?
11
Ricerca di un elemento (key-based)
struct node *search_2_3(bTree t, elemento e) {
if (t == NULL)
return (NULL);
else if (t->tipo == ELEMENTO)
if (t->choice.val == e) return (t);
else return (NULL);
else { // t->tipo == NODO
for (int k = 0; k < t->choice.inodo.kidsNo; k += 1) {
if (t->choice.inodo.children[k].max >= e)
return
(search_2_3(t->choice.inodo.children[k].child,
e));
// end if
}
return (NULL);
}
}
12
Esempio 1: inserimento di un nuovo elemento
.1
• Supponiamo di volere inserire un nuovo elemento informativo eN
in posizione 4.
n0 - 12
n1 - 7
n3 - 2
e1
e2
n2 - 5
n4 - 2
e3
n5 - 3
e4
e5
n6 - 2
e6
e7
e8
n7 - 3
e9
e10
e11
e12
eN
13
Inserimento di un nuovo elemento
1.2
• Poiche' il nodo n4 ha solo due figli possiamo aggiungergliene
ancora 1.
• Ovviamente occorre aggiornare le informazioni strutturali
contenute in
• n4, che ora contiene 3 foglie,
• n1, che ora contiene 8 foglie, ed
• n0, che ora contiene 13 foglie.
• Notare che si sono dovute aggiornare le informazioni strutturali
solo nei nodi che appartengono al path tra la foglia inserita e la
radice.
• Per cui la complessita' dell'operazione e' O(log(n))
14
Inserimento di un nuovo elemento
1.3
• Inserimento di un nuovo elemento informativo eN in posizione 4.
n0 - 13
n1 - 8
n3 - 2
e1
e2
n2 - 5
n4 - 3
e3
n5 - 3
e4
e5
n6 - 2
e6
e7
e8
n7 - 3
e9
e10
e11
e12
eN
15
Esempio 2: inserimento di un nuovo elemento
1
• Supponiamo di volere inserire un nuovo elemento informativo eN
in posizione 11.
n0 - 12
n1 - 7
n3 - 2
e1
e2
n2 - 5
n4 - 2
e3
e4
n5 - 3
e5
e6
n6 - 2
e7
e8
e9
n7 - 3
e10
e11
e12
eN
16
Inserimento di un nuovo elemento
2.2
• Poiche' il nodo n7 ha gia' 3 figli non possiamo aggiungergliene
ancora 1.
• Quindi il nodo n7 deve essere suddiviso in 2 nodi, n7' e n7",
ciascuno con due figli (e due foglie sottese).
• A questo punto il nodo n2 si trova ad avere 3 figli, il che e'
legittimo.
• Ovviamente occorre correggere le informazioni strutturali di
• n2, che ora contiene 6 foglie, ed
• n0, che ora contiene 13 foglie.
• Notare che
• si sono dovute effettuare suddivisioni, o
• si sono dovute aggiornare le informazioni strutturali
solo nei nodi che appartengono al path tra la foglia inserita e la
radice.
• Per cui la complessita' dell'operazione e' O(log(n))
17
Inserimento di un nuovo elemento
2.3
• Inserimento di un nuovo elemento informativo eN in posizione 11.
n0 - 13
n1 - 7
n3 - 2
e1
e2
n2 - 6
n4 - 2
e3
e4
n5 - 3
e5
e6
n6 - 2
e7
e8
n7' - 2
e9
n7" - 2
e10
e11
e12
eN
18
Esempio 3: inserimento di un nuovo elemento
1
• Supponiamo di volere inserire un nuovo elemento informativo eN
in posizione 7.
n0 - 12
n1 - 7
n3 - 2
e1
e2
n2 - 5
n4 - 2
e3
e4
n5 - 3
e5
n6 - 2
e6
e7
e8
n7 - 3
e9
e10
e11
e12
eN
19
Inserimento di un nuovo elemento
3.2
• Poiche' il nodo n5 ha gia' 3 figli non possiamo aggiungergliene
ancora 1.
• Quindi il nodo n5 deve essere suddiviso in 2 nodi, n5' e n5",
ciascuno con due figli (e due foglie sottese).
• A questo punto pero' il nodo n1 si troverebbe ad avere 4 figli, il che
e' illegittimo, per cui anch'esso andra' suddiviso in due nodi n1' e
n1", entrambi con 2 figli.
• Adesso n0 ha 3 figli, n1', n1" e n2: ma questo e' perfettamente
legittimo.
• Ovviamente occorre correggere le informazioni strutturali di
• n0, che ora contiene 13 foglie.
• Ed occorre anche compilare correttamente le informazioni
strutturali di n1' e n1", indicando il numero corretto di foglie da essi
sottese.
• Sia n1' che n1" contengono quattro foglie
20
Inserimento di un nuovo elemento
3.3
• Notare che, anche in questo caso,
• si sono dovute effettuare suddivisioni, o
• si sono dovute aggiornare le informazioni strutturali
solo nei nodi che appartengono al path tra la foglia inserita e la
radice.
• Per cui la complessita' dell'operazione e' O(log(n))
21
Inserimento di un nuovo elemento
3.4
• Inserimento di un nuovo elemento informativo eN in posizione 7.
n0 - 12
n1' - 4
n3 - 2
e1
e2
n1" - 4
n4 - 2
e3
n5' - 2
e4
e5
n2 - 5
n5" - 2
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
eN
22
Esempio 4: inserimento di un nuovo elemento
1
• Supponiamo di volere inserire un nuovo elemento informativo eN
in posizione 7 nell'albero costituito dai nodi non terminali n0, …,
n3, e dalle foglie e1, …, e7.
n0 - 7
n1 - 2
e1
e2
n2 - 2
e3
e4
n3 - 3
e5
e6
eN
e7
23
Inserimento di un nuovo elemento
4.2
• Poiche' il nodo n3 ha gia' 3 figli non possiamo aggiungergliene
ancora 1.
• Quindi il nodo n3 deve essere suddiviso in 2 nodi, n3' e n3",
ciascuno con due figli (e due foglie sottese).
• A questo punto pero' il nodo n0 si troverebbe ad avere 4 figli, il che
e' illegittimo, per cui anch'esso andra' suddiviso in due nodi n0' e
n0", entrambi con 2 figli.
• Avendo suddiviso la radice dell'albero in due, e' necessario creare
una nuova radice r che abbia n0' e n0" come sotto-alberi
 in questo modo si e' dovuto aumentare di uno l'altezza
dell'albero.
• Ed occorre anche compilare correttamente le informazioni
strutturali di n0', n0" e r indicando il numero corretto di foglie da
essi sottese.
•
sia n0' che n0" contengono quattro foglie.
•
r sottende 8 foglie
24
Inserimento di un nuovo elemento
4.3
• Si ottiene quindi l'albero indicato di sotto.
r-8
n0 - 4
n1 - 2
e1
e2
n0 - 4
n2 - 2
e3
e4
n3' - 2
e5
e6
n3" - 2
eN
e7
25
Inserzione di un elemento (key-based)
struct result {
int
#define NONE
#define TOLEFT
#define TORIGHT
struct header
struct header
newEl;
0
1
2
old;
new; };
26
Inserzione di un elemento (key-based)
struct node *getLeaf(elemento e) {
struct node *temp = malloc(STRUCT_NODE);
temp->tipo = ELEMENTO;
temp->choice.val = e;
return (temp);
}
struct header makeLeafHeader(struct node *n) {
struct header head;
head.size = 1;
head.child = n;
head.max = n->choice.val;
return (head);
}
27
Inserzione di un elemento (key-based)
struct node *getNewNode(struct header h0,
struct header h1) {
struct node *temp = malloc(STRUCT_NODE);
temp->tipo = NODO;
temp->choice.inodo.kidsNo = 2;
temp->choice.inodo.children[0] = h0;
temp->choice.inodo.children[1] = h1;
return (temp);
}
struct header getNodeAndMakeHeader(struct header h1,
struct header h2) {
struct header temp;
temp.size = h1.size + h2.size;
temp.max = h2.max;
temp.child = getNewNode(h1.child, h2.child);
return (temp);
}
28
Inserzione di un elemento (key-based)
void setNONEResult(struct node *n, struct result *res) {
res->newEl = NONE;
res->old.child = n;
if (n->choice.inodo.kidsNo == 2) {
res->old.max = n->choice.inodo.children[1].max;
res->old.size = n->choice.inodo.children[0].size +
n->choice.inodo.children[1].size;
} else { // .kidsNo == 3
res->old.max = n->choice.inodo.children[2].max;
res->old.size = n->choice.inodo.children[0].size +
n->choice.inodo.children[1].size +
n->choice.inodo.children[2].size;
}
}
29
Inserzione di un elemento (key-based)
void setHeader2(struct node *n, struct header *h)
{
h->max = n->choice.inodo.children[1].max
h->size = n->choice.inodo.children[0].size +
n->choice.inodo.children[1].size;
h->child = n;
}
30
Inserzione di un elemento (key-based)
int getPos(struct node*n, elemento e) {
int pos;
for(pos = 0; pos <= n->choice.inodo.kidsNo; pos += 1)
if (e < n->choice.inodo.children[pos].max)
break;
// end if
// end for
return (pos);
}
31
Inserzione di un elemento (key-based)
void insert_2_3(bTree *t, elemento e) {
if (*t == NULL) {
*t = getLeaf(e);
} else if ((*t)->tipo == ELEMENTO) {
struct header oldH = makeLeafHeader(*t);
struct header newH = makeLeafHeader(getLeaf(e));
if (e > (*t)->choice.val) {
*t = getNewNode(oldH, newH);
} else {
*t = getNewNode(newH, oldH);
}
} else {
// tipo == NODO
// continua alla prossima pagina
32
Inserzione di un elemento (key-based)
// continua void insert_2_3(bTree *t, elemento e)
// tipo == NODO
struct result res = nodeInsert(*t, e);
switch (res.newEl) {
case NONE :
break;
case TOLEFT : { *t = getNewNode(res.new,
res.old);
break;
}
case TORIGHT : { *t = getNewNode(res.old,
res.new);
break;
}
}
}
}
33
Inserzione di un elemento (key-based)
struct result nodeInsert(struct node *n, elemento e) {
struct result res;
if (n->choice.inodo.children[0].size == 1) {
// i figli sono foglie
int pos = getPos(n, e);
if (n->choice.inodo.kidsNo == 2) {
// i figli sono foglie e sono 2
for (int shift = 3; shift > pos; shift -= 1)
n->choice.inodo.children[shift] =
n->choice.inodo.children[shift-1];
// end for
n->choice.inodo.children[pos] =
makeLeafHeader(getLeaf(e));
n->choice.inodo.kidsNo = 3;
setNONEResult(n, &res);
} else {
// i figli sono foglie e sono 3
34
// continua nella pagina seguente
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// i figli sono foglie e sono 3
struct header newHead = makeLeafHeader(getLeaf(e));
int pos = getPos(n, e);
if (pos <= 1) {
res.newEl = TOLEFT;
if (pos == 0) {
res.new = getNodeAndMakeHeader
(newHead,
n->choice.inodo.children[0]);
} else {
res.new = getNodeAndMakeHeader
(n->choice.inodo.children[0],
newHead);
}
n->choice.inodo.kidsNo = 2;
n->choice.inodo.children[0] =
n->choice.inodo.children[1];
// continua alla pagina seguente
35
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i figli sono foglie e sono 3
// continua if (pos <= 1)
n->choice.inodo.children[1] =
n->choice.inodo.children[2];
res.old.size = 2;
res.old.max =
n->choice.inodo.children[1].child->choice.val;
res.old.child = n;
} else {
// pos >= 2
// continua alla pagina seguente
36
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i figli sono foglie e sono 3
// pos >= 2
res.newEl = TORIGHT;
if (pos == 2) {
res.new = getNodeAndMakeHeader
(newHead,
n->choice.inodo.children[2]);
} else {
res.new
= getNodeAndMakeHeader
(n->choice.inodo.children[2],
newHead);
}
n->choice.inodo.kidsNo = 2;
res.old.size = 2;
res.old.max =
n->choice.inodo.children[1].child->choice.val;
res.old.child = n;
}
} // end if ha 2 o 3 figli
37
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
} else {
// i suoi figli non sono foglie
if (e <= n->choice.inodo.children[0].max) {
// si inserisce nel primo figlio
res = nodeInsert(n->choice.inodo.children[0].child,
e);
if (res.newEl == NONE) {
n->choice.inodo.children[0] = res.old;
setNONEResult(n, &(res.old));
// }
// continua alla pagina seguente
38
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
} else {
// continua i suoi figli non sono foglie
// continua si inserisce nel primo figlio
} else if(res.newEl == TOLEFT) {
if (n->choice.inodo.kidsNo == 2) {
n->choice.inodo.children[2] =
n->choice.inodo.children[1];
n->choice.inodo.children[1] = res.old;
n->choice.inodo.children[0] = res.new;
setNONEResult(n, &(res.old));
} else {
// kidsNo == 3 cioe’ split
// continua alla pagina seguente
39
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i suoi figli non sono foglie
// continua si inserisce nel primo figlio
// kidsNo == 3 cioe’ split
n->choice.inodo.children[0] =
n->choice.inodo.children[1];
n->choice.inodo.children[1] =
n->choice.inodo.children[2];
n->choice.inodo.kidsNo = 2;
res.newEl = TOLEFT;
res.new = getNodeAndMakeHeader(res.new,
res.old);
setHeader2(n, &(res.old));
}
} else {
// continua alla pagina seguente
40
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i suoi figli non sono foglie
// continua si inserisce nel primo figlio
// res.newEl == TORIGHT
if (n->choice.inodo.kidsNo == 2) {
n->choice.inodo.children[2] =
n->choice.inodo.children[1];
n->choice.inodo.children[0] = res.old;
n->choice.inodo.children[1] = res.new;
setNONEResult(n, &(res.old));
} else {
// continua alla pagina seguente
// kidsNo == 3 cioe’ split
41
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i suoi figli non sono foglie
// continua si inserisce nel primo figlio
// continua res.newEl == TORIGHT
// kidsNo == 3 cioe’ split
n->choice.inodo.children[0] =
n->choice.inodo.children[1];
n->choice.inodo.children[1] =
n->choice.inodo.children[2];
n->choice.inodo.kidsNo = 2;
res.newEl = TOLEFT;
res.new = getNodeAndMakeHeader(res.old,
res.new);
setHeader2(n, &(res.old));
}
} // end if res
42
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
} else if (e <= n->choice.inodo.children[1].max
|| n->choice.inodo.kidsNo <= 2) {
// i suoi figli non sono foglie
// si inserisce nel secondo figlio
res = nodeInsert(n->choice.inodo.children[1].child,
e);
if (res.newEl == NONE) {
n->choice.inodo.children[1] = res.old;
setNONEResult(n, &(res.old));
} else if(res.newEl == TOLEFT) {
if (n->choice.inodo.kidsNo == 2) {
n->choice.inodo.kidsNo = 3;
n->choice.inodo.children[2] = res.old;
n->choice.inodo.children[1] = res.new;
setNONEResult(n, &(res.old));
} else {
// continua alla pagina seguente
43
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i suoi figli non sono foglie
// continua si inserisce nel secondo figlio
// kidsNo == 3 cioe’ split
res.new = getNodeAndMakeHeader
(n->choice.inodo.children[0],
res.new);
n->choice.inodo.children[0] = res.old;
n->choice.inodo.children[1] =
n->choice.inodo.children[2];
n->choice.inodo.kidsNo = 2;
res.newEl = TOLEFT;
setHeader2(n, &(res.old));
}
} else {
// continua alla pagina seguente
44
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
// continua i suoi figli non sono foglie
// continua si inserisce nel secondo figlio
// res.newEl == TORIGHT
if (n->choice.inodo.kidsNo == 2) {
n->choice.inodo.kidsNo = 3;
n->choice.inodo.children[2] = res.new;
n->choice.inodo.children[1] = res.old;
setNONEResult(n, &(res.old));
} else { // kidsNo == 3 cioe’ split
res.newEl = TORIGHT;
n->choice.inodo.children[0] =
n->choice.inodo.children[1];
n->choice.inodo.children[1] = res.old;
n->choice.inodo.kidsNo = 2;
setHeader2(n, &(res.old));
res.new = getNodeAndMakeHeader
(res.new,
n->choice.inodo.children[2]);
45
} // end if res
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
} else {
// i suoi figli non sono foglie
// si inserisce nel terzo figlio
res = nodeInsert(n->choice.inodo.children[2].child,
e);
if (res.newEl == NONE) {
n->choice.inodo.children[2] = res.old;
setNONEResult(n, &(res.old));
} else {
// kidsNo == 3 cioe’ split
// continua alla pagina seguente
46
Inserzione di un elemento (key-based)
// continua struct result nodeInsert()
} else {
// i suoi figli non sono foglie
// si inserisce nel terzo figlio
// kidsNo == 3 cioe’ split
res.newEl = TORIGHT;
if (res.newEl == TOLEFT) {
res.new = getNodeAndMakeHeader(res.new,
res.old);
} else { // res.newEl == TORIGHT
res.new = getNodeAndMakeHeader(res.old,
res.new);
}
n->choice.inodo.kidsNo = 2;
setHeader2(n, &(res.old));
}
} // end in quale figlio si inserisce
}
return (res);
}
47
Esempio 5: rimozione di un elemento
1
• Supponiamo di volere rimuovere l'elemento di indice 5 (e5).
n0 - 12
n1 - 7
n3 - 2
n4 - 2
e1
e3
e2
n2 - 5
n5 - 3
e4
e5
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
48
Rimozione di un elemento
5.1
• Poiche' il nodo n5 aveva 3 figli esso rimane ancora con 2 figli, il
che e' legittimo.
• Ovviamente occorre aggiornare le informazioni strutturali
contenute in
• n5, che ora contiene 2 foglie,
• n1, che ora contiene 6 foglie, ed
• n0, che ora contiene 11 foglie.
• Notare che si sono dovute aggiornare le informazioni strutturali
solo nei nodi che appartengono al path tra la foglia rimossa e la
radice.
• Per cui la complessita' dell'operazione e' O(log(n))
49
Rimozione di un elemento
5.3
• Rimozione dell'elemento di indice 5 (e5).
n0 - 11
n1 - 6
n3 - 2
n4 - 2
e1
e3
e2
n2 - 5
n5 - 2
e4
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
50
Esempio 6: rimozione di un elemento
1
• Supponiamo di volere rimuovere l'elemento di indice 3 (e3).
n0 - 12
n1 - 7
n3 - 2
n4 - 2
e1
e3
e2
n2 - 5
n5 - 3
e4
e5
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
51
Rimozione di un elemento
6.2
• Poiche' il nodo n4 aveva solo 2 figli esso rimarrebbe ancora con solo
un figlio, il che e' illegittimo.
• Ma n4 ha almeno un fratello, e in particolare un fratello ad esso
adiacente (n3 non e' adiacente a n5)
• se uno dei fratelli adiacenti di n4 ha 3 figli, puo' cedere a n4 il figlio
adiacente
• nel nostro caso questo capita con n5, che puo' cedere a n4 il figlio
e5
• in questo modo n4 torna ad evere 2 figli, e quindi una
configurazione legittima.
• Ovviamente occorre aggiornare anche le informazioni strutturali
contenute in
• n1, che ora contiene 6 foglie, ed
• n0, che ora contiene 11 foglie.
• Notare che si sono dovute aggiornare le informazioni strutturali solo
nei nodi che appartengono al path tra la foglia rimossa e la radice.
• Per cui la complessita' dell'operazione e' O(log(n))
52
Rimozione di un elemento
6.3
• Rimozione dell'elemento di indice 3 (e3).
n0 - 11
n1 - 6
n3 - 2
e1
e2
n2 - 5
n4 - 2
n5 - 2
e4
e5
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
53
Esempio 7: rimozione di un elemento
1
• Supponiamo di volere rimuovere l'elemento di indice 2 (e2).
n0 - 12
n1 - 7
n3 - 2
n4 - 2
e1
e3
e2
n2 - 5
n5 - 3
e4
e5
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
54
Rimozione di un elemento
7.2
• Poiche' il nodo n3 aveva solo 2 figli esso rimarrebbe ancora con
solo un figlio, il che e' illegittimo.
• n3 ha si’ un fratello adiacente (n4), ma questo non ha un terzo figlio
da cedergli
• Avendo solo 2 figli, n4 puo' pero' assorbire l'unico figlio rimasto a
n3: questo porta alla scomparsa di n3.
• Poiche' il padre di n3 (n1) rimane comunque con 2 figli la
scomparsa di n3 non richiede altre ristrutturazioni nell'albero
• Ovviamente occorre aggiornare anche le informazioni strutturali
contenute in
• n1, che ora contiene 6 foglie, ed
• n0, che ora contiene 11 foglie.
• Notare che si sono dovute aggiornare le informazioni strutturali
solo nei nodi che appartengono al path tra la foglia rimossa e la
radice.
• Per cui la complessita' dell'operazione e' O(log(n))
55
Rimozione di un elemento
7.3
• Rimozione dell'elemento di indice 2 (e2).
n0 - 11
n1 - 6
n2 - 5
n4 - 3
e1
e3
n5 - 3
e4
e5
e6
n6 - 2
e7
e8
n7 - 3
e9
e10
e11
e12
56
Rimozione di un elemento
• Quando la rimozione di un nodo figlio non e' assorbibile con
trasferimento di figli dai nodi adiacenti, questo porta alla
scomparso del nodo padre.
• Ricorsivamente, la rimozione di un nodo puo' propagarsi lungo
l'albero fino alla radice
• Nel caso la radice si trovi ad avere un solo figlio essa deve
essere rimossa:
• il suo unico figlio diventa la radice dell'albero
• l'altezza dell'albero diminuisce di 1
57
BTree
• I 2-3 Btree rappresentano un caso particolare di k–(2k-1) BTree
• Il caso in cui k=2
• La possibilita' di scegliere un k opportuno e' fondamentale
quando la struttura di indiciamento deve essere realizzata su
disco
• in questo caso non occorre minimizzare solo le operazioni
ma anche gli accessi al disco
• Per rendere l'accesso piu' efficiente si possono anche distribuire
le informazioni finali sui nodi intermedi e non solo sulle foglie
• nota che, nel nostro caso, il valore di header.max in un
nodo non terminale di altezza 1 coincide con il valore
contenuto nella foglia associata
58