반응형
반응형
Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS
💋 트리 자료구조란?
- 데이터를
탐색하기 쉽도록
하기 위해서계층적
인 방식으로 정리한 구조 - 계층적인 관계의
노드
들이edge
로 연결된 형태 - 각 노드는 값(value) + 다른 노드의 레퍼런스(ref)로 구성
A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
💋 트리 자료구조 용어
✔️ 구조 용어
- 간선(edge)
- 노드와 노드를 연결하는 선 (link, branch)
- 구현 관점에서는 레퍼런스를 의미
- 루트 노드(Root Node)
- 위 예시에서 A 는 루트 노드
- 트리의 최상단 노드로 시작점 ⇒ Parent Node가 없음
- A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.
- 자녀 노드(Child Node)
D, E
는 B의 자녀 노드- 모든 노드는 0개 이상의 자녀 노드를 가진다.
- 부모 노드(Parent Node)
- 자녀 노드를 가지는 노드
- B는
D, E
의 부모 노드 - The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}.
- 형제 노드(Sibling)
- 같은 부모를 가지는 노드들
D,E
는 형제 노드- 조상 노드(Ancestor of a Node)
- 부모 노드를 따라, 루트 노드까지 올라가며 만나는 모든 노드
A,B
는 E의 조상 노드- 자손 노드(Descendant)
- 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
I, M, N
은 E의 자손 노드- 내부 노드(Internal node)
- 자녀 노드를 가지는 노드
- Leaf Node를 제외한 모든 노드
- 외부 노드(Leaf Node / External Node)
- 자녀 노드가 없는 노드
K, L, M, N, O, P, G
는 외부 노드
✔️ 계산 용어
- 경로(Path)
- 한 노드에서 다른 노드 사이의 노드의 시퀀스(sequence)
- A에서 J노드의 경로는
A - C - F -J
- 경로 길이(length of path)
- 경로에 있는 노드의 수
- A에서 J노드의 경로 길이는 4
- 노드의 높이(height)
- 노드에서 리프 노드까지 가장 긴 경로의 간선 수 (때에 따라 노드의 수로 세기도 한다)
- D의 높이는 2
- 리프 노드의 높이는 0
- 트리의 높이(height of the tree)
- 루트 노드의 높이
- 위 그림에서 트리의 높이는 4
- 노드의 깊이(depth)
- 루트 노드에서 해당 노드까지 경로의 간선 수
- D의 깊이는 2
- 루트 노드의 깊이는 0
- 트리의 깊이(depth of the tree)
- 트리에 있는 노드의 깊이 중 가장 긴 깊이
- 위 그림에서 트리의 깊이는 4
- 트리의 깊이 = 트리의 높이
- 노드의 차수(degree)
- 노드의 자녀 노드 수
- H의 차수는 2
- 트리의 차수(degree of the tree)
- 트리에 있는 노드들의 차수 중 가장 큰 차수
- 위 그림에서 트리의 차수는 2
- 두 노드 사이의 거리(distance)
- 두 노드의 최단 경로의 간선 수
- L과 O의 거리는 8
- 노드의 레벨(level)
- 노드와 루트 노드 사이의 경로에서 간선 수
- 루트 노드의 레벨은 0 (또는 1로 보는 경우도 있다)
- 넓이(width)
- 어떤 레벨에 있는 노드의 수
- Level 2의 width는 4
- 노드의 크기(size)
- 자신을 포함한 자손 노드의 수
- C의 크기는
C, G, F, J, O, P
를 모두 센 6 - 트리의 크기(size of the tree)
- 트리의 모든 노드의 수
- 위 그림에서 트리의 크기는 16
- 서브 트리(Subtree)
- 각 노드의 자녀 노드들은 재귀적으로 서브 트리를 구성한다.
- Any node of the tree along with its descendant.
이런식으로, 트리는 재귀적으로 내부적으로 수많은 서브트리를 가지면서 만들어진다.
struct Node
{
int data;
struct Node *first_child;
struct Node *second_child;
struct Node *third_child;
.
.
.
struct Node *nth_child;
};
💋 트리 구조의 특징
- 루트 노드는 딱 1개만 존재한다.
- 트리 내에 사이클은 존재하지 않는다.
- 자녀 노드는 하나의 부모 노드만 가진다.
- 데이터를 순차적으로 저장하지 않는 비선형 구조
- 트리에 서브 트리가 있는 재귀적 구조
- 계층적 구조
💋 참고자료
- https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/
- https://www.youtube.com/watch?v=ohrwGtqeW-I&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=9
도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!
반응형