概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

二分探索木

各ノードが多くとも2つまでのノードしか持たない二分木の一種で、左の子ノード ≤ 親 ≤ 右の子ノードという制約を持った構造の木
- 最も左にあるノードが最小ノードで、最も右にあるノードが最大ノードとなる
二分探索木に限った話ではないが、木構造の走査（traverse）方法についてかいておく
- 深さ優先探索（depth-first search）
  - 前順（行きがけ順、前置順、preorder）
  - 中順（通りがけ順、中置順、inorder）
  - 後順（帰りがけ順、postorder）
- 幅優先探索（breadth-first search）
  - レベル順（level-order）

計算時間

挿入・削除
- 平均するとO(log n)だが、最悪計算量はO(n)。
探索
- 平衡二分探索木であれば、O(log n)で済む。最悪計算量はO(n)。

実装

package main

import (
	"fmt"
)

// Node is a node of a tree.
type Node struct {
	Key   int
	Left  *Node
	Right *Node
}

// BST is a binary search tree.
type BST struct {
	Root *Node
}

// insert insert a node to tree.
func (b *BST) insert(key int) {
	if b.Root == nil {
		b.Root = &Node{
			Key:   key,
			Left:  nil,
			Right: nil,
		}
	} else {
		recursiveInsert(b.Root, &Node{
			Key:   key,
			Left:  nil,
			Right: nil,
		})
	}
}

// recursiveInsert insert a new node to targetNode recursively.
func recursiveInsert(targetNode *Node, newNode *Node) {
	// if a newNode is smaller than targetNode, insert a newNode to left child node.
	// if a newNode is a bigger than targetNode, insert a newNode to right childe node.
	if newNode.Key < targetNode.Key {
		if targetNode.Left == nil {
			targetNode.Left = newNode
		} else {
			recursiveInsert(targetNode.Left, newNode)
		}
	} else {
		if targetNode.Right == nil {
			targetNode.Right = newNode
		} else {
			recursiveInsert(targetNode.Right, newNode)
		}
	}
}

// remove remove a key from tree.
func (b *BST) remove(key int) {
	recursiveRemove(b.Root, key)
}

// recursiveRemove remove a key from tree recursively.
func recursiveRemove(targetNode *Node, key int) *Node {
	if targetNode == nil {
		return nil
	}

	if key < targetNode.Key {
		targetNode.Left = recursiveRemove(targetNode.Left, key)
		return targetNode
	}

	if key > targetNode.Key {
		targetNode.Right = recursiveRemove(targetNode.Right, key)
		return targetNode
	}

	if targetNode.Left == nil && targetNode.Right == nil {
		targetNode = nil
		return nil
	}

	if targetNode.Left == nil {
		targetNode = targetNode.Right
		return targetNode
	}

	if targetNode.Right == nil {
		targetNode = targetNode.Left
		return targetNode
	}

	leftNodeOfMostRightNode := targetNode.Right

	for {
		if leftNodeOfMostRightNode != nil && leftNodeOfMostRightNode.Left != nil {
			leftNodeOfMostRightNode = leftNodeOfMostRightNode.Left
		} else {
			break
		}
	}

	targetNode.Key = leftNodeOfMostRightNode.Key
	targetNode.Right = recursiveRemove(targetNode.Right, targetNode.Key)
	return targetNode
}

// search search a key from tree.
func (b *BST) search(key int) bool {
	result := recursiveSearch(b.Root, key)

	return result
}

// recursiveSearch search a key from tree recursively.
func recursiveSearch(targetNode *Node, key int) bool {
	if targetNode == nil {
		return false
	}

	if key < targetNode.Key {
		return recursiveSearch(targetNode.Left, key)
	}

	if key > targetNode.Key {
		return recursiveSearch(targetNode.Right, key)
	}

	// targetNode == key
	return true
}

// depth-first search
// inOrderTraverse traverse tree by in-order.
func (b *BST) inOrderTraverse() {
	recursiveInOrderTraverse(b.Root)
}

// recursiveInOrderTraverse traverse tree by in-order recursively.
func recursiveInOrderTraverse(n *Node) {
	if n != nil {
		recursiveInOrderTraverse(n.Left)
		fmt.Printf("%d\n", n.Key)
		recursiveInOrderTraverse(n.Right)
	}
}

// depth-first search
// preOrderTraverse traverse by pre-order.
func (b *BST) preOrderTraverse() {
	recursivePreOrderTraverse(b.Root)
}

// recursivePreOrderTraverse traverse by pre-order recursively.
func recursivePreOrderTraverse(n *Node) {
	if n != nil {
		fmt.Printf("%d\n", n.Key)
		recursivePreOrderTraverse(n.Left)
		recursivePreOrderTraverse(n.Right)
	}
}

// depth-first search
// postOrderTraverse traverse by post-order.
func (b *BST) postOrderTraverse() {
	recursivePostOrderTraverse(b.Root)
}

// recursivePostOrderTraverse traverse by post-order recursively.
func recursivePostOrderTraverse(n *Node) {
	if n != nil {
		recursivePostOrderTraverse(n.Left)
		recursivePostOrderTraverse(n.Right)
		fmt.Printf("%v\n", n.Key)
	}
}

// breadth-first search
// levelOrderTraverse traverse by level-order.
func (b *BST) levelOrderTraverse() {
	if b != nil {
		queue := []*Node{b.Root}

		for len(queue) > 0 {
			currentNode := queue[0]
			fmt.Printf("%d ", currentNode.Key)

			queue = queue[1:]

			if currentNode.Left != nil {
				queue = append(queue, currentNode.Left)
			}

			if currentNode.Right != nil {
				queue = append(queue, currentNode.Right)
			}
		}
	}
}

func main() {
	tree := &BST{}

	tree.insert(10)
	tree.insert(2)
	tree.insert(3)
	tree.insert(3)
	tree.insert(3)
	tree.insert(15)
	tree.insert(14)
	tree.insert(18)
	tree.insert(16)
	tree.insert(16)

	tree.remove(3)
	tree.remove(10)
	tree.remove(16)

	fmt.Println(tree.search(10))
	fmt.Println(tree.search(19))

	// Traverse
	tree.inOrderTraverse()
	tree.preOrderTraverse()
	tree.postOrderTraverse()
	tree.levelOrderTraverse()

	fmt.Printf("%#v\n", tree)
}