ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ Splay 木概論 Splay 木の基本操作 $\newcommand {\rank}{\mathtt{rank}}$Splay 木 $T$ は $0 ≤ Φ(T) ≤ n \log(n)$（ただし $n$ は節点数）なるポテンシャル $Φ(T)$ のもと、次の操作ができる二分木です。 クエリ 引数 事前条件 効果 ポテンシャル増分 最悪時間計算量 $\mathtt{splay}$ 節点 $u$ なし inorder を保って $u$ が根になるように変形する $O(\log(n)) - h(u)$ $O(h(u))$ 従って次のことがわかります。 $\mathtt{splay}$ をばかりを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2024%2F04%2F22%2F205043" title="Splay 木の計算量解析 - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/n/ngtkana/20240422/20240422204843.png Hatena Blog https://hatena.blog 2024-04-22 20:50:43 rich https://blog.ngtkana.com/entry/2024/04/22/205043 1.0 100%