5. Tree (1)

Tree

list, queue, stack은 선형적인 자료구조. 그렇다면 계층적인 자료를 다루려면?

이럴 때 필요한게 바로 tree!

 

트리는 노드(node) 들이 간선(edge) 으로 연결된 계층적 자료구조

        A
       / \
      B   C
     / \   \
    D   E   F

 

 

노드(Node)	트리를 구성하는 각 원소
루트(Root)	트리의 가장 위에 있는 노드 (여기선 A)
부모(Parent)	어떤 노드를 직접 연결해 아래로 이어지는 노드 (B의 부모는 A)
자식(Child)	부모로부터 직접 연결된 하위 노드 (A의 자식은 B, C)
형제(Sibling)	같은 부모를 가진 노드 (B와 C는 형제)
리프(Leaf)	자식이 없는 노드 (D, E, F)
간선(Edge)	부모와 자식을 연결하는 선
레벨(Level)	루트로부터 얼마나 떨어져 있는지 (루트가 level 0)
높이(Height)	트리의 최대 레벨 값
서브트리(Subtree)	어떤 노드를 루트로 하는 하위 트리

---

1. Representation of Trees (트리의 표현 방식)

트리는 선형 구조가 아니라 비선형 구조이기 때문에 배열처럼 단순하게 저장하기 어렵다.
하지만 몇 가지 방법으로 표현할 수 있음.

 

 1) 부모 저장 방식 (Parent Array)

각 노드의 부모 인덱스를 저장하는 방법.

Index:  0  1  2  3  4  5
Node :  A  B  C  D  E  F
Parent: -1  0  0  1  1  2

• A의 부모는 없음(-1)
• B, C의 부모는 A
• D, E의 부모는 B
• F의 부모는 C

->  단순하지만 자식 찾기 어려움 (역참조 필요)

 

 2) 자식 리스트 방식 (Child List)

각 노드가 가진 자식 노드를 연결 리스트로 관리함.

typedef struct node {
    int data;
    struct node* child;
    struct node* sibling;
} TreeNode;

• 자식은 child로, 같은 레벨의 다른 형제는 sibling으로 연결.

->   트리의 형태를 가변적으로 표현 가능.

->  트리 구조 탐색에 용이.

---

2 Binary Tree (이진 트리)

모든 노드가 최대 두 개의 자식을 가지는 트리.
각 노드는 왼쪽 자식(left child) 과 오른쪽 자식(right child) 으로 구분됨.

        A
       / \
      B   C
     / \   \
    D   E   F

 

 

정이진 트리 (Full Binary Tree)	모든 노드가 0개 또는 2개의 자식을 가짐
완전 이진 트리 (Complete Binary Tree)	마지막 레벨을 제외하고 노드가 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워짐
포화 이진 트리 (Perfect Binary Tree)	모든 레벨이 꽉 차 있는 이진 트리
편향 이진 트리 (Skewed Binary Tree)	모든 노드가 한쪽 방향으로만 이어진 트리 (왼쪽 or 오른쪽)

 

A  /    |    \ B      C     D	A    \         B           \              C	A       B  \     /   C	A        / \       B   C        /  \     \        D    E     F
이진트리 X	이진트리 O	이진트리 X (그래프 형태)	이진트리 O
노드 A가 세 개의 자식(B, C, D) 을 가지고 있음.	편향 이진 트리	노드 C가 두 개의 부모(A, B) 를 가지고 있음.

 

 

 

 - Binary Tree ADT (추상 자료형)

이진 트리는 일반적으로 다음 연산들을 지원함:

createTree()	새 트리 생성
insertLeft(parent, child)	부모 노드의 왼쪽 자식으로 삽입
insertRight(parent, child)	부모 노드의 오른쪽 자식으로 삽입
deleteTree()	트리 전체 삭제
isEmpty()	트리가 비었는지 확인
traverse()	순회 (preorder, inorder, postorder)

 

이러한 연산들은 재귀적(recursive) 으로 구현되는 경우가 많음.

 - Binary Tree Representation (이진 트리의 표현)

이진 트리는 두 가지 대표적인 방법으로 표현할 수 있음.

 

 1) 배열 표현 (Array Representation)

트리를 완전 이진 트리 형태로 가정하고 배열로 저장.

인덱스 관계:	왼쪽 자식	오른쪽 자식	부모
	2 * i	2 * i  + 1	i / 2

 

예를들면

트리구조	인덱스 표현
A(1)        /       \   B(2)     C(3)   /      \         \ D(4) E(5)     F(6)	index:  1  2  3  4  5  6 value:  A  B  C  D  E  F

• 인덱스 계산으로 부모·자식 탐색이 쉬움
• 하지만 비정형 트리(uneven tree) 에는 공간 낭비가 심함

 2) 연결 표현 (Linked Representation)

배열표현보다 연결표현이 tree를 표현하는데에 더 적합함

왜냐?!

1. 트리는 가변적 구조를 가짐.  => 노드의 개수나 자식 수가 가변적이므로 크기변동 가능성 O => 배열 활용 시 비효율적
2. 비정형 트리의 경우 배열 활용 시 공간 낭비가 심함

linked list를 활용해 트리릂 표현하면 동적메모리 관리, 삽입, 삭제에 더 유리함

 

즉,

표현병식	특징	장점	단점
배열 표현	완전 이진 트리에 적합	인덱스 접근 빠름	공간 낭비, 비정형 트리에 부적합
연결 리스트 표현	포인터로 노드 연결	구조 유연, 동적 확장 용이	포인터 관리 복잡, 메모리 추가 사용

 

 

각 노드가 자신의 왼쪽·오른쪽 자식에 대한 포인터를 가짐.

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} TreeNode;

• 일반적이며 가장 많이 사용되는 표현.
• 트리의 구조가 가변적일 때 적합.

예를들어

        A
       / \
      B   C
     / \   \
    D   E   F

// 이런 트리를 표현하면
A.left → B
A.right → C
B.left → D
B.right → E
C.right → F