このデータ構造の名前を知りませんか?

Question

時系列のような追記型かつ不変なデータの保存と検索方法を考えていて、素人考えで下図のような非平衡木を作れば直近のデータは最速 O(1) だし古いデータも最悪 O(1+log N) で到達できるかなと思いました。

見るからにナイーブな方法なので既に研究されていていると思うのですが、検索するための名前が分かりません。どなたかご存じの方がいたら教えていただけないでしょうか。

Comments

[Zuishin]

木の名前を聞いているんですか？
データを蓄えるだけならリストじゃだめなんですか？

[ikadzuchi]

その丸には具体的にどのようなデータが入っているのですか? 例えば何かのイベントの起こった時刻と内容のようなものでしょうか。
また、具体的にどのように検索するつもりなのか分かりません。何を入力して何を求めるのですか?

[ppaul]

なぜ、 O(1+log N)で検索できるのでしょう。
検索条件は追加した時間だけなのですか？

Answer 1

直近のデータについてO(1)というのが少々あいまいですが、 基数木(パトリシア)かそれに指(finger)を追加したものじゃないでしょうか。