Data Structureを整理してみましょう.//Part3

Data Structure,

複数のデータセットの使用と格納方法を定義します.

5. Tree

ノードごとに階層化されたデータ構造.
読みやすい情報をたくさん整理するときに役立ちます.
ファミリースペクトルやコンピュータのディレクトリ構造や組織図などの形式を考慮することができる.

図を見て、Treeを理解してください.
Treeは各ノードからなり,上部にRoot Nodeと呼ばれる起点がある.
関係により、これらのノードはParentノードであってもよいし、Childノードであってもよい.
もちろん、どちらでもいいです.
最初のRoot Nodeを作成し、Child Nodeを追加できます.
Root NodeだけがChild Nodeを作成できるわけではありません.各NodeはChild Nodeを持つことができます.
ルートベースで他のノードにアクセスできる距離をDepthと呼ぶ.
ノードとノードを接続する線をEdgeと呼びます.
次はTreeの基本的な方法です.

class TreeNode {
  constructor(value) {
    this.value = value; 
    this.children = [];
  }

  insertNode(value) {
    let newTreeNode = new TreeNode(value);
    this.children.push(newTreeNode);
  }

  contains(value) {
    if(this.value === value) {
      return true;
    } else {
        for(let i = 0; i < this.children.length; i++) {
          if(this.children[i].contains(value)) {
            return true
          }
        }
      }
    return false;
  }
}

6.BinarySearchTree(BST)、バイナリナビゲーション構造

Treeの形式ですが、各ノードには最大2つのChild Nodeがあります.

BSTの機能は次のとおりです.
パラメータの左下の値は、パラメータの値より小さくなければなりません.
逆に、Parentの右下の値はParentの値より大きくなければなりません.
BSTをブラウズする方法は次のとおりです.
1.深度優先ナビゲーション
:Rootから徐々に最深のDepthに入り、さらに最深のDepthに入り、Treeのアプローチを模索します.
2.幅優先ナビゲーション
:1つのDepthの各ノードは、最初にナビゲート(またはSibling)し、次にDepthに入り、Tree全体をナビゲートする方法です.
次はBSTの基本的な方法です.

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null; 
    this.right = null;
  }

  insert(value) {    
    if (value > this.value) {
      if(this.right === null) {
        let newNode = new BinarySearchTreeNode(value);
        this.right = newNode;
      } else {
          this.right.insert(value);
      }
    }
    if (value < this.value) {
      if(this.left === null) {
        let newNode = new BinarySearchTreeNode(value);
        this.left = newNode;
      } else {
          this.left.insert(value);
        }
    }
  }

  contains(value) {
    if(this.value === value) {
      return true;
    } else {
        if(this.value > value) {
          if(this.left === null) {
            return false;
          } else if(this.left.contains(value)) {
            return true;
          }
        } else {
          if(this.right === null) {
            return false;
          } else if(this.right.contains(value)) {
            return true;
          }
        }
      }
      return false;
  }
}