data_structure 컴퓨터구조 computer_science cs 자료구조 트리 tree

[CS/Computer Science][자료구조/Data Structure] 트리

Kwangjin Park

Mar 20, 2025 · 7 min read

Follow

이어서, 이번에는 트리에 대해 알아보겠습니다.

1. 트리

  • 주로 계층 구조 표현을 위한 자료구조
  • 트리의 구성
    • 노드(node): 데이터가 저장된 곳
    • 간선(edge): 노드와 노드 간을 연결(=링크)
      • 간선으로 연결된 노드는 상하 관계를 형 image1
  • 노드의 종류
    • 부모노드(parent node): 이웃한 노드 간 형성된 상하 관계에서, 상위에 위치한 노드
    • 자식노드(child node): 이웃한 노드 간 형성된 상하 관계에서, 하위에 위치한 노드 image2
      • 노드는 하나 이상의 자식 노드를 가질 수 있음
      • 부모 노드는 하나만 있을 수 있음(최상단 노드 제외)

    • 형제 노드(sibling node): 같은 부모 노드를 공유하는 노드
    • 조상 노드(ancestor node): 부모 노드와 그 부모 노드들
    • 자손 노드(descendant node): 자식 노드와 그 자식 노드들

    • 루트 노드(root node): 부모 노드가 없는 최상단 노드
    • 리프 노드(leaf node): 뻗어 나가는 트리의 최하단 끝에 위치한 노드(더 이상 자식 노드가 없는 최하단 노드) image3

  • 이외 트리와 관련된 개념
    • 차수(degree): 각 노드가 가지는 자식 노드의 수
    • 레벨(level): “루트 노드 → 특정 노드”에 이르기까지 거치게 되는 간선의 수
      • 깊이와 같은 개념 → “특정 노드가 얼마나 깊은 곳에 있는지”
    • 높이(height): 트리의 가장 높은 레벨 image4
    • 서브 트리(sub tree): 트리 안에 포함되어 있는 부분트리
  • 트리의 구현 및 저장

    • 하나의 노드를 "데이터를 저장한 공간"과 "자식노드의 위치 정보(메모리 상의 주소)를 저장한 공간 모음"으로 간주 image5

      image6

2. 트리의 순회

  • 트리의 “순회”: 트리의 노드를 모두 한 번씩 방문하는 것
  • 3가지 대표적인 순회 방법
    1. 전위 순회
    2. 중위 순회
    3. 후위 순회 image7

전위 순회(preorder traversal)

  • “루트 노드 → 왼쪽 서브트리 (전위)순회 → 오른쪽 서브트리 (전위)순회” 순서
  • 위의 예시 트리를 놓고 볼 때, '중 → 좌 → 우'의 순서대로 순회
  • ex) 아래의 트리를 전위 순회한다고 하면, image8
    1. 루트 노드 순회(노드 a)
    2. 왼쪽 서브트리 전위 순회(루트 노드가 b인 트리)
      • 서브 트리 b 안에서도, 전위 순회 실시
      • 루트 노드 b → 루트 노드가 d인 왼쪽 서브트리 → 루트 노드가 e인 오른쪽 서브트리
    3. 왼쪽 서브트리에 대한 전위 순회를 마치면, 오른쪽 서브트리에 대한 전위 순회(루트 노트가 c인 트리)
  • 전위 순회를 표현한 의사 코드(psuedo code) image9

중위 순회(inorder traversal)

  • “왼쪽 서브트리 (중위) 순회 → 루트 노드 → 오른쪽 서브트리 (중위) 순회” 순서
  • '좌 → 중 → 우' 의 순서로 순회
  • ex) 아래의 트리를 중위 순회한다고 하면, image10
    1. 왼쪽 서브트리 중위 순회(루트 노드가 b인 트리)
      • 서브 트리 b 안에서도, 중위 순회 실시
      • 루트 노드가 d인 왼쪽 서브트리 → 루트 노드 b → 루트 노드가 e인 오른쪽 서브트리
    2. 루트 노드 순회(노드 a)
    3. 오른쪽 서브트리에 대한 중위 순회(루트 노트가 c인 트리)
  • 중위 순회를 표현한 의사 코드(psuedo code) image11

후위 순회(postorder traversal)

  • “왼쪽 서브트리 (후위) 순회 → 오른쪽 서브트리 (후위) 순회 → 루트 노드”
  • '좌 → 우→ 중' 의 순서로 순회
  • ex) 아래의 트리를 후위 순회한다고 하면, image12
    1. 왼쪽 서브트리 후위 순회(루트 노드가 b인 트리)
      • 서브 트리 b 안에서도, 후위 순회 실시
      • 루트 노드가 d인 왼쪽 서브트리 → 루트 노드가 e인 오른쪽 서브트리 → 루트 노드 b
    2. 오른쪽 서브트리에 대한 후위 순회(루트 노트가 c인 트리)
    3. 루트 노드 순회(노드 a)
  • 후위 순회를 표현한 의사 코드(psuedo code) image13

레벨 순서 순회

  • 레벨의 순서대로 노드를 순회하는 방법
  • 가장 낮은 레벨부터 차례로 노드 순
  • ex) 아래 트리를 레벨 순서로 순회한다면, image14

3. 트리의 종류

  • 상황 및 장단점에 따라 다양한 상황에서 다양한 트리 활용

    이진 트리(binary tree)

  • 자식 노드의 갯수가 2개 이하인 트리
  • 가장 대중적인 트리 중 하나 image15
  • 이진 트리의 종류
    1. 편향된 이진 트리(skewed binary tree)
      • 모든 자식 노드가 한 쪽으로 치우친 이진 트리 image16
    2. 정 이진 트리(full binary tree)
      • 자식 노드의 개수가 1개가 아닌 이진 트리
      • 즉, 정 이진 트리의 자식노드의 갯수는 0개 혹은 2개 image17
    3. 포화 이진 트리(perfect binary tree)
      • 다음 2가지 조건을 만족하는 이진 트리
        1. 리프 노드를 제외한 모든 노드들이 자식 노드를 2개씩 갖고 있음
        2. 모든 리프 노드의 레벨이 동일 image18
    4. 완전 이진 트리(complete binary tree)
      • 다음 2가지 조건을 만족하는 이진 트리
        1. 마지막 레벨을 제외한 모든 레벨이 2개의 자식 노드 가짐
        2. 마지막 레벨의 모든 노드들이 왼쪽부터 존재 image19

이진 탐색 트리와 힙: 탐색에 활용되는 트리

  • 탐색에 활용할 수 있는 특별한 이진 트리: 이진 탐색 트리 및 힙

    1. 이진 탐색 트리(BST, Binary Search Tree)
    • 임의의 노드가 있을 때, 아래의 두 가지 조건을 만족하는 이진 트리
      • 특정 노드의 왼쪽 트리: 해당 노드보다 작은 값 지님
      • 특정 노드의 오른쪽 트리: 해당 노드보다 큰 값 지님
    • 활용도
      • 이진 탐색 트리를 활용하면, $O(logn)$ 으로 원하는 값 탐색 가능
        1. 힙(heap)
    • 탐색에 특화된 또 다른 이진 트리
    • 최댓값 / 최솟값을 빠르게 찾기 위해 활용
    • Time Complexity: $O(logn)$
    • 힙의 종류
      1. 최대 힙
        • 부모 노드가 자식 노드의 값보다 큰 값으로 이루어진 이진 트리
      2. 최소 힙
        • 부모 노드가 자식 노드의 값보다 작은 값으로 이루어진 이진 트리 image20
    • 노드 간 크기 비교 → 값 뿐만 아니라 문자 간의 비교도 가능(원하는 우선 순위를 지정하여)
    • 최대 힙으로 우선순위 큐 구현 가능

RB 트리: 균형을 맞추는 트리

  • 자가 균형 이진 탐색 트리 → 이진 트리의 편향성 문제를 보완한 트리
    • 삽입과 삭제를 반복하는 과정에서, 트리가 한 쪽으로만 자라나는 편향된 트리가 될 수 있음
    • 편향된 트리가 된다면, Time Complexity가 $O(n)$이 됨 → 트리를 사용하는 의미가 없어짐
    • 해당 문제를 보완하여 탐색 성능을 언제나 균일하게 유지하기 위해 좌우 서브트리의 높이 차이를 최소화해주는 트리
  • 자가 균형 이진 탐색 트리(Self-balancing binary search tree)의 종류
    • AVL(Adelson-Velsky and Landis Tree) 트리
    • RB(Red Black) 트리

  • RB 트리?
    • 컴퓨터 과학 전반에 녹아있는 근원적 자료구조 중 하나
    • 모든 노드를 Red or Black으로 칠한 트리
    • 아래와 같은 규칙을 통해, 좌우 서브트리의 균형을 맞춤
      1. 루트 노드는 블랙 노드
      2. 리프 노드는 블랙 노드
      3. 레드 노드의 자식 노드는 블랙 노드
      4. “루트 노드 → 임의의 리프 노드” 경로 내에 있는 블랙 노드의 수는 같다.
    • RB 트리의 리프노드는 실질적 데이터가 저장되지 않은 노드 → NIL(Null Leaf) 노드
    • ex) 아래와 같은 RB 트리가 있을 때, image21
      • 루트 노드(0020) 및 리프노드(모든 NIL 노드)가 모두 블랙 노드 → 1,2번 조건 만족
      • 레드 노드의 자식 노드는 모두 블랙 노드 → 3번 조건 만족
      • 루트 노드에서 임의의 노드에 이르는 경로에 있는 블랙 노드의 수가 모두 동일 → 4번 조건 만족
      • 1-4번 조건 모두 만족 → 위 트리는 RB 트리
    • RB 트리의 새 노드 삽입(삭제 연산도 동일한 알고리즘)
      1. 삽입할 노드를 레드 노드로 간주하고 이진 탐색 트리와 동일하게 삽입 수행
      2. 삽입 이후에도 4개의 RB 트리 조건에 부합하도록
      3. 만약 부합하지 않는다면? → 부합할 때까지 트리를 회전하거나 색상 재지정
    • 트리의 회전
      • 양쪽 서브트리 높이의 균형을 맞추기 위해 부모 노드-자식 노드 관계를 재지정 하는 것
      • ex1) 아래 트리가 노드 R을 기준으로 왼쪽 회전했다면? image22
      • ex2) 아래 트리를 노드 L을 기준으로 오른쪽으로 회전했다면? image23

B 트리: 대용량 입출력을 위한 트리

  • B 트리는 이진 탐색 트리가 아닌, 다진 탐색 트리
    • 즉, 한 노드가 여러 자식 노드를 가질 수 있다는 의미
  • B 트리의 특징
    • B 트리는 한 노드가 가질 수 있는 자식 노드의 갯수가 최소/최대 갯수가 정해져 있음
      • M차 B 트리: 최대 자식 노드의 수가 M개인 B 트리
      • M차 B 트리가 가질 수 있는 최소 자식 노드의 갯수: 올림해서 M/2 개
    • B 트리의 각 노드는 하나 이상의 키 값이 존재하고, 각 키들이 오름차순으로 저장 image24
    • B 트리의 각 노드는 B 트리로 다룰 실질적 데이터의 위치도 포함할 수 있음
      • “키를 알면, 키에 대응하는 데이터를 알 수 있다”
    • 키가 N개인 노드가 가질 수 있는 자식 노드의 수는 반드시 N+1 개
    • B 트리의 모든 리프 노드는 깊이가 같음(편향된 형태 X)
  • B+ 트리: B 트리의 변형
    • 실제 파일 시스템이나 DB에 활용 시, 대체로 B 트리는 변형된 형태인 B+ 형태로 활용됨
    • B 트리와 B+ 트리의 차이점 2가지
      1. B+ 트리는 실질적 데이터가 모두 최하위 리프 노드에 위치
        • 리프노드가 아닌 노드는, 키/주소 등 자식 노드의 범위를 분할하는 용도로 사용되는 데이터를 저장
      2. 이러한 최하위 리프노드는 연결리스트의 형태를 띄고 있음
chat_bubble 0

chat_bubble 댓글남기기

댓글남기기