AVL木で木構造を学ぼう （2/2）－ ＠IT

さて、AVL木に新しくデータが追加された場合、それがどの節点とも一致しなければ節点を追加することになります。そして、新しく節点が追加されたことで先に挙げたAVL木のバランス条件が崩れた場合には、平衡を取り戻す処理を実施しなくてはなりません。 AVL木では節点の追加位置によって以下の4つのパターンが存在することが分かっています。 R（右回転） L（左回転） LR（左－右回転） RL（右－左回転） 右回転を例に見ていきましょう。まず、初期状態は下図のようになっているものと考えます。先に挙げた「通りがけ順」でたどっていくと、「10、20、30、40、50」とソートされた順でたどれることがわかりますね。 この状態のツリーに「9」の要素を追加してみます。自分より小さい値は左側なので、ROOTからたどっていって、「10」の葉の左側に追加することになります。ところが、この状態になると木の高さのバランスが