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を作ることが出来る