[자료구조] Tree

1. Tree

• 사이클이 없는 연결/양방향 그래프
• ✅ 어떤 두 노드를 선택해도 경로는 항상 단 하나만 존재 (오직 하나의 부모를 가지며, 경로에서 바로 이전 노드가 부모가 됨)
• ✅ 계층형 구조 (여러 개의 하위 노드로 분기됨)

 

용어

         A (Root, Depth: 0, Height: 2, Level: 1)
       /   \
      /     \
     B       C (Node, Depth: 1, Height: 1, Level: 2)
    / \     / \
   D   E   F   G (Leaf, Depth: 2, Height: 0, Level: 3)

용어	설명
Node	트리를 구성하는 기본 단위
Root	트리의 최상위 노드
Leaf	자식이 없는 노드
SubTree	특정 노드와 그 노드의 모든 자손 노드로 구성된 트리
Level	트리에서 같은 깊이의 노드들의 집합
Depth	루트 노드에서 특정 노드까지 도달하기 위한 엣지의 수
Height	특정 노드에서 가장 멀리 떨어진 리프 노드까지의 엣지의 수

 

2. 탐색

구분	너비 우선 탐색 (BFS)	깊이 우선 탐색 (DFS)
탐색 방식	가까운 노드부터 탐색	끝까지 깊게 탐색
진행 순서	현재 → 인접 노드 전체 → 다음 단계	한 방향으로 끝까지 → 되돌아옴
구현 방식	반복문 + Queue	재귀 or Stack
특징	레벨(거리) 순 탐색	경로 중심 탐색
사용 예	최단 경로, 레벨 탐색	트리, 백트래킹, 경로 탐색
시간 복잡도	O(V + E)	O(V + E)

 

3. 순회

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

구분	전위 순회 (Preorder)	중위 순회 (Inorder)	후위 순회 (Postorder)
순서 공식	Root → Left → Right	Left → Root → Right	Left → Right → Root
특징	구조를 빠르게 파악	정렬된 결과 (BST)	자식 먼저 처리
활용	트리 복사, 표현식	이진 탐색 트리 정렬	삭제, 계산(후위식)
예시 결과	A → B → D → E → C → F → G	D → B → E → A → F → C → G	D → E → B → F → G → C → A

 

3. 종류

이진 트리

• 각 노드가 최대 두 개의 자식노드를 가지는 트리입니다.

구분	포화 이진 트리 (Perfect)	완전 이진 트리 (Complete)	균형 이진 트리 (Balanced)
핵심 정의	모든 레벨이 꽉 찬 트리	마지막 레벨만 덜 찰 수 있음	좌우 높이 차이가 크지 않음
노드 채움 상태	전부 100% 채워짐	왼쪽부터 순서대로 채움	구조 자유롭지만 균형 유지
높이 균형	완벽하게 균형	대부분 균형	균형 유지가 핵심
특징	가장 이상적인 트리	실전에서 가장 많이 사용	탐색 효율을 위한 구조
노드 수 공식	2^h - 1	일정하지 않음	일정하지 않음

 

예시) 포화 이진 트리

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

 

예시) 완전 이진 트리

    A
   / \
  B   C
 / \ / 
D  E F

 

예시) 균형 이진 트리

    A
   / \
  B   C
 /     \
D       E

 

다진트리

• 각 노드가 세 개의 이상의 자식노드를 가지는 트리입니다.

 

4. 사례

사례	설명	예시
DOM	웹 페이지의 구조를 표현하는데 사용되는 트리	HTML, XML 등에서 사용됩니다.
AST	프로그램의 구조를 표현하기 위한 트리.	컴파일러나 인터프리터에서 소스코드를 분석할 때 사용
Search Tree	효율적인 검색, 삽입, 삭제 연산을 지원하기 위한 트리

 

 

 

출처

• Wiki - Tree