Esiste un'applicazione pratica degli alberi di tango?

Question

Balanced binary search tree fornisce un tempo di ricerca garantito O(log(n)).

Tango trees raggiunge una ricerca di O(log(log(n)) compromettendo una piccola quantità di memoria per nodo. Mentre capisco che dal punto di vista teorico log(n) e log(log(n)) fa una grande differenza, per la maggior parte delle applicazioni pratiche non offre quasi alcun vantaggio.

Ad esempio, anche per un numero enorme come n = 10^20 (che è come poche migliaia di petabyte) la differenza tra log(n) = 64 e log(log(n)) = 6 è piuttosto trascurabile. Quindi c'è un uso pratico di un albero di Tango?

Answer 1

tl; dr: no, utilizzare invece un albero di diffusione.

Gli alberi di tango non forniscono O (log log n) ricerche nel caso peggiore - il caso medio è O (log n log log n). Quello che fanno è eseguito al massimo O (log log n) volte più lentamente di un albero binario con un oracle che esegue le rotazioni per ottimizzare i pattern di accesso.

Gli alberi di diffusione possono eseguire O (1) volte più lentamente rispetto al suddetto albero magico teorico: questa è la congettura dell'ottimalità dinamica. Gli alberi Splay sono molto più semplici degli alberi di tango e avranno dei fattori costanti più bassi per l'avvio. Non riesco a immaginare un'applicazione pratica in cui la garanzia dell'albero del tango sarebbe utile.