[JS] 트리와 이진 탐색 트리

 

트리 Tree

트리는 항상 루트(root)에서부터 시작된다. 루트는 자식(child) 노드를 가지며, 간선(edge)으로 연결되어 있다. 자식 노드의 개수는 차수(degree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다. 높이(height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리(subtree) 구성을 띤다. 레벨(level)은 0부터 시작한다. 논문에 따라 1부터 시작하는 경우도 있으나, 0부터 시작하는 것이 좀 더 일반적이다. 트리는 항상 단방향(uni-directional)이기 때문에 간선의 화살표는 생략 가능하다. 그림에서도 마찬가지로 생략해서 표현했고 일반적으로 방향은 위에서 아래로 향한다.

 

이진 트리  Binary Tree

부모 노드 밑의 자식 노드 개수를 최대 2개

 

이진 탐색 트리 Binary Search Tree

데이터 정렬에 특화된 트리 

부모 노드 왼쪽에 있는 모든 자식 노드는 언제나 부모보다 작고 오른쪽 자식 노드는 크다

자식노드는 최대 2개

 

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(val) {
    let newNode = new Node(val);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while (true) {
        if (val === current.val) return undefined;
        //입력 데이터가 루트 데이터보다 작으면
        if (val < current.val) {
        //루트노드 왼쪽이 비어있으면 삽입
          if (current.left === null) {
            current.left = newNode;
            return this;
            //루트왼쪽이 존재하면 기준노드 이동
          } else {
            current = current.left;
          }
          //입력 데이터가 루트 데이터보다 크면
        } else if (val > current.val) {
        //루트노드 오른쪽 비어있으면 삽입
          if (current.right === null) {
            current.right = newNode;
            return this;
          } else {
          //루트 오른쪽 존재하면 기준노드 오른쪽으로 이동
            current = current.right;
          }
        }
      }
    }
  }


  contains(val) {
    if (this.root === null) return false;
    let current = this.root;
    let found = false;
    while (current && !found) {
      if (val < current.val) {
        current = current.left;
      } else if (val > current.val) {
        current = current.right;
      } else {
        return true;
      }
    }
    return false;
  }
}

이진탐색트리의 빅오

삽입 - O(log n)

탐색 - O(log n)

 

하지만 위 이미지와 같이 한 쪽으로 쏠린 이진탐색트리에서 데이터를 삽입했을 때에는, O(logn)이 아니라 O(n)의 시간복잡도를 갖게 된다. 이런 경우에는 이진 트리나 이진탐색트리를 사용하지 않고 연결리스트 같은 다른 자료구조를 사용하는 것이 적절하다.