Skew Binary List
Operations
要素の列$ (a_0, a_1, \dots, a_{n-1})を扱う.
$ \mathtt{new}()
空の list を作成する
時間計算量$ \Theta(1)
$ \mathtt{is\_empty}()
list が空であるか判定する
時間計算量 $ \Theta(1)
$ \mathtt{cons}(x)
先頭に$ xを追加する
時間計算量$ \Theta(1)
$ \mathtt{head}()
$ a_0を取得する
時間計算量 $ \Theta(1)
$ \mathtt{tail}()
$ a_0を削除する
時間計算量$ \Theta(1)
$ \mathtt{lookup}(i)
$ a_iを取得する
時間計算量 $ \Theta(\log i)
$ \mathtt{update}(i,x)
$ a_iを$ xに変更する
時間計算量$ \Theta(\log i)
Summary
ねじれ二進数を用いた、list とarray の性質を併せ持つデータ構造
ねじれ二進数の$ k桁目は$ 2^k-1を表しており、各桁は$ 0,1,2のいずれかの値を取ることが出来る
ただし、ある桁が$ 2であるならそれより小さい桁は全て$ 0であるという条件を加える
この制限の元、全ての非負整数はねじれ二進数を用いて一意に表現することが可能である
ねじれ二進数に$ 1を足し引きすると、通常の二進数とは異なり定数個の桁しか変化しない
この性質によって、効率的な$ \mathtt{cons}, \mathtt{tail}を実現している
ねじれ二進数の各桁は$ 2^k-1の形であり、これを完全二分木に対応さたものの list を保持する
単純には可変長配列に劣るが構造が扱いやすく、path copying で永続化できるなどの特長を持つ
https://gyazo.com/d09b43ecd63d0dc4f2a53a48a15f3e5f
$ n=12に対して$ \mathtt{cons}を行った状態
$ 112から$ 120への繰上りに対応している
先頭への挿入により、元からあった要素の添え字は$ 1大きくなる
References
Notes
セグ木等と同様、モノイドを乗せることが出来る
永続化した際、以下の操作が実現できる
$ \mathtt{drop}(i)
先頭$ i要素を削除した list を作成する
時間計算量$ \Omicron(\log n)空間計算量$ \Omicron(\log n)
$ \mathtt{extend}(i,x)
先頭に$ i個$ xを追加した list を作成する
時間計算量$ \Omicron(\log (n+i))空間計算量$ \Omicron(\log (n+i))
片側柔軟配列とも呼ぶ
Implementations