[TIL] 자료구조 - Tree

자료구조를 공부한 지가 오래 되어 다 까먹었을 줄 알았는데 또 문제를 풀다 보니 했던 것들이 기억이 나 도움이 되었다. DFS/BFS 문제는 역시 쉽지 않다. 페어와 그래프 활용 문제를 총 4문제 풀었는데 마지막 DFS 활용 문제는 테스트 케이스를 모두 통과하지는 못했다. 스택이랑 큐 활용 문제도 주말에 한번에 다섯 문제 정도 연달아 푸니 어떤 식으로 접근하면 될지 감이 왔으니 DFS/BFS도 활용 문제를 더 찾아 풀어봐야 겠다.

Today I Learned

Tree

• 트리는 부모-자식 관계의 노드들로 이루어진 비선형 자료구조다.
• 하나의 노드는 자식 노드들만 가리킬 수 있다. (부모나 형제 노드는 가리킬 수 없음)
• 트리는 하나의 루트 노드를 가진다. (루트 노드가 여러 개일 수는 없음)
• 트리 구조는 HTML, DOM, 네트워크 라우팅, 파일 시스템 등에 사용된다.

Binary Tree

• 각각의 노드가 최대 2개의 자식 노드를 갖는 트리

BST (Binary Search Tree)

• 검색을 빠르게 할 수 있는 이중트리.

• 각각의 노드는 최대 2개의 자식 노드를 가질 수 있으며, 항상 왼쪽에 있는 자식 노드에는 부모 노드의 값보다 작은 값이, 오른쪽에 있는 자식 노드에는 부모 노드의 값보다 큰 값이 들어가야 한다.

• BST에서는 빠르게 값을 검색하거나 추가할 수 있다. ( O(log n), 하지만 항상 보장된 것은 아니고 트리가 한쪽으로 치우쳐져 있다면 최악의 경우 O(n)의 시간이 걸릴 수 있다)

• cf. 균형이진탐색트리(Balanced Binary Search Tree)를 사용하면 노드가 추가/삭제될 때 자동으로 트리의 높이를 낮게 유지하도록 하여 트리가 한쪽으로 치우쳐지지 않도록 한다. (예: AVL트리, 2-3트리, B-트리 등)

Tree Traversal

• 특정 목적을 위해 트리의 각 노드를 정확히 한 번씩만 방문 하는 것
• 모든 노드를 방문하는 것이 목적인 경우 BFS/DFS 중 어느 것을 써도 무방하다. 둘 다 시간복잡도는 동일하다. (인접 행렬을 사용한다면 O(V**2), 인접 리스트를 사용한다면 O(V+E), 여기서 V는 정점의 개수 E는 간선의 개수)

BFS (Breadth-First Search)

• 너비우선탐색
• 수평방향으로 먼저 탐색
• 현재 탐색하고 있는 정점과 같은 레벨의 노드들을 우선 방문 하고 다음 레벨로 넘어감
• Queue와 while문을 사용해 구현
• 활용 : 최단거리 구하기

DFS (Depth-First Search)

• 깊이우선탐색
• 수직방향으로 먼저 탐색
• 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐사함
• Stack 또는 재귀함수로 구현
• 활용 : 경로에 조건이 있는 경우
• PreOrder : Root, Left, Right 순으로 탐색
• InOrder : Left, Root, Right 순으로 탐색
• PostOrder : Left, Right, Root 순으로 탐색