TIL-072 | 트리(Tree) 자료구조

Lee, Chankyu·2022년 1월 21일

자료구조&알고리즘

목록 보기

9/12

🌈 트리(Tree) 자료구조

앞서 공부했었던 스택(Stack), 큐(Queue) 등의 자료구조는 선형구조에 포함된다. 선형구조는 데이터들을 순차적으로 나열한 형태를 띈다면 트리(Tree) 구조는 데이터가 계층적(혹은 망)으로 구성되어 있다. 또한 선형구조는 데이터의 입/출입에 초점이 맞춰져 있다면 트리 구조는 데이터의 표현에 초점이 맞춰져 있다. 힙(heap)구조, 이진 검색 트리 등을 공부하며 트리에 대해 경험해보았지만 트리 구조 자체에 대해 좀 더 알아보자! 🧐

트리(Tree) 란?

트리 자료구조는 이름이 뜻하는대로 나무의 형태와 같은 자료구조를 의미한다. 다만 나무의 형태가 거꾸로 되어있는, 즉 뿌리가 최상단에 있는 형태이다. 최상단 하나의 노드를 루트로 하여 나머지 노드들이 간선으로 연결되어 있다.

트리의 구조

트리는 하나의 루트 노드를 갖는다.
루트 노드는 0개 이상의 자식 노드를 갖고 있다.
그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
트리에는 사이클(cycle)이 존재할 수 없다.
노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
각 노드는 어떤 자료형으로도 표현 가능하다.

트리 용어 설명

루트 노드(root node): 부모가 없는 최상단 노드, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎새 노드’라고도 부른다.
내부(internal) 노드: 단말 노드가 아닌 노드
간선(edge): 노드를 연결하는 선 (link, branch 라고도 칭함)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수(list의 length)
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree): 하위 트리 개수(간선 수 (degree) = 각 노드가 지닌 가지의 수)
- D의 차수 = 2, E의 차수 = 1
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리의 특징

그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
트리는 계층 모델 이다.
트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
- loop나 circuit이 없다. 당연히 self-loop도 없다.
- 즉, 사이클이 없다.
노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
- 즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.
루트에서 어떤 노드로 가는 경로는 유일하다.
- 임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
- 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.