本記事を読むにあたって
本記事では、木構造の基本概念や二分探索木には触れない。木構造については、下記の記事で触れられている。
平衡木
平衡木は以下のような構造が挙げられる。
- 最悪のツリーの場合、探索にO(n) かかる(n:節点数)。現実では、整列した要素を順位挿入するケースは多い。
- バランスドツリーでは探索効率が最も良い。しかし、形の再構成に時間がかかる。
- 平衡木はバランスドツリーに近い形が適度な手間で維持できる探索木で、節点の挿入/削除・探索どれもO(logN) で済む。この探索木の代表例としてAVL木とB木が挙げられる。
AVL木
AVL木とはすべての節点において 左部分木と右部分木の高さの差が1に収まった二分探索木である。
節点の挿入
例えば、例えば9 の右に10が挿入されたとき、節点8から見た右部分木は2(9,10)だが、左部分木は0(何もない)そのため、差が2になる。AVL木の条件を満たさないため、再構成する必要がある。とある節点から見た時の差が2以上の時、要素が多い方(例では,右)とは逆方向に回転させる。回転させる際に注目した節点の一つ下(今回でいうと9)を中心に回転させる。結果8→9 となり、9の左部分木には節点8。右部分木には節点10という構成になる。7からみた高さの差も1,3から見た高さの差も1以下であるので操作は終了される。
節点が挿入された場合は必ず各節点の高さの差を比較し、高い方の部分木とは逆に回転させ、その際、注目した節点の1つ下の節点(高さが大きい方の部分木の節点)が注目節点と置き換わる。基本はこの操作で完結するが二重回転が必要となるケースが存在する。
二重回転
節点3や節点7のような、節点の分岐後に節点の分岐が存在するような点から見た時の高さの差が2以上の時二重回転が必要となる。例えば、節点4の左下に節点3が挿入されたとき節点3からみて右部分木の高さは4(7→5→4→3)、左部分木の高さは2(1→0or2)となり高さの差は2となる。回転は通常と同様に逆に回転させるが、回転させる際置き換える節点が変化する。結論から述べると、
- 右部分木の方が高い場合は、注目点の右部分木の一番上の節点(今回は7)の左の節点(今回は5)に置き換えられる。
- 左部分木の方が高い場合は、注目点の左部分の木の一番上の節点(今回は1)の右の節点(今回は2)に置き換えられる。
つまり今回は、3→5になり左部分木は(5→3→1→0or2, 5→3→4)となり、右部分木は(5→7→8→9, 5→7→6)となる。節点4は節点5より小さいため左部分木に、節点6は節点5より大きいため右部分木に操作されている。
節点の削除
節点の挿入と同様の操作となる。節点が削除された親の節点から各節点の高さを比較し高さ2以上であれば、回転させる。その際、部分木の高さが高い方とは逆方向に回転させる。二重回転も同様な操作となる。
おわりに
大学の講義でアルゴリズム・データ構造を学習しその際AVL木の内容があまり触れられなかったため、自分で学習し、自分なりの理解を記事として残しました。最初は回転の仕組みの理解に時間がかかりますが数をこなせば何とかなります。