트리(tree)란?

1. 트리(Tree)

여태까지 봤던 배열, 스택, 큐, 연결 리스트는 대부분 선형 구조이다. 즉 "앞 - 뒤"로 이어지는 구조였음
그런데 트리는 다르게, 계층적 관계를 표현하는 비선형 자료구조이다. 예를 들면 폴더 구조, 조직도, 가족관계, HTML DOM 구조 같은 것을 표현할 때 트리가 잘 맞는다. 트리는 노드와 간선으로 이루어지고, 보통 하나의 루트에서 아래로 가지가 뻗는 형태로 설명된다.

 

2. 트리는 왜 필요할까?

학생 명단을 저장하는 건 배열로도 가능하다.
하지만 "학과장 아래 교수들, 교수 아래 조교들, 조교 아래 학생들" 처럼 상하관계가 있으면 배열은 불편하다.
연결 리스트도 한 줄로만 이어지기 때문에 "누가 누구 밑에 있는가"를 표현하기엔 한계가 있다.
트리는 바로 이런 부모-자식 관계, 즉 계층 구조를 표현하려고 쓰는 자료구조이다.

 

3. 트리의 가장 중요한 구성요소

            A
          / | \
        B   C  D
      / \   |
     E   F  G

여기서

• A : 루트 노드(root node)
• B, C, D : A의 자식 노드(child)
• A : B, C, D의 부모 노드(parent)
• E, F : B의 자식
• E, F, G, C : 자식이 없으면 리프 노드(leaf node, 단말 노드)

트리는 일반적으로 이런 용어들을 사용해 설명한다 : 루트, 부모, 자식, 형제, 리프, 서브트리, 레벨, 높이. 이런 용어들이 트리 이해의 기본

[그림1] 트리의 구조

4. 핵심 용어

• 루트(root)
  트리의 맨 위에 있는 시작점
  부모가 없는 유일한 노드다. 보통 트리는 하나의 루트를 가진다고 설명한다.
  
  
• 부모(parent) / 자식(child)
  A 밑에 B가 있으면, A는 B의 부모, B는 A의 자식이다. 이 관계가 트리의 핵심
  
  
• 형제(sibling)
  같은 부모를 가지는 노드들, 예를 들어 B, C, D는 형제다.
  
  
• 리프(leaf)
  자식이 하나도 없는 노드. 말단 노드라고도 불른다. E, F, C, G 같은 애들이다.
  
  
• 서브트리(subtree)
  트리 안의 작은 트리라고 생각하면 된다. 예를 들어, B를 루트로 보고 E, F를 포함하면 그 자체가 하나의 서브트리가 된다.
  
  
• 레벨(level)
  층 수 라고 생각하면 쉽다. A가 0level, 그 아래가 한 단계씩 내려간다. 교재마다 루트를 0으로 보기도 하고 1로 보기도 해서 기준만 일관되면 된다.
  
  
• 높이(height)
  트리의 최대 깊이. 루트에서 가장 깊은 리프까지 몇 단계 내려가는지 보는 개념이다.
  
  
• 링크(Link, Edge)
  트리를 구성하는 노드와 노드 사이를 연결하는 선(Line)

5. 트리의 특징

트리는 "사이클이 없는 연결 구조다"
즉, 아래로 내려가다가 다시 자기 자신으로 돌아오는 고리가 없다.
그래서 계층 구조를 표현하기 좋다. 일반적인 설명에서는 트리를 사이클이 없는 연결 그래프의 한 종류로 보기도 한다.

 

그리고, 보통 한 노드는 부모를 하나만 가진다.
자식은 여러 명일 수 있지만, 부모는 하나라는 게 포인트이다. 그래야 "상하관계"가 깔끔하게 유지된다.

 

6. 선형 구조와 비교

배열 / 연결 리스트

• 앞뒤 순서 표현에는 좋다.
• 계층 구조 표현은 불편하다.

트리

• 상하 관계 표현에 강하다
• 탐색 방향이 여러 갈래로 갈 수 있다.
• 비선형 구조이다.

즉, 배열은 "줄 세우기", 트리는 "조직도 만들기"라고 생각하면 된다.

 

7.예시로 이해하기

• 폴더 구조
  C:
  │─ Users
  │   ├─ CAT
  │   └─ Public
  └─ Program Files
  완전한 트리 구조를 가진 형태이다. 상위 폴더 밑에 하위 폴더, 그 밑에 파일이나 폴더가 또 생긴다.
  실제로 트리는 디렉터리 구조를 설명할 때 대표적으로 등장한다.
  
  
• 조직도
  대표 → 팀장 → 팀원 이것도 트리이다.
  
  
• HTML 문서 구조
  html 아래 head, body 그 아래 div, p , span 이런 것도 트리 구조로 볼 수 있다. 즉, 트리는 컴퓨터 안에서 엄청 자주 나온다.
  
  

8. 마무리 정리

트리(Tree)는 노드와 간선으로 이루어진 비선형 자료구조이며, 부모-자식 관계를 통해 계층적인 데이터를 표현하는 데 적합하다. 루트, 부모, 자식, 형제, 리프, 서브트리, 레벨, 높이 같은 기본 용어를 정확히 이해하는 것이 중요하고, 폴더 구조나 조직도처럼 상하 관계가 있는 데이터를 다룰 때 매우 유용하다. 또한 트리는 사이클이 없고, 일반적으로 각 노드는 하나의 부모만 가진다는 특징을 가진다.