Some, but not all, treaps have a node weight that is updated in a probabilistic fashion. The act of balancing the tree is still deterministic, but the weights of each node are randomized.
I keep trying to find a use for treaps, but haven't had a project that needed it. In particular, the value of a balanced tree is in consistent cost of lookups for arbitrary elements. But if you are mixing entries that are accessed often with those that are not, having an 8:1 access time ratio between the two would be a feature not a bug.
I used a persistent treap for a lock free priority queue (swap in a new root at insertion). It felt nice but to be honest, didn't do a comprehensive comparison to alternate implementation strategies.
Some, but not all, treaps have a node weight that is updated in a probabilistic fashion. The act of balancing the tree is still deterministic, but the weights of each node are randomized.
I keep trying to find a use for treaps, but haven't had a project that needed it. In particular, the value of a balanced tree is in consistent cost of lookups for arbitrary elements. But if you are mixing entries that are accessed often with those that are not, having an 8:1 access time ratio between the two would be a feature not a bug.
I used a persistent treap for a lock free priority queue (swap in a new root at insertion). It felt nice but to be honest, didn't do a comprehensive comparison to alternate implementation strategies.
edit: looks like at least one other has has the same idea https://github.com/lthibault/treap