バイナリナビゲーションツリー

バイナリツリーとは、最大2つのサブノードからなるツリーです.
バイナリ・ナビゲーション・ツリーは、ソートされたバイナリ・ツリーです.
次の2つのプロパティが追加されたバイナリ・ツリーを想定します.
left child node is smaller than its parent Node.
right child node is greater than its parent Node.

サブノードの順序が重要です.

の小さい値を左側のノードに並べ、大きい値を右側のノードに並べます.

キーの重複は許可されていません.

簡単に言えば、木をブラウズするとき、左は下に行くほど小さくなり、右は下に行くほど大きくなります.

インプリメンテーション

一般ツリーを実装する場合,サブノードがどれだけあるか分からないため,サブノードを含む配列を宣言してアドレス値を格納するが,このアレイツリーは左右2つのアドレスを指すポインタ変数のみでよい.
バイナリ探索ツリーの条件を満たすためには,insert法を実現することが最も重要である.
この時は鬼を使っていました.
再帰呼び出しの流れを見てみましょう.

insert(value)メソッドが呼び出されると、まず、パラメータとして受信された値が現在の親ノードの値より大きいかどうかを確認します.

小さいと仮定して、考えてみてください.
値が小さいため、親ノードの左側=>this._toLeft(value)呼び出しに転送された値を入れたい場合は、転送された値をパラメータに再転送することが重要です.

_toLeft(value)の方法は、左側に子供がいるかどうかを確認し、得られた価値を見つけることです.
左に子供ができたら、子供に任せます.自分でこのデータを処理しなさい.
: this.left.insert(value)左に子供がいなかったら?
:this.left = new BST(value)、あなたを子供にします.

上記の第3のプロセスでは、サブシステムからデータを送信し、データを委任することが再帰呼び出しである.
点containsメソッドは、パラメータとして値を受け入れ、ツリーの全部分を返す.
関数ロジックは、上記のinsert再帰実装プロセスと同様であり、thisを値と同時に返すことに重点を置いている.
再帰関数にreturn値がある場合は、関数を再呼び出しするときに、終了条件に遭遇したときにcallスタックを介して上に登ることができるように、関数の前にreturnを付ける必要があります.

class BST {
  // BST의 constructor를 구현.
  // constructor로 만든 객체는 이진 탐색 트리의 Node가 된다.
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  // tree에 value를 추가한다.
  insert(value) {
    value <= this.data ? this._toLeft(value) : this._toRight(value);
    // 입력 값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건이 있어야 한다.
    // 현재 값보다 작으면 왼쪽에, 크면 오른쪽에 넣는다.
  }
  _toLeft(value) {
    this.left ? this.left.insert(value) : this.left = new BST(value);
    // 빈 공간을 찾을 때까지 insert 호출, null이면 노드 생성해서 이어주기.
  }

  _toRight(value) {
    this.right ? this.right.insert(value) : this.right = new BST(value);
    // 빈 공간을 찾을 때까지 insert 호출, null이면 노드 생성해서 이어주기.
  }
  
  contains(value) {
    if(value === this.value) return this;
    return value <= this.value ? this._findLeft(value) : this._findRight(value);
    // 값을 비교해서 작으면 왼쪽, 크면 오른쪽에서 찾는다.
  }

  _findLeft(value) {
    return this.left ? this.left.contains(value) : null;
    // left가 있으면 탐색을 위해 왼쪽 아래로 다시 contains 재귀 호출, 없으면 return null
  }
  _findRight(value) {
    return this.right ? this.right.contains(value) : null;
    // right가 있으면 탐색을 위해 오른쪽 아래로 다시 contains 재귀 호출, 없으면 return null
  }
}

検証関数の実装
パラメータでnodeを受信して、ツリーがバイナリナビゲーションツリーの関数であるかどうかを確認します.
バイナリナビゲーションツリーの成立条件
-左側の子ノードは、親ノードよりも常に小さくなければなりません.
-右側の子ノードは常に親ノードより大きい必要があります.

// min : 상한선, max : 하한선
// 트리의 root로 어떤 값이 들어올지 모르기 때문에 
// 초기값으로 min = Infinity, max = -Infinity 설정해준다.
function vaildate(node, min = Infinity, max = -Infinity) {
  // node가 null일 때
  if(!node) return false;
  
  if(max < node.value && node.value <= min) {
    // 왼쪽도 validate call : min = 상한선을 node.value로
    if(node.left) return vaildate(node.left, node.value, max);
    // 오른쪽 validate call : max = 하한선을 node.value로
    if(node.right) return vaildate(node.right, min, node.value);
  }
  else {
    // 한 번이라도 false 만나면 콜스택 타고 올라가서 false를 return
    return false;
  }
  // 위에서 한 번도 false 안 걸리면, 최종적으로 true를 return
  return true;
}