yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ RBSTは万能かつ簡潔な平衡二分木として有名ですね Q.でもこれって計算量どうなんやろ A.なんかいい感じやねんのままだとよくないかなぁと思ってちょっと考えてみました注意点として今回の記事では全部i番目というのは0-indexedです あと、スピリチュアルです"RBST木"を以下の感じで定義します 根がi番目の可能性はそれぞれ1/(木のサイズ) 左右の子はそれぞれRBST木 例えばサイズ7のRBST木の根を考えると 0と1と2と3と4と5と6がそれぞれ透明度1/7で重ね合わさってる感じそのなかで根が4の木をとりだして、根の左の子の根を見てみると0と1と2と3が透明度1/28で重ね合わさってるQ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2015%2F03%2F30%2F011458" title="RBST(Randomize Binary Search Tree)の計算量について考えてみた - よすぽの日記" 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 2015-03-30 01:14:58 rich https://yosupo.hatenablog.com/entry/2015/03/30/011458 1.0 100%