関連リンク: これで分かったAVL木

Java による再帰を使わないAVL木の実装

 こちらのページでは、 Java による再帰を使ったAVL木の実装を解説しました。 AVL木の原理を理解するには、再帰を使った方が分かりやすいと思うからです。 しかしAVL木は、その主要部分を再帰を使わずループを使って実装できます。 ループの方がオーバーヘッドが小さいため、高速なAVL木を実現できます。 ここでは、Java による再帰を使わないAVL木の実装を示します。

 ループで実装するには、 AVL木のノードの型に親ノードへのリンクを追加する必要があります。 親ノードへさかのぼるのに、再帰をたどることができないからです。 一方で、修正の必要性を示す active フラグは必要なくなります。 再帰を木の根までさかのぼらなくとも、 修正が必要なくなった時点で処理を終了することができるからです。

 また、グラフの終端を表すために null ではなく nil という番兵オブジェクトを使っています。 こうすると、回転などの操作が簡単になりパフォーマンスが上がります。 具体的には replace メソッドを見てください。 nil.lst をAVL木の根(root)にしているところがキモです。

 それでは、コードを示しましょう。 Java による再帰を使わないAVL木の実装は以下のようになります。

 一般に、AVL木は赤黒木より遅いと言われていますが、 この実装は、赤黒木と比較しても遜色ありません。 また、Java の赤黒木の実装である TreeMap と比較しても遜色ありません。 AVL木が遅いと言っても、体感できるほどではないようです。


関連リンク: これで分かったAVL木