[자료구조] 14. 트리 (Tree)
트리 (Tree)
트리(Tree)자료구조는노드(Node,정점)들이엣지(Edge, 간선)으로 연결된 데이터의 배치를 추상적으로 보여주는 계층적 구조이다.- 노드: 트리의 기본 단위이다.
- 엣지: 노드와 노드 사이를 연결하는 요소이다. 트리 내의 노드 수보다 엣지 수는 하나가 적다. 따라서, 노드 수가 \(N\)이라면 엣지의 수는 \(N-1\)이다.
DAG(Directed Acyclic Graphs, 방향성 비순환 그래프)의 한 종류이기 때문에 사이클의 특성을 가지고 있지 않다.
(1) 노드의 세부 구성 요소
- 루트 노드(Root Node): 트리의 최상위에 위치한 노드
- 부모 노드(Parent Node): 자식 노드를 가진 노드
- 자식 노드(Child Node): 부모 노드에 연결된 노드
- 리프 노드(Leaf Node): 자식이 없는 노드
- 내부 노드(Internal Node): 적어도 하나 이상의 자식을 가진 노드
- 부모 노드와 자식노드의 관계
- 형제(Sibling): 같은 부모 하에 위치한 자식 노드들의 관계
조상(Ancestor): 특정 노드의 조상은 해당 노드에서 루트 노드까지의 경로에 있는 모든 노드이다. 즉, 노드의 부모, 부모의 부모 등 루트 노드에 이르는 모든 노드가 조상에 해당한다.
하단의 그림을 예시로 들면, D의 조상은 B(D의 부모 노드)와 A(B의 부모 노드)이다.
후손(Descendant): 조상과 반대로, 특정 노드의 후손은 해당 노드에서 시작하여 리프 노드에 이르는 경로상의 모든 노드를 말한다. 특정 노드의 자식, 자식의 자식 등 모든 하위 노드가 해당 노드의 후손에 해당한다.
하단의 그림을 예시로 들면, B의 후손은 D, E, F, H이다.
(2) 트리와 노드의 특성
- 노드의 수준(Level): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 특정 깊이를 가지는 노드의 집합으로 나타낼 수 있음
- *루트 노드를 기점으로 1로 보는 경우도 흔히 있으나, 해당 포스팅은 0을 기준으로한다. 이에 따라, 하단의 설명될 특성들도 이를 기준으로 삼는다.
- 노드의 크기(Size): 자신을 포함한 모든 자손 노드의 수 (*모든 리프 노드들은 크기가 1이다.)
- 노드의 차수(Degree): 노드가 가진 자식 노드의 수(*모든 Leaf Node는 차수가 0이다.)
- 노드의 깊이(Depth): 노드의 레벨 + 1
- 트리의 깊이/높이(Depth/Height): 트리 내 모든 노드의 레벨 에서 “가장 큰 레벨+1”
서브 트리(Subtree): 서브트리는 트리의 일부분으로서, 특정 노드와 그 노드의 모든 자손 노드로 구성
트리의 종류: 이진 트리
(1) 이진 트리 (Binary Tree)
- 이진 트리는 모든 노드의 차수가 2이하인 트리 구조이다.
재귀적으로 정의하면 다음과 같다.
\[ 이진 트리 = 루트노드+왼쪽서브트리(이진트리 빈트리)+오른쪽서브트리(이진트리 빈트리) \] 다음은 이진 트리의 예시이다. 루트노드를 기준으로 좌측의 서브트리와 우측의 서브트리가 모두 이진트리이므로 이진트리 구조에 해당한다.
다음의 트리 구조는 A를 기준으로 좌측에 위치한 C,F,G,I,그리고 빈-노드로 이루어진 서브트리는 이진 트리에 해당하며, 우측에 위치한 B, D, E, H, 그리고 빈-노드로 이루어진 서브트리도 이진트리에 해당한다. 그러므로, 재귀적인 정의에 따라서 이진트리에 해당한다. (*이진 트리는 빈노드를 포함한다)
심지어,아래와 같은 트리도 재귀적 정의에 따라서 이진트리에 해당한다. 왜냐하면, 노드 C를 기준으로하는 서브트리는 좌측과 우측에 빈-트리가 위치하기 때문에 이진트리에 해당하며, 노드 B를 기준으로하는 서브트리는 이진트리 노드 C와 빈-트리가 위치하기 때문에 이진트리에 해당한다. 그리고, 최종적으로 루트 노드 A를 기준으로 이진트리 노드B와 빈-트리가 위치하기 때문에 이진트리에 해당한다.
(2) 포화 이진 트리 (Full Binary Tree)
- 모든 레벨에서 노드들이 모두 채워져 있는 트리이다. 즉, 빈-트리가 존재하지않는 이진 트리이다.
따라서, 깊이가 \(k\)라고 했을 때, 노드의 개수는 \(2^{k}-1\)이다.
(3) 완전 이진 트리 (Complete Binary Tree)
- 완전 이진 트리는 깊이가 \(k\)인 트리가 있다고 가정할 때,
레벨 \(k-2\)까지는 포화 이진 트리에 해당하며,
레벨 \(k-1\)에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리이다. - 쉽게 말하면, 포화 이진 트리를 우측 리프부터 제거해 나간 트리를 의미한다.
다음의 트리는 완전 이진 트리인 동시에, 깊이가 4인 포화 이진 트리에 해당한다.
위의 트리에서 가장 우측에 위치한 Node(G)를 지우면 다음의 조건을 만족한다.
- 레벨 2까지는 포화 이진 트리에 해당한다.
- 레벨 3에서는 왼쪽부터 노드가 순차적으로 채워져 있다.
따라서, 제거 이후의 트리도 완전 이진 트리에 해당한다. 하지만, 포화 이진 트리에는 해당하지 않는다.
위의 트리에서 다시 가장 우측에 위치한 Node(F)를 지워도 조건을 만족하기에 완전 이진 트리에 해당한다.
다시 가장 우측에 위치한 Node(E)를 지워도 조건을 만족하기에 완전 이진 트리에 해당한다.
