Treap persistenti

In questa tesi, viene presentata un'analisi sui Treap e sui Random Binary Search Tree, due strutture dati correlate presentate nell'89 da Seidel e Aragon, che implementano alberi binari bilanciati in modo non deterministico. Vengono evidenziati i vantaggi offerti dalle strutture, così come la possibile estensioni dell'albero per il supporto di ulteriori tipi di operazioni. Viene inoltre mostrato un procedimento per rendere la struttura confluentemente persistente e infine vengono mostrati dei benchmark relativi ai risultati ottenuti con una implementazione in C++.