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)などの変換を行う