트리 (Tree) - 트리와 이진트리

좌측 : 트리 / 우측 : 이진 트리 from geeksforgeeks

트리 (Tree)

• 정의: 트리는 하나의 루트 노드에서 시작하여 자식 노드로 확장되는 계층적 구조입니다. 각 노드는 자식 노드를 가질 수 있으며, 각 자식 노드는 다시 자신의 자식 노드를 가질 수 있습니다.
• 트리에 관련 용어:
  • 루트 노드: 트리의 최상위 노드.
  • 터미널 노드 (리프 노드): 자식 노드가 없는 말단 노드.
  • 인터널 노드: 하나 이상의 자식 노드를 가진 내부 노드.
  • 서브 트리: 특정 노드를 루트로 하는 부분 트리.
  • 에지: 두 노드를 연결하는 선.
• 특징:
  • 루트 노드에서 시작
  • 각 노드는 하나의 부모 노드와 0개 이상의 자식 노드를 가짐
  • 사이클이 없음
    • 트리는 비순환 그래프.
    • 이는 트리 안에서 어떤 노드에서 출발하여 다시 그 노드로 돌아오는 경로가 없음을 의미.
  • 트리에서 각 노드의 레벨은 해당 노드의 깊이를 나타내는 지표로 사용
    • 노드의 레벨은 해당 노드까지 도달하기 위해 거쳐야 하는 간선(에지)의 수에 1을 더한 값
    • 이 개념은 트리 구조에서 노드의 위치를 명확히 정의하고, 트리의 깊이(depth)와 높이(height)를 계산하는 데 중요한 역할을 합니다.

• 장점:
  • 계층적 데이터 표현에 적합
  • 탐색, 삽입, 삭제 작업이 효율적
• 단점:
  • 균형이 맞지 않으면 성능 저하
  • 특정 작업에 대한 최악의 경우 시간 복잡도가 높을 수 있음

자바스크립트 예시

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(child) {
    this.children.push(child);
  }
}

 

이진 트리 (Binary Tree)

• 정의: 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분됩니다.
• 특징:
  • 각 노드는 최대 두 개의 자식 노드를 가짐
  • 균형 잡힌 이진 트리 (Balanced Binary Tree)와 불균형 이진 트리 (Unbalanced Binary Tree)로 나뉨
• 장점:
  • 탐색, 삽입, 삭제 작업이 효율적
  • 균형 잡힌 이진 트리의 경우 높은 성능
• 단점:
  • 불균형 이진 트리의 경우 성능 저하
  • 트리의 균형을 유지하기 위한 추가 작업 필요

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insertLeft(child) {
    this.left = child;
  }

  insertRight(child) {
    this.right = child;
  }
}

 

포화 이진 트리 

• 포화 이진 트리는 모든 노드가 정확히 두 개의 자식 노드를 가지며, 모든 리프 노드가 동일한 레벨에 위치한 이진 트리입니다.
• 이는 항상 균형 잡힌 구조로, 탐색, 삽입, 삭제 작업에서 효율적입니다.
• 높이가 h인 포화 이진 트리의 총 노드 수는 2^h - 1입니다.

완전 이진 트리

• 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에서는 노드가 왼쪽에서 오른쪽으로 채워지는 이진 트리입니다.
• 이는 탐색, 삽입, 삭제 작업에서 효율적입니다.
• 배열로 구현할 경우 노드 간의 빠른 접근이 가능합니다.
• 트리의 높이는 log(n)에 비례하여 성능이 좋습니다.

       A
     /   \
    B     C
   / \   /
  D     F
  
  // 좌측 오른쪽이 채워지기전 우측 노드가 있는 경우 완전 이진 트리가 될 수 없음

 

트리 & 이진트리 시간복잡도

작업일반	트리	이진 트리 (Binary Tree)	균형 잡힌 이진 트리 (AVL, Red-Black Tree 등)
탐색	O(n)	O(n)	O(log n)
삽입	O(n)	O(n)	O(log n)
삭제	O(n)	O(n)	O(log n)

 

요약

• 자식이 두 개 이하면 = 이진트리
• 이진 트리에 왼쪽부터 채워지면 = 완전 이진 트리
• 이진 트리의 최대 레벨까지 꽉 차 있으면 = 포화 이진 트리