이진 탐색 트리(Binary Search Trees)

References

아래 링크의 강의 중 Section 27. My Best Friend, Binary Search Trees의 내용을 추려 이번 글을 작성하였습니다.
The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Binary Search Trees

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    // 입력값 data가 this.data보다 작고 this.left에 값이 이미 할당되어 있다면 this.left에 입력값 data을 넣고, this.left가 없는데 입력값 data가 this.data보다 작다면 this.left에 새로운 node를 할당한다. 입력값의 대소비교만을 빼고 this.right의 경우도 마찬가지이다.
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    } else if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }

  contains(data) {
    if (this.data === data) {
      return this;
    }
    // 입력값 data가 현재값 this.data보다 크고 this.right에 node가 존재한다면?
    if (this.data < data && this.right) {
      return this.right.contains(data);
    } else if (this.data > data && this.left) {
      return this.left.contains(data);
    }

    return null;
  }
}

binary search trees란 root값을 기준으로 새로 입력하는 값이 작으면 왼쪽, 크다면 오른쪽으로 정렬해놓은 트리이다.