JavaScript에서 기본 이진 검색 트리 구현

데이터 구조와 관련하여 Binary Search Tree만큼 많은 평판이 선행되는 경우는 거의 없습니다.

직장에서 자주 등장하지 않을 수도 있지만 BST가 어떻게 작동하고 어떻게 구축되는지 이해하는 것은 기술 인터뷰를 이해하고 재귀의 더 깊은 측면을 이해하는 데 중요한 기초입니다.

이진 검색 트리란 무엇입니까?

이진 검색 트리는 각 노드에 최대 두 개의 자식이 있는 데이터 구조인 일반Binary Tree의 변형입니다. 이진 탐색 트리를 일반 이진 트리와 구별하는 점은 각 왼쪽 노드의 값이 상위 노드보다 작은 반면 각 오른쪽 노드의 값은 상위 노드보다 크다는 것입니다.

다음은 시각화된 예입니다.

        10
      /    \
     8     12
    / \   /  \
   4   9 11  15

보시다시피, 이것은 올바른 위치에서 더 작은 값과 더 큰 값의 규칙을 충족하기 때문에 유효한 이진 검색 트리입니다.

어떻게 만들까요?

물어봐주셔서 기뻐요! 현대 JavaScript에서 하나를 구축하는 단계를 함께 살펴보겠습니다.

우리는 ES6 클래스 구문을 사용하여 BST를 구축할 것이며 실제로 한 클래스 내에서 모두 수행할 수 있습니다!

먼저 선언하고 동시에 생성자를 작성해 보겠습니다.

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

생성자에 넣은 것은 트리에 있는 각 노드의 실제 데이터에 필요한 모든 것입니다. 노드에는 자체 데이터가 있고 인수로 전달되며 왼쪽 노드와 오른쪽 노드가 있으며 둘 다 기본적으로 null로 설정되어 있습니다. 쉬운!

이제 트리에 새 노드를 삽입하는 클래스 메서드를 작성해 보겠습니다. 이 방법이 주어진 데이터를 현재 노드의 왼쪽 및 오른쪽 값과 비교하고 노드에서 기존 트리 아래로 제대로 작동하는지 확인해야 합니다.

다음과 같이 두 부분으로 할 수 있습니다.

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

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    }

    if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }
}

기본적으로 이것은 오른쪽과 왼쪽 모두에서 동일한 작업을 수행합니다.

전달된 데이터가 현재 노드의 데이터보다 작거나 큰지 확인한 다음 현재 노드에 대해 왼쪽 또는 오른쪽 노드가 이미 존재하는지 확인합니다.

그렇지 않은 경우 이 데이터를 적절한 위치에 새 노드로 삽입합니다. 이미 노드가 있는 경우 이동하는 방향에 따라 왼쪽 또는 오른쪽 노드에서 insert 메서드를 다시 호출합니다. 이는 해당 자식 노드에서 아래 프로세스를 반복합니다.

이진 검색 트리를 구축하는 측면에서 이제 기본적으로 완료되었습니다. 야!

한 단계 더 나아가 BST에 특정 값이 포함되어 있는지 확인하는 방법을 하나 더 구현해 보겠습니다.

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

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    }

    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;
    }

    if (data < this.data && this.left) {
      return this.left.contains(data);
    } else if (data > this.data && this.right) {
      return this.right.contains(data);
    } else {
      return null;
    }
  }
}

위에서 삽입 방법으로 수행한 것과 본질적으로 동일한 작업을 여기서 수행합니다.

주어진 데이터를 현재 노드의 데이터와 비교하여 그보다 작거나 큰지 확인하고 왼쪽 또는 오른쪽 노드가 있으면 동일한 포함 메서드를 호출하여 데이터와 자식을 확인합니다.

값이 현재 데이터보다 작거나 크고 왼쪽 또는 오른쪽 자식 노드가 각각 존재하지 않으면 값이 트리에 존재하지 않는다는 것을 알고 null을 반환합니다.

이 방법의 핵심 측면은 "기본 사례"또는 함수의 처음 세 줄입니다. 이것은 현재 노드의 데이터가 우리가 찾고 있는 값과 같은지 확인하고, 그렇다면 일치하는 것을 찾았습니다! 해당 노드 또는 적중을 확인하기 위해 선택한 다른 값을 반환할 수 있습니다.


그리고 당신은 그것을 가지고 있습니다! JavaScript로 간단하고 기능적인 이진 검색 트리를 공식적으로 구축했습니다. BST와 관련된 다른 인터뷰 질문에 대해 좀 더 자세히 설명하는 이후 블로그 게시물에서 BST의 몇 가지 추가 기능을 탐색할 것입니다.

여기까지 읽으셨다면 시간 내주셔서 감사합니다. 도움이 되었길 바랍니다! :)