⚙️ 노드란?
노드로 이루어진 자료 구조
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
- 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
- 트리에는 사이클(cycle)이 존재할 수 없다.
- 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
- 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
용어 정리
루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
내부(internal) 노드: 단말 노드가 아닌 노드
간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
⚙️ 이진 트리(Binary Tree)
각 노드가 최대 두 개의 자식을 갖는 트리
이진 트리 순회
- BFS, DFS 모두 자식 노드들을 한 번씩 순회하기 때문에 시간복잡도는 동일하다.
- 공간 복잡도의 경우 너비가 넓은 트리의 경우 깊이 우선 탐색이 더 유리하고, 트리의 깊이가 깊을수록 너비 우선 탐색이 더 유리하다.
너비 우선 탐색 (BFS, Breadth First Search)
같은 층에 있는 노드를 우선적으로 탐색
10 -> 6 -> 15 -> 3 -> 8 -> 20
queue를 이용하여 구현
깊이 우선 탐색 (DFS, Depth First Search)
깊이에 따라 노드들을 탐색
stack 데이터 구조를 사용
주로 반복문을 활용하거나, 재귀문을 통하여 구현
1. 전위 순회(preorder)
Root - Left - Right
루트 - 왼쪽 - 오른쪽 순으로 순회
2. 중위 순회(inorder)
Left - Root - Right
왼쪽 - 루트 - 오른쪽 순으로 순회
3. 후위 순회(postorder)
Left - Right - Root
왼쪽 - 오른쪽 - 루트 순으로 순회
슬기로운 개발 생활