基礎

「第3回：ソースでわかる！ハッシング」 でハッシングとリンクトリストを組み合わせたものを紹介しました。今回はそのプログラムを紹介しますが、実はその本体はこれまでに紹介したものばかりで す。1本のリンクトリストを扱うプログラムは第1回に紹介しました。これをハッシュ値が同じもの同士をひとつのリストにするようにして、複数のリストを 作って管理するのがこの方法です。

リンクトリストでは要素を探索する場合、リンク（ポインタ）を順にたどるしかないため、線形探索と等しい時間がかかってしまいます。今回は、リストと同 様にポインタでつながった構造でありながら、探索時間は二分探索と同じ性能の構造である二分木（Binary Tree）を紹介します。これはB-Tree や Balanced Tree（バランス木）と言葉も機能も似ていますが、少し違います。今回は、探索目的に使う二分木である二分探索木（Binary Search Tree）と呼ぶものを扱います。