Golangで二分探索木の生成・探索をする

この記事は、筆者ブログを出典としています。

二分探索木とは

左の子の値 ≤ 親の値 ≤ 右の子の値 という制約がある二分木である。

二分探索木にデータを格納するメリット

線形リスト(配列に格納されたデータ)を0番目から順番に検索するよりも、早く目的のデータを見つけ出せる可能性がある。

ここで、要素数を $N$ とする。

木の高さ $H$ は

• 最良の場合: 平衡状態で $H = log_{2}N$
• 最悪の場合: 全てのノードで左(または右)だけに子が続くとき $H = N$ (線形リストと同じ)

深さ優先探索を行う場合、時間計算量は $O(log_{2}N)≤E≤O(N)$であり、線形リストの時間計算量$O(N)$に対し、削減される。

Goでの実装

ノードの定義

type node struct {
	key   int
	value int
	left  *node
	right *node
}

ノードには、ノードを識別するkeyと、値(データ)を格納するvalueをまず格納する。また、左右の葉にぶら下がる子ノードへのポインタも含める。

木の定義

type tree struct {
	root *node
}

二分探索木の生成

着目ノードの葉（左右は着目ノードの値との比較で決める）に子ノードがなければ、新たなノードを作成し値を格納する。

func maketree(parentNode *node, newKey int, newValue int) {
	var childNode node
	childNode.key = newKey
	childNode.value = newValue
	if newValue >= parentNode.value {
		if parentNode.right == nil {
			parentNode.right = &childNode
		} else {
			maketree(parentNode.right, newKey, newValue)
		}
	} else {
		if parentNode.left == nil {
			parentNode.left = &childNode
		} else {
			maketree(parentNode.left, newKey, newValue)
		}
	}
}

深さ優先探索

targetNumberを右側ノードから深さ優先探索する。

func findNumber(targetNode *node, targetNumber int) {
	if targetNode.value == targetNumber {
		fmt.Printf("target number[%v] found at key[%v]\n", targetNumber, targetNode.key)
	} else if targetNumber > targetNode.value {
		if targetNode.right != nil {
			findNumber(targetNode.right, targetNumber)
		} else {
			fmt.Printf("target number[%v] not found.\n", targetNumber)
		}
	} else {
		if targetNode.left != nil {
			findNumber(targetNode.left, targetNumber)
		} else {
			fmt.Printf("target number[%v] not found.\n", targetNumber)
		}
	}
}

データの生成、木への格納、探索を行うメイン関数

func main() {
    //格納するデータを生成
        maxValue := 1000
	var valueArray = []int{maxValue/2}
	rand.Seed(time.Now().UnixNano())
	for index := 0; index < maxValue; index = index + 1 {
		valueArray = append(valueArray, rand.Intn(maxValue))
	}

	//木と根ノードのインスタンス化
	var myTree tree
	var firstNode node
	myTree.root = &firstNode

	//二分探索木の生成
	for index := 0; index < len(valueArray); index = index + 1 {
		maketree(myTree.root, index, valueArray[index])
	}

	//探索
	findNumber(myTree.root, 100)
}

ここでは、平衡状態に近づけるため、根ノードを$maxValue/2$とした。実運用上では、データが新たに追加または削除されたりした場合、平衡状態に近づける(=木の高さを減らす)為に、回転(Tree Rebalancing)などの変換を行う