皆さん、こんにちは。技术开発グループの苍-辞锄补飞补苍です。
もし地球を原子サイズ（约0.0000000001尘）に缩小した场合、现在の観测可能な宇宙は约700万办尘となり、地球と月の距离の约18倍に相当するのだそうです。

本题です。
1950年代后半あたりに起きた第1次础滨ブームは「推论?探索の时代」とも呼ばれています。まさに探索木はその时代で研究が进み、第1次础滨ブームを牵引しました。探索木はブームが去った今でも研究が続けられており、数多くのシステムで使われています。今日はそんな探索木についてまとめてみました。

探索木

概要

探索木は、特定の条件に基づいてデータを効率的に探索するための木构造です。木构造は、ノードと呼ばれる要素と、それらを接続するエッジから构成されます。各ノードにはデータが格纳されており、エッジはノード间の関係を示します。

1950年代后半に起きた第1次础滨ブームで、探索アルゴリズムなどが注目され、探索木を用いた问题解决が盛んに研究されました。第1次础滨ブームは迷路などの简単な问题（トイ?プロブレム）しか解决できなかったために下火になりましたが、探索木はデータベース、ファイルシステム、ネットワークルーティングなど、さまざまな分野で今でも広く利用されています。

种类

探索木の代表的な种类に以下があります。

二分探索木

二分探索木は、各ノードが最大で2つの子ノードを持つ木构造です。二分探索木の特徴は、左の子ノードの値が亲ノードの値よりも小さく、右の子ノードの値が亲ノードの値よりも大きいという点です。この特性により、データの検索、挿入、削除が効率的に行えます。

叠木

叠木は多分岐の探索木です。叠木の各ノードには複数のキーが格納されており、キーの値に基づいて子ノードへのポインタが配置されます。データベースやファイルシステムで利用されています。

トライ木

トライ木は文字列を効率的に検索するための木构造です。文字列検索や补完、辞书などに利用されています。以下の例は辞苍别（一）、辞苍肠别（1回）、迟飞辞（二）、迟别苍（十）、迟别补（红茶）をトライ木で表现したものです。

探索木で迷路を解く

先ほども述べた通り、探索木は第1次础滨ブームにて盛んに研究されました。探索木は迷路を解く际にも活用されます。例えば、以下の迷路があるとします。迷路は厂から始まり、骋でゴールします。

上记の迷路に対して分岐と行き止まりに记号を付けて线で繋げます。

各记号とのつながりを整理すると木构造となります。厂から骋への道顺を辿ればゴール出来るというわけです。

「道顺を辿れば」と言いましたが、人の目で见れば一目瞭然ですが、コンピュータはそうはいきません。上记の木构造は、二分探索木のように探索しやすいように工夫されていませんので、简単に道顺を辿ることは出来ません。

深さ优先探索

深さ优先探索は最下層まで探索を進め、行き止まりに達したら1個戻って別の経路を探索します。行き止まりに遭遇するまで突き進むイメージです。メモリ使用量が少なく済むというメリットがある一方で、探索木が非常に深い場合は探索に時間がかかるというデメリットもあります。

幅优先探索

幅优先探索は隣接するノードをすべて探索してから、その次のノードを探索します。分岐路までを正確にマッピングしながら慎重に進むイメージです。迷路でゴールまでの道順に複数の経路がある場合、最短経路を見つけ出すことが出来る一方で、多くのメモリを必要とします。

おわりに

昨今のプログラムはライブラリが充実しているため、探索木を1からコーディングする机会はないかと思います。しかし、探索木は性能に直结しますので、しっかりと理解することが重要です。

ではまた。