Comment by anfelor

Another interesting data structure related to skiplists but not mentioned here are zip trees: https://arxiv.org/abs/1806.06726

The are a tree-based version of skiplists and thus more suited to functional programming / immutable datastructures.