[ 비선형 자료구조 ] 트리

트리

1. 개념

  트리는 그래프의 한 종류로서 각 노드가 특정 값을 저장하고 하나 이상의 자식 노드에 대한 참조값을 가지고 있는 자료구조이다. 트리를 구성하는 노드들은 계층구조로 이루어져있으며 최상위 노드를 root라 한다. 트리는 일반적으로 파일 시스템, 데이터 베이스, 의사결정 알고리즘 등에서 사용된다.

 

2. 용어

• root : 부모 노드가 존재하지 않는 노드, 최상위 노드 (A)
• node : 데이터와 다음 노드에 대한 주소값을 저장한 자료구조
• leaf : 자식노드가 존재하지 않는 노드, 최하위 노드 (H, I, E, J, K, L)
• parent : 하나 이상의 자식 노드를 가진 노드 (A, B, C, D, F, G)
• child : 다른 노드의 자손인 노드 (B, C, D, E, F, G, H, I, J, K, L)
• sibling : 같은 부모 노드를 공유하는 노드 (H, I / J, K / D, E / ...)
• ancestor : root에 가까운 노드
• descendant : leaf에 가까운 노드
• subtree : 특정 노드에 연결된 하위 노드 그룹 ([B, D, E, H, I], [F, J, K], ...)
• depth : root로 부터의 거리
• width : 같은 레벨의 노드 수
• height : 트리의 depth 중 최대값
• degree : 각 노드의 branch의 수
• distance : 두 노드의 최단경로의 간선 수
• BFS / DFS : 너비 우선 탐색 / 깊이 우선 탐색 
• in-order / pre-order / post-order traversal : 트리에서 노드를 순회하는 세 가지의 방법

 

3. 특징

• 데이터 탐색에 있어 빠른 속도를 보인다.
• 계층구조를 갖는 자료구조이다.
• 하나의 root 노드를 갖는다.
• 각 노드는 0개 이상의 자식 노드를 갖는다.
• 모든 자식 노드는 하나의 부모노드를 갖는다.
• n개의 노드로 이루어진 트리는 항상 n-1개의 간선을 갖는다.
• self-loop가 존재하지 않는다.
• 트리는 내부에 또다른 트리가 존재하는 재귀적 자료구조이다.
• 무방향 그래프이며, 루프를 가지지 않는다.

 

 

4. 종류

1) Binary tree

  이진 트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리이다. 

 

 

(1) complete binary tree (완전 이진 트리)

 

  트리의 마지막을 제외한 각 레벨이 전부 채워진 트리. 따라서 leaf는 전부 같은 레벨에 해당한다.(마지막 레벨의 경우 좌측부터 채워지며, 전부 채워지지 않을 수 있다.)

 

 

(2) full binary three / strictly binary tree (전 이진 트리)

 

  모든 노드가 0개 혹은 2개의 자식 노드를 가지는 트리

 

 

(3) perfect binary tree (포화 이진 트리)

 

  full binary tree, complete binary tree 두 특성을 모두 가진 트리

 

 

(4)  skewed binary tree (편향 이진 트리)

같은 높이의 이진 트리 중 최소의 노드를 가지며 한 방향으로 치우친 서브 트리만을 가지는 이진트리

 

 

(5) heap (힙)

최소 힙 예씨

  부모 자식 간의 대소관계만 정의되어 있는 이진 트리이다. 부모 노드의 값이 자식 노드의 값보다 항상 큰 경우 최대 힙, 그 반대로 항상 작은 경우 최소 힙이라 한다.

 

2) binary search tree (BST)

 

  이진 탐색트리는 정렬된 이진 트리이다. 왼쪽 자식 노드는 부모의 값보다 작으며 오른쪽 자식 노드는 부모의 값보다 큰 값을 가진다.각 노드의 값이 중복되지 않는며, 이러한 이진 탐색 트리는 트리의 특정 노드의 위치를 알아내는 연산에 최적화 되어있다. 저장 및 탐색에 필요한 시간이 O(log n)로 효율적이나 이는 트리가 균형잡혀 있을때이고 균형이 무너져 편향 이진트리와 같은 구조를 가지게 되면 저장, 탐색 등의 작업에 필요한 시간이 O(n) 만큼 증가할 수 있다.

 

3) self-balancing BST (자가 균형 이진 탐색 트리)

 기존 BST의 경우 트리의 균형이 무녀졌을 시 탐색과 저장에 필요한 시간이 O(n) 만큼 증가할 수 있다는 문제점을 갖는다. 이를 극복하기 위해 등장한 것이 자가 균형 이진 탐색 트리이다. 대표적으로 AVL tree, Red-Black tree가 있으며, AVL tree가 보다 엄격하게 균형을 유지한다.

 

 

(1) Red-black tree

  Red-black tree는 자가 균형 이진 탐색 트리의 한 종류이다. rb트리는 각 노드에 특정 색을 적용하며, 트리의 균형을 위해 노드 배치에 제약을 둔다. 그 결과 삽입, 삭제 등과 같은 작업에 필요한 시간이 O(log n)으로 효율적이다.

• 각 노드는 빨간색 혹은 검은색이다.
• root 노드는 검은색이다.
• leaf 노드는 검은색 이다.
• 부모 노드가 빨간색이면 자식 노드는 모두 검은색이다.
• 각 노드에서 리프까지의 단순 경로에 포함된 검은색 노드의 수는 동일하다.
• 삽입되는 새로운 노드는 항상 빨간색으로 삽입되며, 연속된 빨간색이 발생했을 경우 restructuring 혹은 recoloring을 통해 색조정을 한다.

자세한 설명은 아래 글을 참고하자!

알고리즘 ) Red-Black Tree

 

 

 

(2) AVL tree

  AVL 트리는 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 최대 1만큼 차이를 가지도록 재구성된 트리이다. 그 결과 어떤 노드를 탐색하더라도 O(log n)에 탐색가능하다.

• 왼쪽 자식 노드를 루트 노드로 하는 서브트리와 오른쪽 자식 노드를 루트 노드로 하는 서브트리의 높이 차이가 최대 1이다.
• 높이 차이가 1 보다 커질 시 rotation을 통해 높이차이를 줄여 트리의 균형을 맞춘다.
• 특정 노드에 대한 탐색, 삽입 등의 연산에 필요한 시간이 O(log n)으로 효율적이다.

자세한 설명은 아래 글을 참고하자!

[자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터

 

4) M-way Search Tree (MST : 다원 탐색 트리)

  각 노드에 최대 m 개의 자식이 있는 탐색 트리의 한 유형이다. 트리구조가 균형을 유지한다는 부분은 균형 이진 트리와 유사하나, 각 노드의 데이터가 한개가 아닌 여러개를 가질 수 있으며, 자식 노드의 수가 제한되지 않는다는 점에서 차이를 가진다. 파일 시스템과 데이터 베이스를 구현하는 데 주로 사용되며 B-tree, B+tree 등의 자료구조에서 일반적으로 사용된다.

• k개의 자식 노드를 가지는 노드는 k-1개의 요소를 갖는다.
• 각 노드 않의 요소는 오름차순으로 정렬된다.
• i 번째 요소 <= i번째 서브트리의 모든 요소 <= i+1번째 요소

 

(1) B-tree

 B-tree는 파일 시스템과 데이터 베이스를 구현하는데 주로 사용되는 m-way 탐색 트리의 한 유형이다. m-way 탐색 트리의 차수가 늘어나면 점차 비효율적으로 바뀌게 되는데, 이를 극복하기 위해 등장한 것이 b-tree이다. 

• root, leaf 노드를 제외한 각 노드의 하위 트리의 개수는 m/2 ~ m개이다.
• 노드의 키 값(요소)의 개수는 (m / 2 - 1) ~ (m - 1) 개이다.
• root 노드는 최소 두개의 하위 트리를 갖는다.
• 모든 leaf 노드는 같은 레벨에 위치한다.
• 탐색은 매우 빠르나 순회가 어렵다.

 

(2) B+tree

  b-tree의 경우 순회가 어렵다는 단점이 있다. b+tree는 이러한 문제점을 해결하기 위해 색인을 이용한다. 이 자료구조는 B-tree의 특징을 갖지만 모든 데이터가 leaf 노드에 정렬되어 있다. 이때, leaf노드는 연결 리스트의 형태로 서로 연결되어 있으며, 이를 순차집합이라 한다.

 

 

(3) B*tree

  b-tree에서 구조 유지를 위해 수행되는 새로운 노드의 생성이나 연산을 최소화 하기 위해 최소 자식 노드 수를 2M/3으로 늘리고 노드의 증가에 따라 분열이 아닌 형제 노드로의 재배치를 실행한다.

 

4) Trie tree

  문자열을 효율적으로 저장/탐색하기 위한 트리형태의 자료구조이다. 각 노드에 문자를 저장하며, 트리를 아래쪽으로 순회 시 그 결과가 특정 단어와 대응한다. 접두사를 빠르게 찾는데 효율적인 방식이며, 검색엔진의 자동완성 등에 사용된다.

 

5. 트리의 구현

1) binary tree

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

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

  add(data) {
    let newNode = new Node(data)

    if (this.root === null) this.root = newNode;
    else{
      let queue = [this.root];

      while (queue.length) {
        let current = queue.shift();

        if(current.left) {
          queue.push(current.left)
        } else {
          current.left = newNode;
          break;
        }

        if(current.right) {
          queue.push(current.right)
        } else {
          current.right = newNode;
          break;
        }
      }
    }
  }
}

 

2) Binary Search Tree (BST)

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

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

  insert(data) {
    let newNode = new Node(data);

    if (this.root === null) this.root = newNode;
    else{
      let current = this.root;

      while (true) {
        if (current.data === newNode.data) {
          console.log('Error : this value is already exist');
          return;
        }

        if (current.data > newNode.data) {
          if(current.left === null) {
            current.left = newNode;
            break;
          } else {
            current = current.left;
          }
        } else {
          if(current.right === null) {
            current.right = newNode;
            break
          } else {
            current = current.right;
          } 
        }
      }
    }
  }
}

 

5. 트리의 순회

 트리위 순회는 트리의 모든 노드를 방문하는 작업이다. 트리의 순회는 아래와 같이 세가지로 구분되며, 재귀적으로 구현된다. 자세한 사항은 다음 글에 정리하겠다.

 

1) pre-order traversal (전위 순회) / DFT (깊이 우선 순회)

root - 왼쪽 하위트리 전위 순회 - 오른쪽 하위트리 전위 순회

트리를 복사/생성할 때 주로 사용

 

2) in-order traversal (중위 순회) / symmetric traversal (대칭 순회)

왼쪽 하위트리 중위 순회 - root - 오른쪽 하위트리 중위 순회

오름차순, 내림차순으로 값을 가져올 때 사용

 

3) post-order traversal (후위 순회)

왼쪽 하위 트리후위 순회 - 오른쪽 하위 트리후위 순회 - root

트리를 삭제 할 때 주로 사용