Quali sono le differenze tra alberi di segmenti, alberi ad intervalli, alberi indicizzati binari e alberi di distanza?

Quali sono le differenze tra alberi segmentari, alberi intervallati, alberi indicizzati binari e alberi gamma in termini di:

  • Idea / definizione chiave
  • applicazioni
  • Prestazioni / ordine in dimensioni superiori / consumo di spazio

Per favore non dare solo definizioni.

Tutte queste strutture dati sono utilizzate per risolvere diversi problemi:

  • Intervalli degli intervalli di albero dei segmenti e ottimizzati per le query ” quali di questi intervalli contengono un dato punto “.
  • Intervalli sugli intervalli tra gli alberi , ma ottimizzati per le query ” quali di questi intervalli si sovrappongono a un dato intervallo “. Può anche essere usato per le query puntuali – simile all’albero del segmento.
  • L’albero della distanza memorizza i punti e ottimizzato per le domande ” che punti rientrano in un dato intervallo “.
  • L’albero indicizzato binario memorizza gli elementi conteggio per indice e ottimizzato per ” quanti articoli ci sono tra le query index e n “.

Prestazioni / consumo di spazio per una dimensione:

  • Albero del segmento – Tempo di preelaborazione O (n logn), tempo di interrogazione O (k + logn), spazio O (n logn)
  • Interval tree – O (n logn) tempo di preelaborazione, O (k + logn) tempo di interrogazione, O (n) spazio
  • Albero degli intervalli – Tempo di preelaborazione O (n logn), tempo di interrogazione O (k + logn), spazio O (n)
  • Albero indicizzato binario – Tempo di preelaborazione O (n logn), tempo di interrogazione O (logn), spazio O (n)

(k è il numero di risultati riportati).

Tutte le strutture dati possono essere dinamiche, nel senso che lo scenario di utilizzo include sia le modifiche dei dati che le query:

  • Albero del segmento – l’intervallo può essere aggiunto / eliminato nel tempo O (logn) (vedi qui )
  • Interval tree – intervallo può essere aggiunto / cancellato nel tempo O (logn)
  • Albero degli intervalli : nuovi punti possono essere aggiunti / cancellati nel tempo O (logn) (vedi qui )
  • Albero indicizzato binario : il numero di elementi per indice può essere aumentato nel tempo O (logn)

Dimensioni superiori (d> 1):

  • Albero del segmento – O (n (logn) ^ d) tempo di pre-elaborazione, O (k + (logn) ^ d) tempo di interrogazione, O (n (logn) ^ (d-1)) spazio
  • Interval tree – O (n logn) tempo di preelaborazione, O (k + (logn) ^ d) tempo di interrogazione, spazio O (n logn)
  • Albero degli intervalli – O (n (logn) ^ d) tempo di preelaborazione, O (k + (logn) ^ d) tempo di interrogazione, O (n (logn) ^ (d-1))) spazio
  • Albero indicizzato binario – O (n (logn) ^ d) tempo di preelaborazione, O ((logn) ^ d) tempo di interrogazione, spazio O (n (logn) ^ d)

Non che io possa aggiungere nulla alla risposta di Lior , ma sembra che potrebbe fare con un buon tavolo.

Una dimensione

k è il numero di risultati riportati

inserisci la descrizione dell'immagine qui

Dimensioni superiori

d > 1

inserisci la descrizione dell'immagine qui

Queste tabelle sono create in Markdown formattato Github – vedi Gist se vuoi il testo non elaborato.