AVLツリー回転操作を視覚的に理解しよう

AVL木は、ツリー構造を自動で平衡を保つことで、検索、追加、削除などの操作の時間計算量をO(log n)に抑える高標準なデータ構造です。このAVLツリー、ツリーの高さを平衡状態に保つために『回転』という作業が発生します。AVLを実装する上では欠かせない『回転』ですが、やや込み入った操作が必要となります。最終的に、私は回転パターンのチャート表を作成することで解像度が高まりましたので、ここで紹介できればと思います。

このAVLツリー、ツリーの高さを平衡状態に保つために回転という作業が発生します。AVLを実装する上では欠かせない回転ですが、やや込み入った操作が必要となります。最終的に、私は回転パターンのチャート表を作成することで解像度が高まりましたので、ここで紹介できればと思います。

---

ノードの高さとバランスファクター

本記事はツリー構造についてある程度見識がある読者を想定していますが、チャート表を紹介する前に、最低限の用語解説を行っておこうと思います。

• 高さ: ノードにおいて、最上部の親ノードからリーフまでの階層数。
• バランスファクター(BF): 左子ノードの高さ - 右子ノードの高さ。ノードがない場合は高さを-1と計算。

下画の図の通り、左子ノードが重くなる場合はバランスファクターが+2を超え、この状態になると「回転」が実行されます。

例図: ノード/ 高さ/ バランスファクター

回転のパターン

AVLでは、回転はその再構造に必要な操作です。単純な「右回転」と「左回転」、両者を組み合わせた「右左回転」、「左右回転」の4パターンがあります。BFが2,もしくは-2を超えると修正が入るため、ツリーの各ノードのBFは[-1,0,1]の範囲に常に収まります。

親ノードのBF	子ノードのBF	回転タイプ	特徴
+2	+1 or 0	右回転 (RR)	左部分木が重い。簡単な単回転で修正可能。
+2	-1	左右回転 (LR)	左部分木が重く。ノードのアームが曲折している。
-2	-1 or 0	左回転 (LL)	右部分木が重い。簡単な単回転で修正可能。
-2	+1	右左回転 (RL)	右部分木が重く。ノードのアームが曲折している。

チャート表

実行するパターンは4つなのですが、実際は子ノードのがBF=0の場合、ちょっと複雑な動きになります。また二重回転も1回目の回転を施すと、シングル回転と同じ形に変化するという特性があります。
このあたりを理解する上で、ノードの移動が分かりやすくなるように色付けをしたうえで、右回転3パターン、左回転3パターンの全6パターンをチャート化してみました。

Right Rotation Patterns

Left Rotation Patterns

まとめ

理解してしまえばそれほど難しい作業ではありませんが、初めての場合は、どのノードがどこに移動するのか、言葉だけでは分かりにくいかもしれません。本チャートを使えば、ノードの移動や操作が視覚的に理解しやすくなるはずです。この図を参考にしながら、実際に回転の仕組みを確認してみてください。