noshi91 https://blog.hatena.ne.jp/noshi91/ noshi91のメモ https://noshi91.hatenablog.com/ データ構造 はじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平衡二分探索木です。 本記事では三分探索木を Splay Tree を用いて実装します。 以下、与えられるキーの文字の種類を σ、文字列長を M、要素数を N とし、各文字は定数時間で大小比較が可能とします。 三分探索木とは Trie において、次の文字を二分探索木で管理したものです。 これにより各ノードは二分探索木の左子/右子と Tr… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnoshi91.hatenablog.com%2Fentry%2F2018%2F10%2F01%2F182903" title="Splay Tree で三分探索木を組む - noshi91のメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-10-01 18:29:03 rich https://noshi91.hatenablog.com/entry/2018/10/01/182903 1.0 100%