{"url":"https://blog.ngtkana.com/entry/2024/04/22/205043","blog_url":"https://blog.ngtkana.com/","type":"rich","image_url":"https://cdn-ak.f.st-hatena.com/images/fotolife/n/ngtkana/20240422/20240422204843.png","author_url":"https://blog.hatena.ne.jp/ngtkana/","provider_name":"Hatena Blog","version":"1.0","description":"Splay \u6728\u6982\u8ad6 Splay \u6728\u306e\u57fa\u672c\u64cd\u4f5c $\\newcommand {\\rank}{\\mathtt{rank}}$Splay \u6728 $T$ \u306f $0 \u2264 \u03a6(T) \u2264 n \\log(n)$\uff08\u305f\u3060\u3057 $n$ \u306f\u7bc0\u70b9\u6570\uff09\u306a\u308b\u30dd\u30c6\u30f3\u30b7\u30e3\u30eb $\u03a6(T)$ \u306e\u3082\u3068\u3001\u6b21\u306e\u64cd\u4f5c\u304c\u3067\u304d\u308b\u4e8c\u5206\u6728\u3067\u3059\u3002 \u30af\u30a8\u30ea \u5f15\u6570 \u4e8b\u524d\u6761\u4ef6 \u52b9\u679c \u30dd\u30c6\u30f3\u30b7\u30e3\u30eb\u5897\u5206 \u6700\u60aa\u6642\u9593\u8a08\u7b97\u91cf $\\mathtt{splay}$ \u7bc0\u70b9 $u$ \u306a\u3057 inorder \u3092\u4fdd\u3063\u3066 $u$ \u304c\u6839\u306b\u306a\u308b\u3088\u3046\u306b\u5909\u5f62\u3059\u308b $O(\\log(n)) - h(u)$ $O(h(u))$ \u5f93\u3063\u3066\u6b21\u306e\u3053\u3068\u304c\u308f\u304b\u308a\u307e\u3059\u3002 $\\mathtt{splay}$ \u3092\u3070\u304b\u308a\u3092\u2026","provider_url":"https://hatena.blog","width":"100%","height":"190","title":"Splay \u6728\u306e\u8a08\u7b97\u91cf\u89e3\u6790","author_name":"ngtkana","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2024%2F04%2F22%2F205043\" title=\"Splay \u6728\u306e\u8a08\u7b97\u91cf\u89e3\u6790 - \u30d6\u30ed\u30b0\u540d\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","published":"2024-04-22 20:50:43","categories":[],"blog_title":"\u30d6\u30ed\u30b0\u540d"}