Binary Trees

二元ツリーは、最大2つの参照ノードからなるツリー構造です.
データ構造は、ノードや参照(たとえば、既存のツリー)からなる周期の影響を受けませんが、ツリーは参照の数を決定しません.
バイナリツリーには条件があります.
すべてのノード
左側のサブノードの[小さい](Left Sub)値
右側のサブノードの「より大きい」値
与えなければならない.
これらの条件がすべて満たされている場合にのみ、バイナリプローブツリーが生成されます.それ以外は
ノードの値は重複しません.
ノードの価値は外来ではない.
まだ2つの条件があります.

このGifをよく見れば理解できる
ソース:(https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node)
では,SWIFTを用いてバイナリナビゲーションツリーを実現する.

class BinaryNode<Element> {
    var value : Element
    var leftChild : BinaryNode?
    var rightChild : BinaryNode?
    init ( _ value : Element) {
        self.value = value
    }
}

classを定義する場合、Elementを使用してすべてのデータを受信します.
あと前の条件はvalueが傍観者になれないのでNon Option
では、行う前に、順番がどのように働いているのかを理解しておきましょう.

ツリーの場合は、次の順になります.

0 - 1 - 5 - 7 - 8 - 9

このように行います
最初のルートユーザ7から、まずleftChildに0でアクセスする.
これにより、ノードの親ノード1にアクセスし、右側の5にアクセスできます.
左側のアクセスが完了するとrootに戻ります.その後右8->彼の両親9
彼らに近づく
コードを見てみましょう.

extension BinaryNode {
	func traverseInOrder(visit : (Element) -> Void) {
        //재귀
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }
}

以上のコードは再帰的に実行できます.
では、値を代入して出力します.

let ten = BinaryNode(10)
let nine = BinaryNode(9)
let one = BinaryNode(1)
let two = BinaryNode(2)
let three = BinaryNode(3)
let four = BinaryNode(4)
let six = BinaryNode(6)

ten.leftChild = two
ten.rightChild = nine
nine.leftChild = one
nine.rightChild = three
two.leftChild = four
two.rightChild = six

こんな風にクリスマスツリーを作ると

こんな木ができました.
関数出力値を使用します.

正常に動作.
ここでの問題は、ルートノードまたは親ノードを介してchildにアクセスできることです.
では、この問題を補う方法で.
これは、真ん中から根を通って左から右、最後に根に着くのではなく、左から右の方法です.

    func traversePostOrder(visit : (Element) -> Void) {
        leftChild?.traversePostOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
        visit(value)
    }

印刷してみます.

もう一つは船東門めぐりというもの.
これは根からずっと下を向いていることを意味します.

    func traversePreOrder(visit : (Element) -> Void) {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
    }

Binary Search Trees

バイナリ検索ツリー(BST)は、バイナリ検索ツリーとして機能する.
例を挙げて説明しましょう.

最初のROOTで動物かどうかを尋ねるそして答えによる.
左と右に分かれます.
動物でなければ岩になり、動物であれば毛の有無を聞かれます.
各特定のノードは、以下の内容を表すTreeノードです.
これにより、「はい」または「いいえ」の2つの質問に答えるだけで、すぐに結果を確認できます.
これには、検索結果をすばやく検索できるという利点があります.

Case Study - Array vs BST

上はアレイアレイ
次はBST
この二つで比較してみる
まず、各アレイを比較し、線形検索を行う必要があります.
また,アイテム数が増えるにつれて配列の検索時間も長くなる.
では、BSTの様子を見てみましょう.
たとえば、105の値を探すとします.

BSTはrootに基づいてタスクを実行します.
必要な値-105はrightにあります.rootより大きい値であることは当然です.
左側は検索する必要はありません.
だから半分の時間を減らしました
私たちは質問にしか答えません.105は77より大きい価格ですか?答えが正しい場合は、必要な値を見つけることができます.値段がもう少し安くても.

Insert

また、挿入する場合も比較します.

配列にsortを使用して0を挿入する場合.
int型Arrayなので、0の値は自然に最初の要素として位置づけられます.
しかし、実際には、0を挿入するために、他の要素はすべて後方に移動します.
これにより、特定のアレイの複雑さが増大します.

しかしBSTではどうなるのでしょうか?
いくつかの質問に答えればいいです.
rootに対して0は40未満です.
これで18と0の値を左に比較できます.
回答に従って、左側に移動し、最後の質問に答えます.
それなら.

簡単ですよね?

Remove

removeもそうです.配列は、消去する値を消去し、残りの要素を適切な位置に移動します.これにより、複雑さが増します.
BSTは枝を切るだけでいいです.
次にBSTの実装について議論する.