きっかけ

AVL木というものを最近知ったのですが、回転の意味がよく分からなかったので、可視化したいと思いました。

作ったもの

JavaScriptで書いて、以下のGitHub Pagesに置きました。
（おそらく問題ないと思いますが、もし間違っていたら教えてください）

操作手順は、以下の通りです。

たとえば、以下のような数列をinsertしてみます。
8 4 12 2 6 10 5 7 11

二分木なので、左から小さい順に並びます。

ここで、4のノードを左回転してみます。(4ノードのLをクリックします)

4が左下に移動し、それに伴い2,5,6等も移動していることが分かります。
回転をしても、大小関係に影響を与えないことが、視覚的に分かります。

AVL木の解説を読むときに、右・右回転や、左・右回転などを場合分けしているのですが、初心者にはとても理解しづらいです。
どうしてこのようなことをしなければいけないのかというと、1回の回転では、バランスを取れないことがあるからです。
以下は、その例です。

8 4 6をinsertしてみます。
8がバランス取れていないので、右回転します。
すると、4が先頭に来て、バランスが取れていません。
しかし4を左回転しても、もとに戻るだけです。
赤いノードの回転だけでは、バランスが取れません。

このような場合、まず子ノードの4を左回転させてから、親ノードの8を右回転させるという操作をする必要があります。

場合分けをするのは、このような場合にそなえてのことだと分かります。

自分で右回転と左回転をやってみることで、イメージできるようになりました。