Gli alberi K, alberi di ricerca con un vettore di valori

Ogni albero K invece di una chiave ha un vettore di chiavi

Gli alberi K, o K-dimensionali, sono una struttura dati per memorizzare i dati in uno spazio k-dimensionale. Gli alberi K sono considerati un’estensione degli alberi binari, la principale differenza con questi ultimi è che in un albero K-d ogni chiave è costituita da un vettore (k-dimensionale) invece che da un solo valore.

Le operazioni di inserimento e di ricerca di un elemento all’interno dell’albero dipendono dall’ordine di inserimento dei record. Con Gli alberi K sono molto più semplici da implementare e con le Range query si ha una significativa del numero dei nodi da visitare. La cancellazione può risultare relativamente complessa quando occorre eliminare un nodo intermedio dell’albero, per ovviare a questo problma si si possono effettuare anche delle cancellazioni logiche senza modificare la struttura dell’albero.

Gli alberi K, alberi di ricerca con un vettore di valori

Nell’esempio è possibile vedere che ogni nodo dell’albero K ha un vettore di chiavi e non obbligatoriamente un unico valore. Gli alberi k, essendo una struttura dati derivata dagli alberi di ricerca, hanno ogni valore del sottoalbero sinistro minore del minimo valore del nodo, così come ogni valore del sottoalbero destro è maggiore del più grande valore del nodo. Ad esempio, partendo dalla radice, il suo sottoalbero sinistro ha tutti valori minimo di 25, mentre il sottoalbero destro ha tutti i valori più grandi di 32 e così via per tutti i sottoalberi.

Pubblicato in Sistemi Informativi Taggato con: , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*