Questa è una specie di domanda a più parti.
È possibile fare un albero di ricerca binario se i dati non possiedono un ordinamento naturale? Sareste costretti a imporre ordini artificiali a tali dati? Come le immagini? O file eseguibili? O video? o file audio? Oggetti che non possiedono un ovvio ordine alfabetico o numerico (la mia idea di ordinamento totale "naturale").
O sarebbe meglio usare una hashmap a quel punto?
Sono disponibili dati ordinabili (che possono essere non ordinati), ma possono essere ordinati in base a una varietà di algoritmi di ordinamento. Tutti questi algoritmi di ordinamento dipendono dalla capacità di eseguire un test di ordinamento di confronto di base tra elementi dati arbitrari. Tale confronto deve restituire l'ordinamento relativo di due elementi, ad esempio, di solito -1 per meno, 0 per uguale e 1 per maggiore. Esiste una sola risposta possibile per il risultato ordinato nel suo insieme (salvo i duplicati).
Ci sono anche dati correlati come avresti in un grafico, possibilmente un grafico diretto, ma non necessariamente così. Dato un grafico, sappiamo qualcosa sulle posizioni relative dei nodi attraverso i loro bordi di collegamento. Tuttavia, non esiste un ordinamento totale di tutti i nodi, solo che alcuni nodi sono noti per essere prima o dopo altri nodi. Possiamo eseguire un ordinamento topologico per ordinare i nodi, ma la linea di fondo è che ci sono molte risposte corrette, quindi solitamente un ordinamento topografico ne sceglierà solo uno. Un grafico ciclico può avere cicli, quindi di nuovo l'ordine è (anche più) arbitrario. Spesso guardiamo ad altre proprietà, ad esempio, per scegliere l'elemento principale di un ciclo per determinare un buon ordinamento per il dominio.
Poi ci sono dati non correlati, in cui tutto ciò che possiamo fare è confrontare per l'uguaglianza. Per quelli, l'hashing è una struttura dati ragionevole per la memorizzazione e il recupero. Non esiste alcuna nozione di ordinamento.
Dovremmo anche considerare che lo stesso elenco di entità può essere ordinato per proprietà o qualità differenti. Ad esempio, i file possono essere ordinati in base alla loro dimensione, che fornirà un ordinamento totale. Potrebbero essere ordinati in base ai loro timestamp. Questi possono essere inutili per il tuo dominio, ma il punto è comunque pensare alle varie proprietà disponibili per l'ordinamento, la categorizzazione, ecc ...
Is it possible to do a binary search tree if the data does not possess natural ordering?
Non so cosa significhi la parola "naturale" nel tuo contesto; sembra vago.
Inoltre, immagini, video, file eseguibili e file audio mi sembrano perfettamente ordinabili. Ordinarli per confronto ordinale a byte, in caso di parità, il file più corto è più piccolo. Perché pensi che questo non sia un modo naturale per mettere qualcosa in ordine? Ecco come si mettono le stringhe in ordine, quindi perché non i file audio? Un file audio è solo una stringa di byte, quindi ordinalo come una stringa di byte.
Permettimi di rispondere a una domanda che so come rispondere invece:
Is it possible to do a binary search tree if the data does not possess a total ordering?
No. Gli alberi di ricerca binaria richiedono un ordinamento totale.
What is a total order?
Un ordine totale significa semplicemente che devi fornire a un operatore di confronto che può determinare l'uguaglianza, maggiore o minore rispetto a ogni coppia di elementi. Inoltre, tutte le regole che ritieni siano ovviamente valide per l'ordine devono essere soddisfatte, ad esempio:
e così via. Se non riesci a rispettare queste regole, non puoi fare una ricerca binaria e ottenere sempre risultati corretti. Se riesci a rispettare queste regole, puoi farlo
Or would it just be better to use a hashmap at that point?
Meglio per quale criterio? Non hai detto quali operazioni intendi eseguire su questa struttura dati diversa dalla ricerca . Le mappe hash sono molto utili in alcune attività a cui gli alberi binari sono malvagi e viceversa.
Un ordine è solo una relazione tra due elementi in un insieme. La relazione non è sempre "è maggiore di". Ad esempio, la relazione "è il figlio di" è, matematicamente parlando, un ordine. Non è l'ordine necessario per una ricerca binaria perché non è ben definito per tutti gli elementi: cosa succede se scelgo due fratelli? Questa relazione esiste solo per alcuni degli elementi di un determinato insieme.
Invece l'ordine che esiste nei numeri naturali è buono perché PER OGNI numero dell'insieme è possibile stabilire quale "è maggiore di". Tuttavia fino a quando non definisci un ordine totale ogni relazione è buona: per le immagini "è più verde di" funzionerà bene. Questo è tutto ciò che serve per una ricerca binaria, un ordine totale; Spetta alla tua creatività / necessità di trovare la giusta proposizione d'ordine. Per ulteriori informazioni .
Questo è la documentazione dell'interfaccia Comparable in java necessaria per costruire un set di alberi. È particolarmente interessante la descrizione del metodo compareTo.
Leggi altre domande sui tag algorithms binary-tree