ToDo:
なんかこれよくわからんのは、 なんで一回でルートまで持っていっちゃうのかなーということ。 参照されるたびに splay を 1 step だけやるとかの方が 直感的に(本当に完全に直感だけど)平均的に速そうなイメージがあるのだけど。
ちゃんと調べたらどっかに書いてあるんだろうけど
(01:11)
http://yhara2.blogspot.com/2009/10/pro.html
golfer.pro とか取って Java で import pro.golfer.saru とかやりたいなーとか思ったけど 取られていた
(01:12)
| 前 | 2009年 12月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
償却時間計算量（最悪な操作列が来た時の平均計算量）を O(log(n)) にしたかったからじゃないかと思ってました。例えばsplayを1stepだけだと、木のバランスが一番とれてない状態で一番深いところにあった要素にn回連続アクセスされるとO(n^2 / n)=O(n)の償却計算量になってしまう。
途中適当なところでsplayを止めるのはsemi-splay treeとかいう名前でいくつかのバリエーションがあるみたいですが、僕もよくわかりません。
あーなるほど。えーとでもすぷれー木をバランスが一番とれてない状態にするのって大変そうな気がするんですが、えーとそうなることもあるんですかね…
Wikipediaとかにありますが、小さい方から順番に１個１個アクセスしていくと一番崩れた状態になります。わりとよくある状況ではないかなーと
あーなるほど。 root まで持ってく splay を前提に小さい方から順番にアクセスしていくと悲惨な状態になるのはわかるのですが、例えば splay を 1step だけやる実装が前提ならそこまで悲惨な状態にならないような。 splay を 1step だけやる実装が前提なら、 0,1,2,3,4,... と入ってる tree に、 0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,... とアクセスしていくと崩壊する感じですかね。