テックリードがJavaでAVL木を実装してみた

テックリードとして第一線で活躍している神田さんがJavaを用いてAVL木を実装したのでその内容を公開いたします！

AVL木とは二分探索木の一種で、自動的に木のバランスを保つことで要素の探索計算量を
常にO(logn)に維持し効率的に探索を行えるようにした木です。

O(logn)とは、データがn件ある構造に対して最低でもlogn回の計算量で結果が得られるということで、
例えばnが10,000,000の場合、lognはおよそ23.3(つまり2の23.3乗が約10,000,000になる)なので
必ず24回の比較以内には探索の結果が得られることになります。

例えばバランスを保たない木の場合、1,2,3,...と挿入した場合は根からひたすら
右にノードが伸びていった実質は線形リストの構造になってしまい、最悪の場合はO(n)の探索計算量になってしまいます。

しかし自動的にバランスを取ることによってO(logn)の探索計算量で探索が可能になります。

また、探索する要素が必ず含まれているとは限らない場合もあるため、もし含まれていない要素を
線形リストで探索する場合、必ず最低値のn回の計算量がかかってしまいます。

以下のサンプルではAVL木とArrayListにそれぞれ10,000,000の数字を1から順に挿入していき、そこから値が存在するかを確認するまでの時間(ns)を計測してみました。(時間の計測方法は力尽きたので適当です)

JavaでAVL木構造を実装したコード

AVL木への挿入はバランスを取る処理が必要なためArrayListに比べるとかなりの時間を要しますが、探索では圧倒的な処理速度を記録しています。
そしてArrayListの方は線形リストなので値が小さいほど探索に要する時間が少ないことも確認できます。

実行結果

(そもそもListは探索のためのものじゃないだろという指摘は今回はスルーで…)