Udemy - 이진 검색 트리(Tree)

20.

생성일: 2022년 3월 9일 오후 7:28

이진 검색 트리

이진 검색 트리는 하나의 루트 노드에서 두 개의 엣지(브랜치)로 파생된 노드들이 줄기처럼 상하 구조로 구성된 자료구조다. 사실 글로만 봐서는 한 눈에 이해하기 모호하기 때문에 바로 그림으로 설명해보도록 하겠다.

이와 같이, 루트 노드를 기준으로 노드들이 상하관계로 구성된 자료구조인 것이다.

물론 이진 검색 트리가 되기 위한 조건들이 몇 개 존재한다.

이와 같은 조건들을 만족해야지만 이진 검색 트리가 될 수 있다.

이진 검색 트리를 활용하면 데이터를 정렬할 때 훨씬 더 효율적으로 정렬을 수행할 수 있다. 애초에 루트 노드에서부터 좌우로 숫자들이 갈라지기 때문에, 이전에 학습했던 분할 점령 탐색 방식과 동일하게 경우의 수를 계속 줄여 나가며 데이터를 탐색 및 정렬할 수 있기 때문이다.

---

활용 방법

그렇다면 이러한 이진 검색 트리를 어떻게 구현하고 활용할 수 있을까?

insert

우선, 특정 숫자를 트리 내에서 적절한 위치(대수 비교)에 insert하는 방식은 이하와 같다.

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

class BST {
  constructor() {
    this.root = null;
  }
  insert(val) {
    const newNode = new Node(val);
    // 루트가 없을 때는 root에 새로운 노드를 할당
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    // 만약 루트 노드가 존재한다면? -> tempNode를 루트노드로 설정
    let tempNode = this.root;
    while (true) {
      // 같은 값은 처리하지 않는다.
      if (val === tempNode.val) return undefined;
      // 만약 입력된 값이 tempNode의 값보다 크다면?
      if (val > tempNode.val) {
        // 그리고 만약 tempnode의 우측 노드가 비어있다면? -> right가 newNode의 자리가 된다.
        if (!tempNode.right) {
          tempNode.right = newNode;
          return this;
        }
        tempNode = tempNode.right;
      } else {
        if (!tempNode.left) {
          tempNode.left = newNode;
          return this;
        }
        tempNode = tempNode.left;
      }
    }
  }
}

find

그리고 특정 숫자를 검색하는 find 메소드 또한 이하와 같이 구현할 수 있다.

class BST {
  constructor() {
    this.root = null;
  }
  find(value) {
    if (this.root === null) return false;
    let currentNode = this.root;
    let found = false;
    while (currentNode && !found) {
      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        currentNode = currentNode.right;
      } else {
        found = true;
      }
    }
    if (!found) return undefined;
    return currentNode;
  }
}

---

이진 검색 트리의 시간 복잡도

메소드	시간 복잡도
insertion	O(nlogn)
searching	O(nlogn)

이진 검색 트리는 굉장히 훌륭한 시간 복잡도를 갖는다!

---