이진탐색트리, DFS, BFS, (전위, 중위, 후위) 순회

주의 : 해당 게시물에서 작성될 내용은 과제를 해결하기 위해 출처의 내용을 그대로 작성한 부분이 많으며 일절 광고나 수익 창출 목적으로 쓰인 것이 아님을 밝힙니다.

이진탐색트리는 이진 탐색과 연결리스트를 결합한 자료구조입니다. 이진 탐색의 효율과 자료 입력과 삭제가 가능합니다. 구성은 자식 노드가 2개로 구성된 트리로 볼 수 있습니다.

특징으로는 각 노드에 중복되지 않는 키가 있고 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드로 되어있고 반대로 오른쪽은 해당 노드보다 큰 키를 갖고 있습니다. 또한 좌우 서브트리도 모두 이진 탐색으로 되어있어야 합니다. 연산은 트리의 높이가 h일 때, O(h)의 복잡도를 가지게 됩니다. 탐색 과정은 좌측에 작은 키, 우측에 큰 키로 되어있는 것을 기준으로 찾고자 하는 값을 비교해서 찾는 값이면 탐색을 종료하고 루트 노드의 키보다 작다면 왼쪽으로, 크다면 오른쪽으로 탐색을 진행해서 찾고자 하는 값을 찾을 때까지 반복하며 없더라도 최대 h번의 연산 및 탐색이 진행됩니다.

---

DFS, BFS에 대해 알아보겠습니다.

먼저 DFS는 Depth First Search로 깊이 우선 탐색의 줄임말입니다. 가장 깊이 내려가고 더 깊이 갈 수 없을 경우 옆으로 이동하는 방식입니다. 루트 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식입니다. 모든 노드를 방문하고자 했을 때나 밑에서 말하게 될 BFS보다 간단합니다. 하지만 검색 속도는 BFS보다 느리다는 단점이 있습니다.

 

다음 BFS는 Breadth First Search로 너비 우선 탐색의 줄임말입니다. 최대한 넓게 이동하고 더 이상 갈 수 없을 때 아래로 이동하는 방식입니다. 루트 노드에서부터 가장 인접한 노드를 먼저 탐색하는 방식으로 가까운 곳부터 방문하고 먼 곳을 나중에 방문하는 순회방법입니다. 주로 노드 사이의 최단 경로를 찾을 때 사용합니다.

좌 : DFS, 우 : BFS

---

트리 순회에서는 크게 세 가지 방법이 있습니다. 정확히 한 번만 체계적인 구조로 합니다.

전위 순회(Preorder Traversal)는 루트 노드를 먼저 탐색하고 자식 노드를 탐색하는 방법입니다. 위에서 설명한 DFS가 이 전위 순회의 방식을 사용하고 있습니다.

 

중위 순회(Inorder Traversal)는 왼쪽에 있는 자식 노드를 먼저 탐색하고 점차 오른쪽에 있는 자식 노드를 탐색하는 방법입니다.

 

후위 순회(Postorder Traversal)는 가장 밑에 있는 자식 노드를 먼저 탐색하고 위로 올라오면서 루트 노드까지 탐색하는 방법입니다.

 

이외에 레벨 순회(Levelorder Travalsal)도 있지만 이는 BFS와 같은 방식입니다.

 

읽어주셔서 감사합니다.