Perché alcuni alberi di ricerca posizionano gli elementi degli insiemi che rappresentano solo nelle foglie, mentre alcuni in tutti i nodi?

Question

Perché alcuni alberi di ricerca posizionano gli elementi degli insiemi che rappresentano solo nelle foglie, mentre alcuni in tutti i nodi?

#1 da (1 voti)

0

Un albero di ricerca è una struttura dati che rappresenta un insieme di elementi.

Un albero 2-3 e a B-tree sono alberi di ricerca. Gli elementi degli insiemi che rappresentano sono posizionati solo nelle foglie degli alberi di ricerca.

Un albero di ricerca binario è anche un albero di ricerca. Ma gli elementi dell'insieme che rappresenta un albero di ricerca binario sono collocati in tutti i nodi, inclusi i nodi interni.

Perché c'è la differenza?
Quali tipi di alberi di ricerca posizionano gli elementi degli insiemi che rappresentano solo nelle foglie?
Quali tipi di alberi di ricerca posizionano gli elementi dei set che rappresentano in tutti i nodi?

Grazie.

data-structures

posta Tim 11.10.2016 - 06:48

fonte

1 risposta

Leggi altre domande sui tag data-structures

Esiste un nome per questo tipo di funzione? Perché un max-heap non ha un'operazione di tasto di diminuzione e un heap minimo un'operazione di aumento della chiave?

score 1 · Answer 1

Contrariamente a quanto hai detto, nei tre esempi che hai fornito, i nodi interni contengono anche valori.

In un albero B + , ad esempio, tutti i valori si trovano nelle foglie, i nodi interni contengono solo le chiavi .

Questo è interessante solo quando i dati sono separati in una chiave e qualche altro valore (come in un database). Ciò consente a più chiavi di andare nei nodi interni, limitando la profondità dell'albero. Quando i nodi sono su un supporto lento, ciò limita il tempo necessario per andare ai dati.