🐢 4. Trees and Graphs

🫧 트리

: 하나의 루트 코드를 가진다

루트 노드는 0개 이상의 자식 노드를 갖고 있다

트리에는 사이클 존재할 수 없다

노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다

각 노드는 어떤 자료형으로도 표현이 가능하다

노드(node)	트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소
간선(edge)	노드와 노드를 연결하는 연결선
루트 노드(root node)	트리 구조에서 최상위에 존재하는 A와 같은 노드
단말 노드(terminal node, leaf node)	아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드
내부 노드(internal node),비 단말 노드(non-terminal node)	단말 노드를 제외한 모든 노드로 A, B와 같은 노드
디그리(degree,차수)	각 노드에서 뻗어나온 가지의 수 A=3, B=2
트리의 디그리	노드들의 디그리 중에서 가장 많은 수 A가 3개의 디그리를 가지기 때문에 트리의 디그리는 3이다.
부모 노드(parent node)	어떤 노드에 연결된 이전 레벨의 노드 E,F의 부모노드는 B
형제 노드(brother node)	동일한 부모를 갖는 노드들 E의 형제노드는 F

레벨(level),깊이	트리에서의 각 층별로 숫자로 매겨서 이를 트리의 ‘레벨’이라 한다. 이 트리의 레벨(깊이)는 3이다.
높이(height)	트리의 최고 레벨을 가리켜 ‘높이’라 한다.

🫧 BFS 노트

• level order (BFS, 큐를 사용하여)
• 시간 복잡도: O(n)
• 공간 복잡도: 최고: O(1) 최악: O(n/2)=O(n)

🫧 DFS 노트

• 시간 복잡도: O(n)
• 공간 복잡도: 최고: O(log n) - 평균적으로, 트리의 높이이다. 최악: O(n)
• 중위(inorder) (DFS: 왼쪽, 자신, 오른쪽)
• 후위(postorder) (DFS: 왼쪽, 오른쪽, 자신)
• 전위(preorder) (DFS: 자신, 왼쪽, 오른쪽)