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