[TIL][DataStructure] Tree & BST

Treeは..。

ノードからなる階層的な資料構造.まずはDOMを知っている私.
DOM Treeに似た構造で、最もよく知られている資料構造です.
一番上のノードはRootと呼ばれ、Rootをはじめ、その下の子孫は一連の形で
基本的には、Child(サブノード)ノードの数およびソート形式は制限されない.
子供を持たなければならない強制性もない.
ただし、Root以外の各ノードにはParent(親ノード)が存在する必要があり、場合によっては同じ親ノードからSibling(兄弟ノード)が存在する可能性があります.
子がなくなるノードを木の末端、葉(Leaf)と呼ぶ.
親子の接続線はEdgeと呼ばれています!
また,ツリーにはDepthとHeightの属性が存在し,ルートベースで他のノードにアクセスする距離Depthを定義しているが,このときRootのDepthは0である.
Heightでは、最高DepthのLeafから、上へ、最低のLeafがHeight 0、Rootが最高のHeightとなります.

Treeのタイプは…。

親の子供1人当たり最大2つのツリー構造はBinary Tree(バイナリツリー)と呼ばれ、各構造に基づいてもう一度タイプを分けることができます.
1.完全バイナリツリー完全バイナリツリー
各ノードは左優先で塗りつぶされ、最後のノードを除いてすべてのノードにサブノードがあります.
2.パーフェクトツリー飽和バイナリツリー
最後の葉を除いて、すべてのノードには2つのサブノードがあり、葉の深さは同じです.
3.Skewed Binary Treeオフセット付きツリー

すべてのノードが一方向のツリーに接続されています.実際にLinked Listと似ています.

そして。

BST‐Binary Search Treeと呼ばれる構造が存在する.

各親ノードはbinary treeと同様に、最大2つのノードをサブノードとして使用できますが、値が自分の値より小さいノードは左側にあり、値が自分の値より大きいノードは右側にあります.
これにより規則性があり、特定の値が見つかった場合、O(n)時間の複雑さを持つツリー、バイナリツリーに比べて、O(logn)時間の複雑さがより速くなります.
巡回BSTには3つの方法がある.
1.Preorder Traversal電位巡視
初めて,親は値の少ない左子と値の大きい右子の順に巡回した.
2.Inorder Traversal中尉巡り
値の小さい左の子を巡回し、親、値の大きい子、または等しい右の子を巡回します.
3.PostoderTraversal後列巡視
まず左と右の子供を見回して、それから一番遅く両親を探します.
最も重要なBSTをJSに実現!

class BinarySearchTreeNode {		// BST 노드 생성자
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  insert(value) {			// 트리에 Node를 추가하는 method
    let node = new BinarySearchTreeNode(value);
    function recursion(el) {
      if(value >= el.value) {
        if(el.right === null) {
          el.right = node;
        }
        else {
          recursion(el.right);
        }
      }
      else if(value < el.value) {
        if(el.left === null) {
          el.left = node;
        }
        else {
          recursion(el.left);
        }
      }
    }
    recursion(this);
  }
  contains(value) { 			//  해당 값을 가진 Node가 존재하는지 반환하는 method
    let result = false;
    function recursion(el) {
      let root = el;
      if(el.value === value) {
        result = true;
        return;
      }
      else {
        if(el.value > value) {
          if(el.left) {
            root = el.left;
            recursion(root);
          }
        }
        else if(el.value <= value) {
          if(el.right) {
            root = el.right;
            recursion(root);
          }
        }
      }
    }
    recursion(this);
    return result;
  }
  inorder(callback) {			// 트리를 순회하여 콜백 함수를 통해 특정 행동을 하는 method
    let rootNode = this;
    function recursion(node){
      let leftNode=node.left;
      let rightNode=node.right;
      if(leftNode){
        recursion(leftNode);
      } 
      callback(node.value);
      if(rightNode){ 
        recursion(rightNode);
      }
    }
    recursion(rootNode);
  }
}

BSTとTreeを実施する体験は再回帰の重要性です...Dom Tree巡りの時も疲れましたが、今回のBSTの実施を通じて、まだ100%征服回帰していないと感じました…
特に最後の中尉巡りの状況は、まだ完全に理解されていないので、勉強する必要があるかもしれません.
tree資料構造はweb、app開発者にとって就職上の重要性が高いので、もう一度掘る必要があります!!