整理整頓を心がけましょう [GRE CS]

何だかよく分からんタイトル付けちゃったけど、GREサブジェクトテストCS分野問題第8問、お題は2分探索木(binary search tree)。

で、気付いたと思うけど、この2分探索木ってのは、この間やった2分木に、次の性質を付加したもの。

• ある点に着目した場合、その左側の各点の要素はその点よりも「小さく」なるように、右側の各点の要素は「大きく」なるように、それら点の要素を配置。

ま、これも実例を見てもらったほうが話が早い。

実際、根の10の左側の点はみな10より小さく、右側の点は10より大きい。さらに、10の子孫の各点を見ても、この性質は保持されている。たとえば、7もその左は小さく、右は大きい、などなど。

あと、この例では要素は数字になってるけど、これを単語とかにして、たとえば「あか＜あき＜いか」みたいな感じ配置できたりする（だから、さっきの説明では、「小さい」、「大きい」とクオートしておいたのだ）。

それで、何でこんな性質を持たせるのか、っていうと、まあ「2分探索木」って名前からも分かるように、検索がしやすくなるんだよね。たとえば、"dog"っていう点を探したい場合、根が"cat"だったらとりあえず右のほうに行けばいいんだな、って分かる。

てな説明だけで問題は解けると思います。