728x90
반응형
트리란
- 트리는 그래프의 일종으로, 노드로 이루어진 계층적 구조이다.
- 한 노드를 시작으로 다른 노드를 순회하며 자기 자신에게 돌아오는 순환 없는 연결 그래프이다.
트리의 용어
- 루트 노드(Root Node): 트리 구조의 최상위 노드로, 모든 다른 노드들은 이 루트 노드에서 시작된다.
- 부모 노드(Parent Node): 다른 노드에게 연결된 상위 노드를 가리킨다.
- 자식 노드(Child Node): 부모 노드에 의해 직접적으로 연결된 하위 노드를 말한다.
- 잎 노드(Leaf Node): 자식 노드가 없는 노드로, 트리 구조의 끝에 위치한다.
- 서브 트리(Subtree): 트리 안에서 다른 트리를 포함하는 부분 트리를 의미한다.
- 형제(Sibling): 같은 부모를 가진 노드를 의미한다.
- 간선(edge): 노드를 연결하는 선으로 link나 branch라고도 부른다.
- 노드의 크기(size): 자신을 포함한 모든 노드의 개수를 말한다.
- 노드의 깊이(depth): 해당 노드가 루트에서 몇 개의 간선을 거쳐야 하는지 의미한다.
- 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합을 의미한다.
- 노드의 차수(degree): 하위 트리 개수 / 간선 수, 즉 각 노드가 갖고있는 가지의 수를 의미한다.
- 트리의 차수(degree of tree): 트리의 최대 차수를 의미한다.
- 트리의 높이(height): 루트에서 가장 깊숙하게 있는 노드의 깊이를 의미한다.
트리의 특징
- 트리는 부모-자식으로 이루어지는 계층적 구조이다.
- 각 노드는 하나의 부모노드를 갖거나 자신이 루트 노드임을 의미한다.
- 트리는 특정 노드로 가는 길이 정해져있으며, 이러한 특징으로 인해 사이클이 존재하지 않는다.
- 트리는 데이터 저장보다 효과적인 탐색을 위해 사용된다.
- 노드가 N개인 트리는 N-1개의 간선을 가진다.
트리의 장단점
- 장점
- 계층적인 구조로, 데이터를 관리하는데 효율적이다.
- 특정 데이터를 검색하는데 뛰어나다.
- 단점
- 구현이 상대적으로 어렵다.
- 트리는 데이터가 정렬되어있지 않다면 검색 효율이 떨어진다.
출처 : 트리 구조 - 위키백과, [자료구조] 트리란
728x90
반응형
'개념정리 > 자료구조' 카테고리의 다른 글
[자료구조] 이진탐색트리(Binary Search Tree)란? (1) | 2023.12.06 |
---|---|
[자료구조] 이진트리(Binary-Tree)란? (0) | 2023.11.29 |
[자료구조] 연결리스트(Linked List)란? (0) | 2023.11.25 |
[자료구조] 덱(Deque)이란? (1) | 2023.11.22 |
[자료구조] 원형 큐(Circle Queue) (1) | 2023.11.18 |