きっかけ
AVL木というものを最近知ったのですが、回転の意味がよく分からなかったので、可視化したいと思いました。
作ったもの
JavaScriptで書いて、以下のGitHub Pagesに置きました。
（おそらく問題ないと思いますが、もし間違っていたら教えてください）
操作手順は、以下の通りです。
- 数字を入力して、
insertボタンを押してください - バランスしていないところがあれば、ノードが赤くなります
-
Rで右回転、Lで左回転です - ノードを削除する場合は、
xを押してください
考察
たとえば、以下のような数列を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を右回転させるという操作をする必要があります。
場合分けをするのは、このような場合にそなえてのことだと分かります。
感想
自分で右回転と左回転をやってみることで、イメージできるようになりました。