Dati binari di ricerca binaria bilanciata solo nelle foglie

Question

Ho acquistato un bel libro sulla geometria computazionale e mentre lo leggevo qua e là mi capitava spesso di imbattermi nell'uso di questo speciale tipo di albero di ricerca binario. Questi alberi sono bilanciati e dovrebbero memorizzare i dati solo nei nodi leave, i nodi interni dovrebbero solo memorizzare valori per guidare la ricerca verso le foglie.

L'immagine mostra un albero esempio, dove le foglie sono rettangoli ei nodi interni sono cerchi.

Ho due domande a riguardo:

1. Qual è il vantaggio di non memorizzare i dati nei nodi interni?
2. Ai fini dell'apprendimento, vorrei implementare un tale albero, quindi ho pensato che fosse una buona idea usare un albero AVL come base, ma è così?

Ultimo ma non meno importante, voglio sottolineare il fatto che mi sto occupando di queste cose perché voglio imparare qualcosa, quindi ogni tipo di risorsa utile è molto gradita. Grazie in anticipo, per quanto riguarda ...

Answer 1

annuncio 1: In generale non vi è alcun vantaggio di non memorizzare i dati nei nodi interni. Ad esempio un RB-albero è pure un albero bilanciato e memorizza i propri dati nei nodi interni al posto delle foglie (vedi: http://en.wikipedia.org/wiki/Red-black_tree)

annuncio 2: IMHO è sicuramente più. (Una buona idea)

Answer 2

1. ci sono alcune strutture di dati albero che, di progettazione, richiedono che nessun dato è memorizzato nei nodi interni, come Huffman code trees e B+ trees. Nel caso degli alberi di Huffman, il requisito è che nessuna foglia abbia lo stesso prefisso (cioè il percorso per il nodo 'A' è 101 mentre il percorso per il nodo 'B' è 10). Nel caso degli alberi B + deriva dal fatto che è ottimizzato per la ricerca di blocchi (questo significa anche che ogni nodo interno ha molti figli e che l'albero di solito ha solo pochi livelli di profondità).
2. Sicuro! Un albero AVL non è estremamente complicato, quindi è un buon candidato per l'apprendimento.

Spero che questo aiuti.

Answer 3

Un vantaggio solo per mantenere i dati nei nodi foglia (ad esempio, albero B +) è che la scansione/lettura dei dati è estremamente semplice. I nodi foglia sono collegati tra loro. Quindi, per leggere l'elemento successivo quando ci si trova nella "fine" (destra o sinistra) dei dati all'interno di un dato nodo foglia, basta leggere il link/puntatore al nodo successivo (o precedente) e passare alla pagina foglia successiva .

Con un albero B in cui i dati sono in ogni nodo, è necessario attraversare l'albero per leggere i dati in ordine. Questo è certamente un processo ben definito ma è probabilmente più complesso e in genere richiede più informazioni di stato.

Answer 4

È comune avere altri tipi di alberi binari con dati sulle foglie invece dei nodi interni, ma piuttosto rari per gli alberi di ricerca binari.

Una ragione per cui si potrebbe desiderare di fare questo è educativo - è spesso più facile implementare un albero di ricerca binario in questo modo quindi nel modo tradizionale. Perché? Quasi interamente a causa di delezioni.L'eliminazione di una foglia è in genere molto semplice, mentre l'eliminazione di un nodo interno è più difficile/disordinata. Se i tuoi dati sono solo alle foglie, allora sei sempre nel caso facile!

Vale la pena pensare a dove vengono le chiavi sui nodi interni. Spesso sono duplicati di chiavi che sono anche alle foglie (con i dati). In seguito, se la chiave sulla foglia viene cancellata, la chiave nei nodi interni potrebbe rimanere bloccata.

Answer 5

Sto leggendo lo stesso libro e dicono che potrebbe essere fatto in entrambi i modi, la memorizzazione dei dati a nodi esterni o interni.

Gli alberi che usano sono rosso-nero.

In ogni caso, ecco un articolo che memorizza i dati nei nodi interni di un albero nero rosso e collega quindi questi nodi di dati insieme come un elenco.

Balanced albero binario di ricerca con una doppia lista collegata in C++ di Arjan van den Boogaard

http://archive.gamedev.net/archive/reference/programming/features/TStorage/default.html