データ構造:囲碁でのバイナリ検索木

このエキサイティングな探求の継続的なデータ構造とアルゴリズムについての詳細をご覧ください.私は、これから参照されるリンクリストの上で最後に議論される知識の上で構築するバイナリ検索木について話すのが好きですbook , あなたはポストを見つけることができます.

バイナリ探索木の理由

高速検索や柔軟な更新を可能にするデータ構造がありますが、両方ともありません.ソートされていない、二重にリンクされたリストは、一定時間に挿入をサポートしますO(1) しかし、検索は線形時間O(n) 悪い場合は.ソートされた配列は、対数時間で検索を助けるバイナリ検索をサポートするO(logn) , しかし、線形時間更新のコストで.
バイナリ検索ツリーは、高速検索と対数時間で更新することができますO(logn) しかし、これについては、バイナリ検索ツリーのバランシングについて話をするときに説明します.
ツリーの配置とバランシングは、左側のサブツリー上のノードのキーが右のサブツリーのキーよりも小さくなるように行われます.

バイナリ探索木の実装

バイナリ検索ツリーを作成するには、ノードごとに2つのポインタを持つリンクリストが必要です.
アイデアは、左側のサブツリーと右のサブツリーとノードがキーでラベルされていることです.バイナリーサーチツリーに次の操作を実装します.
ツリーのノードは1です.左側ポインタ2 .右ポインタ3.オプションの親ポインタ4.データフィールドで、値を格納します.この実装のすべてのコードとテストはここで見つかりますgithub .
バイナリ検索ツリーを作成するには、root すべてが構築される場合、それは空でありえます、あるいは、それはノードから成っている2つのバイナリー探索木と一緒にノードから成ることができます.そして、ノード(構成される最小の単位であるノード(木)と基礎から成る右の部分木)と以下のようにバイナリー探索木の基礎を作ります:

    // Tree is the basic structure or node in a binary search tree.
    type Tree struct {
        parent *Tree  // parent can be nil i.e Root tree
        left   *Tree  // left child or left subtree
        right  *Tree  // right child or right subtree
        Item   string // data held by the node
    }

親は木であるかもしれませんが、ルートツリーの場合、それは空になります、そして、左と右は我々が木の終わりにあることを示す空でもありえます.このデータ構造を使用して辞書(昇順順序でソートされた単語のコレクション)をモデル化します.

    // BinarySearchTree to store the words of a dictionary.
    type BinarySearchTree struct {
        Root *Tree
    }

挿入

私は、挿入操作、再帰的で非再帰的なアプローチの2つの異なる実装を持っています.

非再帰性
このアプローチは、より多くのコードとビットを理由に簡単です.我々は、ルートからバイナリの検索木を通過し始めて、それから、挿入されるアイテムに基づいて、以下の決定点を持ちます、そして、これは再帰的アプローチの後で概念を作ります:

ルートが空の場合は、項目を挿入し、新しいツリーを作成します.ここで、親、左、右のサブツリーまたは子はNILです.

挿入される項目がノードの現在の項目より小さい場合、左のサブツリーに移動し、左のサブツリーの終わりまで到達するまで検索を続けます.

挿入する項目がノードの現在の項目より大きい場合は、上記の手順を繰り返しますが、左のサブツリーに移動するのではなく、右のサブツリーに移動します.

これは以下の通りです.

    func (bt *BinarySearchTree) NormalInsert(item string) {
        if bt.Root == nil {
            bt.Root = &Tree{
                Item: item,
            }
            return
        }
        currentTree := bt.Root

    insertionLoop:
        for {
            switch {
            // go to the left subtree
            case item < currentTree.Item:
                if currentTree.left == nil { // at the end of the left subtrees
                    // attach the new node
                    currentTree.left = &Tree{
                        Item:   item,
                        parent: currentTree,
                    }
                    break insertionLoop
                } else {
                    currentTree = currentTree.left
                }
                break
            // go to the right subtree
            case item > currentTree.Item:
                if currentTree.right == nil { // at the end of the right subtree
                    // attach the new node
                    currentTree.right = &Tree{
                        Item:   item,
                        parent: currentTree,
                    }
                    break insertionLoop
                } else {
                    currentTree = currentTree.right
                }
                break
            default:
                break insertionLoop
            }
        }
    }

我々はループにラベルを必要としたbreak switch文では、それはスイッチから外れて、ループではありません.

再帰的
上で議論したように、このアプローチはより少ないコードですが、特にあなたが新しい木をその親に接続したい点になるとき、特に、上の同じアプローチに従う理由に少しはかかります.

    func (bt *BinarySearchTree) RecursiveInsert(currentTree **Tree, item string, parent *Tree) {
        // currentTree is a pointer to the memory location(also a pointer) where the current node tree
        // is stored. This is needed because, when we get to a tree that is empty and we need to insert
        // the new item, we'll need to replace the empty space (which is to hold a tree) with the new tree, this warrants having access to the location.
        // If you don't do this, your update will be detached from the main binary search tree.

        // when we have come to the end of the search.
        if *currentTree == nil {
            newTree := &Tree{
                Item:   item,
                left:   nil,
                right:  nil,
                parent: parent,
            }
            // Attach to its parent, by getting the memory location where the currentTree.
            *currentTree = newTree
            return
        }

        // Recursively search for where to put the item.
        if item < (*currentTree).Item { // diverge to the left subtree
            bt.RecursiveInsert(&(*currentTree).left, item, *currentTree)
        } else {
            bt.RecursiveInsert(&(*currentTree).right, item, *currentTree)
        }
    }

ツリーへの新しいノードの接続は一定時間かかるが、ノードの前に実行される検索操作はO(h) , 木の高さ
ここでの挿入は、バランスの取れた検索ツリーを保証しないことに注意してください.これは、赤い黒い木とO(logn) 高さと挿入、更新、および削除のために適用されると、ツリーは、ツリーの高さを保証するためにバランスが保たれていることに近いように突然変異に応答しますO(log n) .
私たちがこれまでに持っているものはランダムなバイナリ検索ツリーです.しかし、挿入が南に行くなら(私たちがユーザーによって挿入された値または項目を制御しない)、我々は木のためにo(n)高さに終わることができます.

探索
二項探索木にラベルを付けることは重要である.
これらは、この操作を実行するときに考慮する手順です.

ツリーのルートで検索を開始する

を検索するキーがある場合

キーが大きいか、ルートのキーまたは識別子より小さいかどうかチェックしてください、そして、これは我々が木または右の左の子を下ろすかどうか決定します.

あなたがアイテムを見つけるか、木の端に着くまで、これらのステップを再帰的に続けてください

探索アルゴリズムはO(h) 時間、hはバイナリ検索ツリーの高さです
木の最小のノードを見つけることは、最も小さなサブツリーが最小のアイテムを持っているということを理解しています.また、最大のサブツリーは木の中で最も高い項目を持っています.左のサブツリーのすべてのキーがルートのそれより少ない値を持っているので、最小のキーはルートの左の部分木に存在しなければなりません、そして、右の下位木のキーがルートより高いので、最も大きいキーは右の下位木にあります.これらの動作を以下に示す.
検索

    // Search searches for an item, it expects to start from the Root.
    func (bt *BinarySearchTree) Search(item string) string {

        if result := bt.Root.Search(bt.Root, item); result != nil { // found!
            return result.Item
        }
        return ""
    }

ミニマム

    func (bt *BinarySearchTree) FindMinimum() *Tree {
        // start from the Root and move to the left subtrees
        minTree := bt.Root

        for minTree.left != nil {
            minTree = minTree.left
        }
        return minTree
    }

最大

    // FindMaximum returns the largest or highest item item in the tree.
    func (bt *BinarySearchTree) FindMaximum() *Tree {
        // start from the Root and move right wards
        maxTree := bt.Root

        for maxTree.right != nil {
            maxTree = maxTree.right
        }
        return maxTree
    }

横断する

これは、ルートバイナリツリー内のすべてのノードを訪問するには、これは多くのアルゴリズムの非常に重要な部分です.これは、グラフのノードとエッジを横断するための基礎です.
これは、最小のキーがルートの左側にあり、最大のキーがルートツリーの右側にあるので、バイナリ検索ツリー内の要素が既にソートされていることについて理解しています.
これは木のノードを訪問して、左の木を処理して、木の項目を処理して、また、右の部分木を再帰的に訪問する再帰的なアプローチを使用することによって達成されます.この操作を行う順序は1になる.順横断2.順次横断3ポストオーダー横断

順を追って
左のサブツリーを横切って、アイテムを処理して、右のサブツリーを横断します.そして、再帰のインデックスは、我々が葉でないか、子供なしでノードに達するとき、あります.

プリオーダー横断:
最初に木の項目を処理し、左の部分木を横切って右の部分木を横切る

post - order traversal :
左のサブツリーを最初に横断し、右のサブツリーを横断し、ツリー内の項目を処理します.
二次探索木が演算式または論理式を表したとき、順序と順序の前後関係は便利です.
横断の走行時間は線形であるO(n) なぜなら、それぞれのアイテムが一度訪れているからです.
下記は、順方向のverversalの説明です、あなたは上の順序の注文を受注することができて、注文しますgithub :
順を追って

    // InOrderTraversal traverse in the order [smallest ... largest] [allLeft ... allRight]
    func (bt *BinarySearchTree) InOrderTraversal(t *Tree, processItem func (string)) {
        if t != nil {
            bt.InOrderTraversal(t.left, processItem)
            // process the item in the tree using the power of closure
            processItem(t.Item)
            bt.InOrderTraversal(t.right, processItem)
        }
}

最後の思考

Picking the wrong data structure for the job can be disastrous in terms of performance. Identifying the very best data structure is usually not as critical because there can be several choices that perform similarly. - Steven S. Skiena

あなたが解決しようとしている問題は、常にあなたが使用するデータ構造の種類を通知する必要があります.それはいつものように学習の旅は、私はあなたからの質問(s)またはフィードバックを持っている場合は、楽しい時を聞いて喜んでいるでしょう!