자료구조
[자료구조] 트리(Tree)
JadenM
2021. 3. 15. 22:15
[트리 구조]
정의:
트리는 계층형 트리 구조를 시뮬레이션하는 추상 자료형( ADT)으로,
루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.
후기
알 것 같으면서도 아직 잘 모르겠다?!
조금만 더 살펴보자.
트리(Tree)는 하나의 뿌리에서 위로 뻗어 나가는 형상처럼 생겨서 '트리(나무)'라는 명칭이 붙었다.
트리 구조를 표현할 때는 나무의 형상과는 반대 방향으로 표현한다.
가계도(조직도)의 형상과도 비슷하다.
트리 구조는 아래 그림의 형상을 가진다.
트리의 대표적인 특징
- 트리는 노드로 이루어진 자료 구조.
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고, 이는 반복적으로 정의된다.
트리의 각 명칭
- 루트(Root) : 트리구조가 시작되는 지점
- 간선(Edge) : 노드를 이어주는 선
- 자식(Child) : 부모 노드로부터 이어진 노드
- 차수(Degree) : 자식 노드의 개수
- 크기(Size) : 자신을 포함한 모든 자식 노드의 개수
- 리프(Leaf) : 차수가 0인 노드(자식이 없음ㅠㅠ)
- 높이(Height) : 현재 위치에서부터 리프까지의 거리
- 깊이(Depth) : 루트에서부터 현재 노드까지의 거리
그래프와 트리의 차이점
- 그래프와 트리의 차이점은 무엇인가요?
면접자 A : "어... 트리는 그래프의 한 종류로... 조상 대대로 이어온... 뿌리 깊은..."
- 네?
면접자 B : "트리는 순환 구조를 갖지 않는 그래프입니다.(단호)"
우리는 면접자 B와 같이 답변을 할 수 있어야 한다.
그래프 vs 트리
- 트리 구조는 순환 구조(Cyclic)가 아니다.
- 트리의 방향은 부모 노드에서 자식 노드를 가리키는 단방향뿐이다.
- 트리는 하나의 부모 노드를 갖는다.
- 루트는 하나여야 한다.
아래 트리가 아닌 예를 한번 살펴보자.
예시 1) 트리는 순환 구조를 갖지 않아야 하는데 순환하기 때문에 탈락.
예시 2) 트리는 부모가 하나여야 하는데 둘이므로 탈락.
예시 3) A -> B와 D <- C -> E가 서로 연결되어 있지 않고, 루트가 둘이므로 탈락.
이진 트리
각 노드가 m개 이하의 자식을 갖고 있으면 m-ary 트리(다항 트리, 다진 트리).
여기서 m=2, 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리(Binary Tree)라 한다.
이진 트리는 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태를 띤다.
이진 트리의 유형
| 정 이진 트리(Full Binary Tree) | 모든 노드가 0개 또는 2개의 자식 노드를 갖는다. |
| 완전 이진 트리(Complete Binary Tree) | 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다. |
| 포화 이진 트리(Perfect Binart Tree) | 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로, 가장 완벽한 유형의 트리. |
이진 탐색 트리(BST)
이진 탐색 트리(Binary Search Tree)란, 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다.
자가 균형(또는 높이 균형) 이진 탐색 트리는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리다.
자가 균형 이진 탐색 트리는 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다.
트리 구조에 노드가 엄청나게 많을 경우엔 균형트리의 연산속도가 불균형 트리와 비교하기 부끄러울 정도로 훨씬 빠르다.
"끝!"
