kankinkon https://blog.hatena.ne.jp/kankinkon/ Afro-Blue https://kankinkon.hatenadiary.org/ アルゴリズムとデータ構造 挿入時に左右の回転を使用して新たな節点を根にするという動作に加え、回転がある意味で木を平衡させるように根への挿入を修正する。 新しい節点を木のトップに持ってくる単純回転を使う代わりに、節点を根の孫の位置から木のトップに移動する二つの回転を行う。最初に根の子の位置に移動する回転を行い、次に根に移動する回転を行う。 二重回転は、根から挿入される節点への二つのリンクが同じ方向か別々の方向かの二つの場合がある。 また、別々の方向の場合は、下の方の回転を最初に実行する場合と上の方の回転を最初に実行する場合がある。スプレイ挿入は上の回転が使われる。BSTへのスプレイ挿入のプログラム。次の4つの規則に従う。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkankinkon.hatenadiary.org%2Fentry%2F20120520%2F1337502541" title="平衡木（スプレイBST） - Afro-Blue" 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 2012-05-20 17:29:01 rich https://kankinkon.hatenadiary.org/entry/20120520/1337502541 1.0 100%