binary treeについて

最近プログラミングコンテストを眺めるようになって、データ構造も調べる様になった。何が嬉しいのか、golangでどうやって実装するケースがあるのか、をざっくり理解する。

binary tree

あるノード(節点 node)が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。

golangではこんな感じで表現できそう

type Tree struct {  
    Left  *Tree
    Value int
    Right *Tree
}

且つ、下記のようなルールを付与すると、色々効率的になる。ちなみに、このように整列されているものを二分探索木(binary search tree)と呼ぶ。

二部探索とは

例えば、100個あるうちから正解を1個求めるとき、1,2・・・と試していけば最悪99回間違える必要があるが、50,25...と試していけばlog2nで答えにたどり着く。このことを二部探索と行って、binary treeはこれに相性がいい。
通常のソートされた配列でも同様の探索方法が取れるが、左の木をたどることで最小値を、右の木をたどることで最大値を簡単に求めることができるというメリットが有る。

Depth First Search

この二部探索方法にも色々あるが、例えば深さ優先(Depth First)検索がある。

golangだとこんな感じだろうか。

func Walk(t *Tree, ch chan int) {  
    if t == nil {
        return
    }
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}