Goでのアルゴリズムクイックリファレンス第2版(二分探索木)

Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。

前回: Goでのアルゴリズムクイックリファレンス第2版(ブルームフィルタ)

今回は二分探索木

二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。

package main

import "fmt"

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

type BinaryTree struct {
	Root *BinaryNode
}

func NewBinaryNode(val int) *BinaryNode {
	return &BinaryNode{val, new(BinaryNode), new(BinaryNode)}
}

func (n *BinaryTree) Add(val int) {
	if n.Root == nil {
		n.Root = NewBinaryNode(val)
	} else {
		n.Root.Add(val)
	}
}

func (n *BinaryNode) Add(val int) {
	if val <= n.Value {
		if n.Left != nil {
			n.Left.Add(val)
		} else {
			n.Left = NewBinaryNode(val)
		}
	} else {
		if n.Right != nil {
			n.Right.Add(val)
		} else {
			n.Right = NewBinaryNode(val)
		}
	}
}

func (n *BinaryTree) Contains(target int) bool {
	node := n.Root
	for node != nil {
		if target < node.Value {
			node = node.Left
		} else if target > node.Value {
			node = node.Right
		} else {
			return true
		}
	}
	return false
}

func main() {
	bn := new(BinaryTree)
	bn.Add(1)
	bn.Add(2)
	bn.Add(3)
	bn.Add(100)

	if bn.Contains(4) == false {
		fmt.Println("not found")
	}

	if bn.Contains(100) {
		fmt.Println("found")
	}
}

次回は深さ優先探索です。