スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#入門基本編落穂拾い その23 ツリー構造(3) Binary Search Tree

今回は二分探索木(Binary Search Tree)を紹介します。
二分探索木というのは、ノードに保持する値に大小(順序)関係が定義されていて、どのノードをとっても、右(上)側のノードにはそれより大きい(小さい)値が保持されていて、左(下)側にはそれより小さい(大きい)値が保持されているという条件を満たす二分木です。(同じ値は保持しません。)
 
例 右(上側)が左(下側)より大
    9
   /
  7
 / \
5   6
 \
  4
   \
    2
    
例、タプルの第一成分で大小関係を定義
    (9,"a")
   /
  (7,"k")
 / \
(5,"u") (6"w")
 \
  (4,"n")
   \
    (2,"z")
    
このような、構造の木に対して、例えばその木に6が含まれているかどうかを、調べることを考えてます。
まず根っこの5と6を比べて、6の方が大きいので、6が含まれるとしたら上側の木の中です。次に7と6を比べて、6の方が小さいので、あるなら下側の木の中です。ここで見つかります。
通常のリストなどで一つ一つ調べていくのに比べて高速に調べることができます。
さてそれでは二分探索木を作っていきます。まずは普通の二分木を定義します。
 
type BTree<'a> =
    |Empty
    |Node of ('a * BTree<'a> * BTree<'a>)
 
上の二分木は次のように定義できます。
let t =  Node
    (5, Node (7, Node (9, Empty, Empty), Node (6, Empty, Empty)),
     Node (4, Empty, Node (2, Empty, Empty))) 
 
まずは、値svを持つノードがあるかどうかを調べる関数isMemを定義します。
 
let rec isMem sv btr =
    match btr with
    |Empty ->
         printfn "not find"
    |Node (v,right,left) ->     
        if   sv > v  then isMem sv right //探す値がvより大きいときは右の木を探す
        elif sv < v  then isMem sv left  //探す値がvより小さいときは左の木を探す
        else  printfn "find"   //等しい場合
        
実行例)        
> isMem 8 t;;
not find
val it : unit = ()
> isMem 4 t;;
find
val it : unit = ()
 
木を一直線に降りて行くので、見つからない場合はEmptyとのマッチが一度だけであることに留意しておいてください。
 
次に、値nvを木に加えて新しい木を返す関数addを定義します。
 
一度にやると、ちょっとややこしいので、まずは、木を与えてそれのコピーを作る関数copyを考えてみます。
 
> let rec copy btr =
     match btr with
     |Empty ->
            Empty
     |Node(v,right,left) ->
            Node(v,copy right,copy left);;
 
val copy : BTree<'a> -> BTree<'a>
 
> let tc = copy t;;
 
val tc : BTree<int> =
  Node
    (5, Node (7, Node (9, Empty, Empty), Node (6, Empty, Empty)),
     Node (4, Empty, Node (2, Empty, Empty)))
 
さて、上のisMemとcopyを考え併せてaddを定義すると次のようになります。
 
> let rec add nv btr =
   match btr with
   |Empty ->
        Node(nv,Empty,Empty)    
   |Node (v,right,left) ->     
        if   nv > v   then
            Node(v,add nv right,left)  
        elif nv < v  then
            Node(v,right,add nv left)
        else
            failwith "Data Error" ;;
 
val add : 'a -> BTree<'a> -> BTree<'a> when 'a : comparison
 
(実行例)
> add 10 tc;;
val it : BTree<int> =
  Node
    (5,
     Node
       (7, Node (9, Node (10, Empty, Empty), Empty), Node (6, Empty, Empty)),
     Node (4, Empty, Node (2, Empty, Empty)))
 
さて、それでは簡単な辞書を作ってみます。(Mapのようなものです。)
キーと値を組で与えると登録して、キーを与えるとそれに対応する値を返すようにします。
 
まず2分木の定義は節に二つの値(キーと値)を保持できるように次のようにします。
 
type BTree<'a,'b> =
    |Empty
    |Node of ('a *'b * BTree<'a,'b> * BTree<'a,'b>)
    
キーと値を登録するのは次のようになります。(上のaddとほとんど同じです。)
 
let rec add nk nv btr = //nkはnew key,nvはnew value
   match btr with
   |Empty ->
        Node(nk,nv,Empty,Empty)    
   |Node (k,v,right,left) ->     
        if   nk > k   then
            Node(k,v,add nk nv right,left)  
        elif nk < k  then
            Node(k, v,right,add nk nv left)
        else
           Node(nk,nv,right,left) //同じkeyが存在するときは、値を置き換えます   
 
キーに対応する値を返します。
 
let rec tryFind sk btr =
    match btr with
    |Empty ->
         None
    |Node (k,v,right,left) ->     
        if   sk > k  then tryFind sk right //探す値がkより大きいときは右の木を探す
        elif sk < k  then tryFind sk left  //探す値がkより小さいときは左の木を探す
        else  Some ( v )                   //等しい場合  
 
では使ってみます。
 
> let m0 = Node(8,"cat",Empty,Empty);;
 
val m0 : BTree<int,string> = Node (8, "cat", Empty, Empty)
 
> let m1 = add 1 "dog" m0;;
 
val m1 : BTree<int,string> =
  Node (8, "cat", Empty, Node (1, "dog", Empty, Empty))
 
> let m2 = add 12 "tiger" m1;;
 
val m2 : BTree<int,string> =
  Node
    (8, "cat", Node (12, "tiger", Empty, Empty), Node (1, "dog", Empty, Empty))
 
> tryFind 12 m1;;
val it : string option = None
 
> tryFind 12 m2;;
val it : string option = Some "tiger"
 
(参考リンク)2分探索木http://ja.wikipedia.org/wiki/2%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。