이전 포스팅 그래프(Graph)에 이어서 이번엔 트리(Tree)에 대해서 알아보자
트리(Tree)란?
🎄트리는 그래프의 하위 개념 중 하나이다. 트리를 그래프의 특징에 따라서 정의하게 된다면.
트리는 방향성이 있는 연결된 비순한 그래프이다.
트리는 이름과 같이 나무를 뒤집어 놓은 형태의 그래프 모양을 띈다.
하지만, 트리를 따로 분류해서 구분하는 까닦은 트리는 일반적인 그래프와는 달리, 계층 구조(hierarchical structure)를 가지는 특수성 때문이다.
😀디렉토리 폴더 구조가 트리의 대표적인 예가 될 수 있다. 우리는 하나의 폴더에서 부터 한 계층씩 다른 폴더를 찾아들어가서 마지막으로 파일을 찾게된다. 이때 폴더가 노드가 될 것이고, 들어가는 경로가 엣지, 파일이 리프노드가 가지는 데이터가 될 것이다.
트리의 구조
😀트리는 그래프의 하위 개념이기 때문에 그래프와 같이 구조는 정점과 간선으로만 이루어져 있지만, 각 정점과 간선의 갯수 깊이 관계 등에 따라서 다르게 지칭된다.
| 명칭 | 설명 |
|---|---|
| 노드(node) | 트리에서 데이터를 저장하는 기본적인 단위 그래프의 정점 |
| 루트 노드(root node) | 부모가 없는 노드, 트리 구조에서 최상위에 존재하는 A와 같은 노드 |
| 내부 노드(internal node) | 단말 노드가 아닌 노드 |
| 단말 노드(leaf node) | 자식이 없는 노드, (말단 노드, 잎 노드 라고도 부름) 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드 |
| 경로(edge) | 노드와 노드를 연결하는 연결선(link, branch 라고도 부름) 그래프의 간선 |
| 형제(sibling) | 같은 부모를 가지는 노드 |
| 노드의 크기(size) | 자신을 포함한 모든 자손 노드의 개수 |
| 노드의 깊이(depth) | 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 루트 노드로부터의 거리 |
| 노드의 레벨(level) | 트리의 특정 깊이를 가지는 노드의 집합 |
| 노드의 차수(degree) | 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 |
| 트리의 차수(degree of tree) | 트리의 최대 차수 |
| 트리의 높이(height) | 루트 노드에서 가장 깊숙히 있는 노드의 깊이 |
| 보조트리(Sub-Tree) | 큰 트리(전체)에 속하는 작은 트리 트리 내의 하위집합 또는 부분집합 |
트리의 특징
😀앞서 정의에서 말했듯이 그래프는 정점(vertex)들과 간선(edge)들로 이루어진 추상적인 자료구조로, 그 중에서도 트리는 특별한 형태의 그래프이다. 트리는 아래와 같은 특징을 가지며, 이 특징들 때문에 그래프와는 다른 새로운 성질을 가지게 된다.
-
트리는 사이클(cycle)이 없은 비순환 구조이다.
즉, 한 정점에서 출발하여 다시 자기 자신으로 돌아오는 경로가 존재하지 않는다. -
하나의 루트 노드와 0개 이상의 하위 트리
루트 노드는 반드시 하나여야 하며, 두개가 될 수 없다. -
모든 노드는 단 하나의 부모(parent) 노드를 가진다.
루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가져야 한다. -
노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다. -
모든 노드로 갈 수 있는 경로는 루트 노드를 거쳐야만 가능하다.
다른 노드들이 모든 경로를 지나기 위해서는 반드시 루트 노드를 거치는 구조를 가진다.
위와 같은 특징들로 트리는 일반적인 그래프와는 달리, 계층 구조(hierarchical structure)를 가지며, 데이터를 표현하거나 분석하기에 적합한 자료구조가 된다.
트리의 종류
😀트리의 종류는 노드의 갯수나 위치에 따라서 결정된다.
이진트리(Binary Tree)
이진트리란 자식 노드의 갯수가 두개 이하인 트리를 말하며 아래와 같이 분류한다.
-
정 이진 트리
자식 노드가 0 또는 2개인 이진 트리 -
완전 이진 트리
왼쪽에서부터 채워져 있는 이진 트리
마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있는 트리 -
변질 이진 트리
자식 노드가 하나밖에 없는 이진 트리 -
포화 이진 트리
모든 노드가 꽉 차 있는 이진 트리
반드시 노드의 개수가 2^(h+1)-1 의 개수를 가진다.(h=높이) -
균형 이진 트리
왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리
이진탐색트리(Binary Search Tree)
탐색을 위한 이진 트리의 일종으로 특수한 노드 값을 가지는 형태의 이진 트리이다.
이진 탐색트리에서 노드의 값이 저장되는 구조는 다음과 같다.
-
left node에는 부모노드보다 작은 값이 저장된다.
-
right node에는 부모노드보다 큰 값이 저장된다.
-
모든 노드는 중복된 값을 가지지 않는다.
- ⛔일반적인 비선형적인 구조로 잘 만들어진 이진탐색트리는 O(log n)의 시간복잡도를 가진다. 하지만 이진 탐색트리는 데이터의 삽입 순서에 따라서 선형적인 구조를 가지게 될 수도 있어 시간복잡도가 변경 되고, 최악의 경우 O(n)의 시간복잡도를 가지게 될 수도 있다.
AVL트리
균형 이진 트리의 일종으로 이진 탐색 트리에 균형 트리의 특징을 넣은 트리이다.
이진탐색 트리와 같은 특징을 가지고 있지만, AVL트리는 균형 트리의 특징을 가져 서브트리의 좌 우 높이가 1을 초과하지 않도록 동작한다.
균형이 무너지게 된다면, 새로운 노드를 넣거나 뺐을 때 왼쪽으로 돌리고, 오른쪽으로 돌리는 등 회전을 통해 균형을 유지한다.
- 균형을 맞추는 동작의 예시
균형이 무너진 첫번째 예시이다. 최상위 노드의 기준에서 높이가 왼쪽은 2인데 오른쪽은 0이기 때문에 2 차이가 나서 균형이 무너졌다. 이럴 때는 우회전을 통해 트리의 균형을 맞춘다. 반대의 경우는 좌회전을 통해 균형을 맞춘다.
첫번째 예시처럼 높이가 왼쪽은 2, 오른쪽은 0인데 조금 다른 경우이다. 왼쪽 서브트리의 모습이 < 모양을 띄고 있다. 이 때는 두 번째 노드를 좌회전 한 번 후, 전체 노드를 우회전 한 번 해줘서 균형을 맞춘다. 반대의 경우 또한 두 번째 노드를 우회전, 전체 노드를 좌회전 하여 맞춰준다.
- AVl트리는 항상 균형을 맞춰 높이를 유지하기 때문에 평균도 최악도 시간복잡도 O(log n)을 가지게 된다.
레드-블랙 트리(수정 진행 중)
균형 이진 트리의 일종
트라이(Trie)
스플레이 트리(Splay tree)
B+tree의 특징은 인덱스 포스팅에서 다루고 있으니 참고하자.
참고자료(출처)
티스토리 Monsieur_Songsong 포스팅 [알고리즘] 2.3.자료구조 : 트리(Tree) 이해하기와 구현
Velog kimdukbae 포스팅 [자료구조] 트리 (Tree)
티스토리 yoongrammer 포스팅 [자료구조] 트리 (Tree)
티스토리 개발자Miro 포스팅 [자료구조] 트리(Tree)란?
깃허브io 권희정 포스팅 [자료구조] 트리(Tree)란
제로초 알고리즘 자료구조(AVL 트리(tree))
p.s 종류에 대한 내용이 많아서 천천히 진행하겠습니다. 죄송합니다.
