이진 탐색 트리

이진 트리는 자식 노드가 최대 2개인 노드들로 구성된 트리를 말한다.

이진 탐색 트리는 정렬된 이진 트리이다.
다음과 같은 2가지 속성이 추가된 이진 트리라고 생각하자.
left child node is smaller than its parent Node.
right child node is greater than its parent Node.

• 자식 노드의 순서가 중요하다.
  • 작은 값을 왼쪽 노드에, 큰 값을 오른쪽 노드에 정렬한다.
• 중복된 키를 허용하지 않는다.

쉽게 말하면, 트리를 탐색할 때 왼쪽은 내려갈수록 작아지고, 오른쪽은 내려갈수록 커진다.

구현

일반 트리를 구현할 때에는 자식이 얼마나 될지 모르기 때문에 자식 노드를 담을 배열을 선언해서 주소값을 저장했지만, 이진 트리는 왼쪽과 오른쪽 두 개의 주소를 가리키는 포인터 변수만 있으면 된다.

이진 탐색 트리의 조건을 만족하기 위해서는 insert 메서드의 구현이 가장 중요하다.
이 때 재귀를 사용한다.
재귀 호출의 흐름을 보자.

1. insert(value) 메서드가 호출되면, 일단 인자로 받은 value 값이 현재 부모 노드의 값보다 큰 지, 작은 지 검사한다.

2. 작다고 가정하고 생각해보자.
   값이 작으니까 넘겨받은 value를 부모 노드의 왼쪽에 넣고 싶다 => this._toLeft(value)호출, 이 때 넘겨받은 value를 인자로 다시 넘겨주는 것이 중요하다.

3. _toLeft(value) 메서드가 하는 일은 왼쪽에 이미 자식이 있는지 없는 지를 확인해서 넘겨받은 value가 들어갈 곳을 찾는 역할을 한다.
   이미 왼쪽에 자식이 있다면, 자식한테 위임한다. 너가 알아서 이 데이터 처리해라
   : this.left.insert(value)
   왼쪽에 자식이 없다면?
   : this.left = new BST(value), 자식으로 만들어 준다.

위의 세번째 과정에서 자식에서 데이터를 주면서 위임하는 것이 곧 재귀 호출이다.
빈 공간을 찾을 때까지 insert를 재귀 호출 하는 것이 point

contains 메서드는 값을 인자로 받아서, 해당하는 트리의 부분 전체를 리턴하는 메서드다.
함수 로직은 위의 insert를 재귀로 구현한 과정과 같고, 다만 값이 같을 때 this를 리턴하는 것이 포인트다.
주의할 점은 재귀 함수 안에서 return 값이 있는 경우에는 함수를 다시 호출할 때, 그 앞에 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
  }
}

---

validate 함수 구현
인자로 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;
}