Ecco un breve elenco.
BST
Sono inutili, servono solo nella teoria.
BBST
Sono già implementati all’interno della stl sotto il nome di std::set. Sono particolarmente utili perché supportano le funzioni insert, erase, lower_bound e upper_bound con complessità \mathcal O(\log N). Consiglio di leggere la documentazione.
Heap
Anche questi sono già implementati nella stl sotto il nome di std::priority_queue. In poche parole sono dei BBST che supportano solo inserimento ed estrazione dell’elemento minore. Si usano perché sebbene abbiano la stessa complessità sono molto più veloci nella pratica.
Treap, skip list
Fino a due anni fa si pensava che queste strutture dati fossero escluse dal syllabus delle OII, poi è arrivato specchi. Se non punti ad arrivare primo puoi ignorare queste strutture dati.
Binary lifting
L’applicazione principale è il LCA, è abbastanza semplice da imparare e fa comodo conoscerlo.
Sparse table
Struttura dati molto carina che permette di ottenere il minimo o il massimo in un intervallo in tempo costante. In alternativa si può usare un classico segment tree, anche se è meno efficiente.
Union-find disjoint sets
Davvero utili soprattutto se combinate con i treap soprattutto nei grafi. Sono una delle strutture dati che bisogna conoscere.
Min/max queue
Questo commento dovrebbe essere abbastanza esaustivo.
Trie, suffix tree, suffix array
Le strutture dati e in generale gli algoritmi sulle stringhe dovrebbero essere esclusi dal syllabus delle OII. In ogni caso è bene citare queste strutture dati.
Fully dynamic CHT, Li Chao tree
Queste strutture dati sono sicuramente utili, ma non so quanto convenga impararsele.
Link-cut tree
Questa direi proprio di no.
Y-fast trie
Questa esiste solo nella teoria.