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")
    }
}

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