|
|
Un B-albero binario è un albero binario T di ricerca tale che ciascun nodo di un albero 2-3 D, detto supernodo, è rappresentato con uno o due nodi binari di T. Una connessione padre figlio tra due nodi binari è detta orizzontale se è interna allo stesso supernodo, mentre è detta verticale se è tra due supernodi. Soltanto una connessione tra il padre e il suo figlio destro può essere orizzontale. Vediamo come vengono trasformati due supernodi, composti da due elementi, con rispettivamente due e tre figli:
Vediamo quindi come si trasforma un albero binario 2-3 in un b-albero binario:
Ad ogni nodo u del B-albero binario è associato un intero, che è il livello del supernodo dell’albero 2-3 che rappresenta. E’ però più conveniente numerare i livelli dalle foglie alla radice. Poiché un supernodo con tre figli è rappresentato con due nodi binari aventi una connessione destra orizzontale , tali nodi binari anno lo stesso livello.
Qualsiasi percorso radice foglia nel B-albero binario è lungo O(log n).
Ci sono due operatori ausiliari tipici dei b-alberi : inclina e fraziona.
Se un nodo binario u, ha una connessione orizzontale sinistra, “inclina” modifica l’albero
effettuando una rotazione destra, come descritto in figura:
Se in un nodo binario u, anche il figlio di u ha una connessione destra, l’operatore fraziona modifica l’albero con una rotazione sinistra.
Utilizzando gli operatori inclina e fraziona, è possibile descrivere semplicemente gli operatori inserisci e cancella. Per l ‘ operatore “inserisci” si aggiungi il nuovo nodo col nuovo elemento a livello 1 e si risali il percorso dal nuovo nodo verso la radice e per ogni nodo binario u incontrato si esegue inclina(u) seguita da fraziona(u).
Per quanto riguarda l’ operatore “cancella”, viene tolto dal livello 1 il nodo con l’elemento da cancellare. Poi si risali il percorso dal nodo rimosso verso la radice e per ogni nodo binario u; se manca supernodo sotto u, decrementa di 1 il livello di u, altrimenti se il figlio destro d di u appartiene allo stesso supernodo, decrementa anche livello di d. Infine si esegue inclina(u) seguita da fraziona(u).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.