auの日記

プログラミング初心者の日記。(auはハンドルネームです)

AVL木について

auです。

若干風邪がよくなってきた気がします。

今日はAVL木って何だろうなーって思って調べてみました。

AVL木とは

AVL木は、木構造の二部探索木で出てくるソートアルゴリズムです。

また、平行二部探索木の一種であり、全てのノードが、左右の部分木の高さの差が1以下になるようにしなければなりません。

高さが1以上の差になった場合、木の回転をすることで、差を1以下にします。

詳しい計算などは今は載せませんが、アルゴリズムの勉強をすることで、C言語の理解が深まった気がします。