読者です 読者をやめる 読者になる 読者になる

stMind

You'll never blog alone

golangでbinary tree

Code as Art: Binary tree and some generic tricks with golang

golangでbinary treeを作る!というので読んでみると、理解しやすかったので、実装もトレースしてやってみた。

目標

「intやstringなど特定の型ではなく、任意の型を扱えるbinary treeを実装する」となってました。

実装

データ構造体とコンストラクタ関数の定義

まずは、binary treeの構造体型を作ります。このとき、nodeは空のインタフェース型にします。

type BinaryTree struct {
    node  interface{}
    left  *BinaryTree
    right *BinaryTree
}

この型に対するコンストラクタを作ります。

func New() *BinaryTree {
    tree := &BinaryTree{}
    tree.node = nil
    return tree
}
Insert関数

binary treeのノードを作成するInsert関数を作ります。Insert関数の動作は、

  • treeと新しいnodeのデータを受け取る
  • treeが空であれば新しいnodeをこのデータから作成
  • treeが空でなければ現在のnodeの値と新しいnodeの値と比較
    • 新しい値の方が大であれば、再帰的に辿って右側に追加
    • 新しい値の方が小であれば、同じように再帰的に辿って左側に追加
func (tree *BinaryTree) Insert(value interface{}) {
    if tree.node == nil {
        tree.node = value
        tree.right = New()
        tree.left = New()
        return
    } else {
        if value < tree.node {
            tree.left.Insert(value)
        } else {
            tree.right.Insert(value)
        }

    }
}
関数型を使う

シンプルに実装できたように見えますが、これを実行するとエラーになります。

prog.go:24: invalid operation: value < tree.node (operator < not defined on interface)
 [process exited with non-zero status]

空のinterface型のvalueとBinaryNode型のtree.nodeを比較するオペレータは無効であるというものです。
intやstringやユーザ定義の型はどのように比較すれば良いのか?
そこで、最初のBinaryTree型に新しく関数型のフィールドを加えます。

type BinaryTree struct {
    node    interface{}
    left    *BinaryTree
    right   *BinaryTree
    lessFun Comparable
}

type Comparable func(c1 interface{}, c2 interface{}) bool

Comparableは、c1とc2の二つの空のinteface型に対して、c1がc2より小ならtrue、そうでなければfalseを返す。 binary treeを作る人は、どの型のtreeであるかを知っていて、比較の方法も知っているので、それを定義してコンストラクタで初期化します。 (ここは、オリジナルのエントリーとは記載の順番を入れ替え)

intの場合。

func compare(x interface{}, y interface{}) bool {
    if x.(int) < y.(int) {
        return true
    } else {
        return false
    }
}

それに合わせてNewとInsertも修正して完成です。

func New(compareFun Comaparable) *BinaryTree {
    tree := &BinaryTree{}
    tree.node = nil
    tree.lessFun = compareFun
    return tree
}

func (tree *BinaryTree) Insert(value interface{}) {
    if tree.node == nil {
        tree.node = value
        tree.right = New(tree.lessFun)
        tree.left = New(tree.lessFun)
        return
    } else {
        if tree.lessFun(value, tree.node) == true {
            tree.left.Insert(value)
        } else {
            tree.right.Insert(value)
        }

    }
}

TL;DR

  • interface{}と関数型を使うと、任意の型に対するbinary treeを作ることが出来る