[ignoramous]

> Perhaps without much advantage compared to, say, a balanced BST.

A balanced BST comparatively does more work than a SkipList. Its cousin, SplayTrees, on the other hand, might give SkipList a run for its money.