スキップリスト
これで、コイン投げの回数は、 O ( n log  n ) {\displaystyle {\mathcal {O}}(n\log n)} でなく O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)} に削減できる。この方法では、悪意を持ったユーザが、ある1つのノードの高さを正しく推測できる確率は非常に低いにも関わらず、「全ての偶数番目のノードは高さが1より大きいだろう」という推測が50%の確率で当たってしまう。
スキップリストは、より伝統的な平衡木と同じ最悪時のパフォーマンスを保証しない。なぜなら、(確率はとても低いが)バランスの悪い構造になる場合が常にあるからである。しかし実際にはよく動作し、ランダム化されたバランスとりの仕組みは平衡二分探索木の決定論的なバランスとりの仕組みより実装が容易であることが示されている。スキップリストは並列計算においても有用で、挿入はスキップリストのいくつかの部分で並列に実施でき、全体のリバランスが不要である。この並列化は、アドホック無線ネットワークでのリソース探索において特に有用となりうる。なぜなら、ランダム性のあるスキップリストは単一ノード損失に対して堅牢にすることができるからである。