アルゴリズム

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

バブルソートからはじめて、本質的には同じことをする2つのバージョンを作りました。プログラムというものは、どうしても技巧的になりますが、一方では もっと直感的な方法をそのままプログラムにできるということを示しました。

「第2回：直感的にわかるソートの方法は？（/article/62/2/index.html）」では、バブルソートの原理に従ったプログラミング方法 を紹介しました。しかしこの方法は、理屈はわかるのですが、筆者には複雑すぎて直感的には理解しにくいものでした。それで別のアプローチを考えました。