OCamlのsetの実装の軽い紹介

Competitive Programming Advent Calendar 2016 - Adventar 1日目の記事です。

OCamlのsetがsplit/merge可能なAVL木になっているので、それの簡単な紹介です。 ちなみに、上の一文でこの記事の9割は終わったも同然です。

いくつかコアの関数を軽く紹介。計算量でh(t)って書いてあるのは、AVL木 t の高さのこと

balance

  • |h(n.l) - h(n.r)| = 3 のときに、木を回転させて |h(n.l) - h(n.r)| < 3 にする。
  • 計算量は O(1)
  • OCamlの実装だと、balという名前がついている
  • OCamlのset実装のAVLは、|Balance factor| <= 2 が不変条件になっているので注意。 gist.github.com

join(Node l, Node v, Node r)

  • l, v, r の並びでマージする関数
  • h(l), h(r) は任意で、h(v) = 1
  • 計算量は O(|h(l) - h(r)|)

gist.github.com

merge(Node l, Node r)

  • 2つのAVL木 l, r をマージする関数
  • 計算量は O(max(h(l), h(r)))
  • OCamlの実装だと、concatという名前がついている

gist.github.com

split(Node t, int k)

  • AVL木 t を [0,k), [k,size(n)) で分割する関数
  • 計算量は O(h(t))
    • (splitで再帰しながらjoinを呼んでおり一見 O(h(t)) に見えないが、joinしていく木の高さが徐々に高くなっていき、O(h1 + (h2 - h1) + (h3 - h2) + ...) = O(h(t)) となるのが面白い)

gist.github.com

性能

コピー&ペーストで、AVLとRBSTの性能を計測してみました。

問題
copypaste: コピー&ペースト - 2012年 日本情報オリンピック春合宿OJ | AtCoder
JOI 2011-2012 春季トレーニング合宿 問題

AVLによる解答 Submission #1000130 - 2012年 日本情報オリンピック春合宿OJ | AtCoder
RBSTによる解答 Submission #1000163 - 2012年 日本情報オリンピック春合宿OJ | AtCoder

AVLのほうがRBSTより速い(やけに実行速度が速いけど、昔よりジャッジが早くなってたりする?)

反省

  • 本当は図を入れたりして、どんな操作か丁寧に説明したかったのですが、間に合わず😞

明日の担当は tubo28 さんと snuke さんです。

参考(といいつつ自分はあんまり見てない)