この記事では$N$を二分探索木中の要素数(ノード数)として以後断りなく用います。
今回はAVL木をsetのような平衡二分探索木として扱いますが、配列型(平衡二分木)として使ってもほとんど同じことがいえます。
前提知識
二分探索木について
(分かってると嬉しい) : AVL木の平衡方法
正しい平衡
ノードの平衡係数は(左の子の高さ) $-$ (右の子の高さです)。
説明によっては一重回転をやるケースと二重回転をやるケースとを完全に別のものとして区別していますが、二重回転は一重回転を2回やってるだけで、かつその2回目が一重回転をやるケースの一重回転と一致するので以下のように実装することができます。
- ノード$x$の平衡係数が2の場合
- $x$の左の子の平衡係数が-1なら左の子を左回転
- $x$を右回転
- $x$の左の子の平衡係数が-1なら左の子を左回転
- ノード$x$の平衡係数が-2の場合(上の全く左右対称)
- $x$の右の子の平衡係数が1なら右の子を右回転
- $x$を左回転
- $x$の右の子の平衡係数が1なら右の子を右回転
- それ以外(平衡係数が-1,0,1の場合) 特に何もしない
サボり
故意にサボらなくても実装ミスって回転されてないとかありそう
いろんなサボり方があるけど上の実装であり得るのが手順の各1.を全くしないタイプです。
つまり平衡係数の絶対値が2だったらいい感じの方向に1回転させて終わりっていう実装です。
もちろんなんで二重回転するかを考えれば間違ってるのは明らかですが困ったことにこいつ適当なケースでは落ちません。
いろいろ実験
$N = 10^4$で実験します
- ランダムシャッフルした順列を挿入
高さ17
ランダムケースは何も平衡しないやつすら落とせないので当たり前 - 昇順挿入
高さ14
ただの二分探索木はこれで落ちますがこいつは落ちません - 最大値と最小値を交互に
i番目に(i & 1) ? i : n - iを挿入するみたいな感じです
高さ83
ちょっと兆しが見えてきました、これのオーダー分からん
一番平衡が壊れたケース
$N = 10000$の場合、i番目にi xor 0xFFF(=4095)を挿入すると最終的な高さが4108になりました。
実験ではxorする定数を$r$($r$は2べき-1)とすると、だいたい$\min(r, N - r)$くらいの高さになりそうなことが分かったので高さを$\Theta(N)$にできました。
そしてこのケースは平衡手順の、「ノード$x$の平衡係数が-2の場合」の項の手順1.をサボった場合に平衡が壊れます。
「ノード$x$の平衡係数が2の場合」の方の手順1.だけサボってるのを落としたい場合はi xor rの代わりにINF - (i xor r)にするとよいです。
最後に
ちゃんと二重回転するモチベができて良かった
超簡単に生成できるし、露骨に平衡二分探索木使う問題のテストデータに入ってるとうれしいな