忍者ブログ

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



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

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

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

http://www.ehmtm.com/image/Binary_search_tree.png

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

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

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



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

PR
この記事にコメントする
お名前
メールアドレス
URL
コメント
この記事へのトラックバック
この記事にトラックバックする:
カレンダー
05 2017/06 07
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30
最新コメント
[06/28 FerminBycle]
[06/27 カルティエ 指輪 クリーニング]
[06/27 ブランド激安 時計 0752]
[06/27 ブランド激安通販]
[06/26 バッグ ブランド激安]
[06/26 s品 n品]
[06/26 ルイビトン激安本物]
[06/26 グッチ 長財布 メンズ]
[06/26 ブルガリ カフェ 銀座]
[06/26 レディース財布 ブランド激安]
最新トラックバック
メール
ブログ作成者(はやし)に直接訴えたいことがある、という場合は、下のアドレスにメールをどうぞ。

thayashi#ucalgary.ca
(#を@に置換してください)

ブログ内検索
Google
WWW を検索 このブログ内を検索

はやしのブログ内で紹介された
 書籍の検索はこちら
 音盤の検索はこちら
ランダムおすすめ
(忍者ブログに引越してから、うまくうごかなくなってしまいました。いつか、直します)
Randombook
このブログで紹介したことのある本をランダム表示。
Randomusic
このブログで紹介したことのある音をランダム表示。
自分がらみのリンク
はやしのブログ書籍一覧
このブログで言及された書籍の一覧。
はやしのブログ音盤一覧
このブログで言及された音盤の一覧。
最近のおすすめ本
最近のおすすめ音

Copyright © [ はやしのブログ ]
No right reserved except those which belong to someone else.
Special Template : 忍者ブログ de テンプレート and ブログアクセスアップ
Special Thanks : 忍者ブログ
Commercial message : [PR]