bst

이진탐색트리는 트리형태를 갖지만, 자식노드로 두 개의 노드만 가지는 형태이다.
root보다 작은 경우는 왼쪽, 큰 경우는 오른쪽에 위치하기 때문에,
탐색을 할 때 log N의 시간 복잡도를 가지게 된다.

자료구조에 대해 항상 봐야지 봐야지 생각만 하다가 이제서야 하나씩 시작하게 됐다.

맡은 업무가 알고리즘 관련이라 그런지 자료구조를 많이 접하게 되는게 다행이라면 다행인 것 같다.

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

    if (value < this.value) {
      if (this.left === null) {
        this.left = new BinarySearchTree(value);
      }
      else {
        this.left.insert(value);
      }
    }
    else if (value > this.value) {

      if (this.right === null) {
        this.right = new BinarySearchTree(value);
      }

      else {
        this.right.insert(value);
      }
    } else {

    }
  }

  contains(value) {

    if (value === this.value) {
      return true;
    }

    if (value < this.value) {
      return !!(this.left && this.left.contains(value));
    }

    if (value > this.value) {
      return !!(this.right && this.right.contains(value));
    }
  }

BST는 이런 코드 구조를 가지게 된다.

contains를 구현하는 부분에서 이해가 안간다고 하는 부분을 설명하려다 보니 조금 더 제대로 뜯어보게 됐고,

아는것을 설명한다는게 정말 어려운 부분인 것을 다시 깨닫게 됐다.

우선 BST의 노드가 생성 될 때, left값과 right rmflrh value 값을 가지게 된다.

value의 값에 따라 생성되는 노드의 위치가 달라지게 되고 root보다 작으면 왼쪽에, 크다면 오른쪽에 배치된다.

노드의 value를 포함하는지 여부를 알 수 있는 contains 함수 같은 경우에는, 인자로 들어간 value 값과 현재 노드의 value 값이 같다면 true를 리턴하게 되고, 아니라면 value 값에 따라 자식 노드를 탐색한다.

value가 현재 노드의 value 보다 작다면 왼쪽을 탐색하고, 반대의 경우라면 오른쪽을 탐색하게 되는데

예를 들어 1-10까지 빠짐없이 있는 트리에 root 노드의 value가 5라면 1-4는 왼쪽에, 6-10은 오른쪽에 위치할 것이다. 찾는 value 가 2라면 root의 왼쪽 노드로 내려가게 되고, 여기에서 조건이 맞지 않는다면 root의 왼쪽 노드에서 재귀를 돌며 2를 탐색한다.