트리 , DFS, BFS

임준성·2023년 3월 21일

자료구조

CS

목록 보기

2/9

트리란?

트리 자료구조는 굉장히 우리 일상과 밀접한 개념이다.

부모와 자식, 토너먼트 표, 어떠한 조직의 조직도 역시 트리 자료구조다.

또한 컴퓨터의 폴더 및 디렉토리 시스템이 가장 대표적이라고 볼 수 있는데,

우리는 파일을 찾기 위해 어떠한 폴더를 들어가고, 또 들어가는 식으로 목표에 도달하게 된다.

계층 구조

트리는 대표적인 계층 구조의 자료구조이다.

이는 부모 & 자식으로 이루어진 관계를 뜻하는데,

이러한 계층 형식의 자료구조는 탐색에서 엄청난 효율을 자랑한다.

트리 구성 요소

Key

value라고 불리기도 하며 해당 노드의 data를 나타낸다.

ex) 1번 노드의 key 값은 6

Root

트리의 가장 윗 부분에 위치하는 노드를 루트 노드라고 한다. 하나의 트리에는 하나의 루트 노드가 존재한다.

Parent

한 노드에서 위로 직접적으로 연결된 노드를 부모 노드라고 한다. 노드는 1개의 부모 노드를 가질 수 있다.

Children

어떤 노드로 부터 간선으로 연결된 아래쪽 노드를 자식 노드라고 한다. 노드는 여러 개의 자식을 가질 수 있지만 자식 노드는 하나의 부모만 가질 수 있다.

Edge

간선이라고도 불리며 트리와 트리를 이어주는 개념적 존재이다. 간선으로 서로 연결되어 있으면 해당 트리는 부모-자식 관계로 이어진 것이다.

Leaf Nodes

트리의 가장 아래에 위치하는 노드를 리프 노드라고 한다. 주의해야할 점이 트리에 물리적으로 가장 아래에 있는 노드를 뜻하는게 아니라 노드가 더 이상 간선으로 연결할 수 없고, 더 뻗어나갈 수 없는 마지막 노드에 위치할 때 리프 노드라고 부른다.

SubTree

트리 안에서 다시 어떤 노드를 루트 노드로 정하고 그 자손으로 이루어진 트리를 서브 트리라고 한다.

Height of the Tree

트리의 높이, 즉 차수(Degree, Level)라고도 하며 루트 노드로부터 한 계층이 내려갈 수록 1씩 차수가 증가한다.

트리의 탐색

트리의 탐색에는 두 가지 방법이 있다.

BFS::너비 우선 탐색

너비 우선 탐색은 가장 낮은 레벨에서 시작해서 왼쪽에서 오른쪽 방향을 탐색하고 한 레벨에서 탐색이 끝나면 다음 레벨로 내려가는 방식의 탐색 구조이다.

너비 우선 탐색은 가까운 정점을 먼저 방문 하고 멀리 있는 정점을 나중에 방문한다는 점에서 특정 정점과의 관계가 중요한 탐색 방법이다.

예를 들어 전 세계의 도시 이름을 검색한다고 하면, 도시 A와 B 는 같은 차수에 있기 때문에 도시 A에 있는 모든 동과 마을을 모두 조사하는 DFS보다 빠른 탐색이 가능하다.

⭕ BFS 장점

답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

❌ BFS 단점

경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

DFS::깊이 우선 탐색

깊이 우선 탐색은 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다.

리프에 도달해서 더 이상 검색을 진행할 곳이 없으면 부모에게 돌아가고 다시 자식 노드로 내려간다.

Step 1: 스택에 시작 노드를 넣는다.
Step 2: 스택이 비어있으면 실행을 멈추고 False를 반환한다.
Step 3: 스택의 맨 위 노드가 찾고자 하는 노드라면 탐색을 종료하고 True를 반환한다.
Step 4: Step 3에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를 POP하고, 스택에 들어온 적이 없는 POP한 노드의 모든 이웃 노드를 찾아서 순서대로 스택에 넣는다.
Step 5: Step 3으로 돌아간다. ( 재귀 )

⭕ DFS 장점

현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다는 점이 있다.

❌ DFS 단점

해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색하며, 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.
DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없는데,  DFS는 해에 도착하면 탐색을 종료하기 때문이다.

깊이 우선 탐색에서는 언제 노드를 방문할지에 따라서 3가지 종류로 나뉜다.

Tree Traversals (트리 순회)

트리 순회 방법은 위에서 말 했던 것 처럼 언제 노드를 방문할지를 정하는 개념인데, 크게

전위 순회 - PreOrder
중위 순회 - InOrder
후위 순회 - PostOrder

이진 트리 Binary Tree

이진 트리는 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리이다.

이 때 중요한 점이 왼쪽 자식과 오른쪽 자식을 하나씩만 가져야 이진 트리가 된다.

이러한 이진 트리는 왼쪽 자식과 오른쪽 자식을 구분한다는 특징이 있는데, 우리가 트리의 개념과 용어 에서 배웠듯이 오른쪽 자식은 오른쪽 서브트리를 갖고 왼쪽은 왼쪽 서브트리를 가질 수 있다.

Full Binary Tree

Full Bianry Tree는 모든 노드의 자식이 0이거나 2인 이진 트리이다.

Complete Binary Tree

Complete Binary Tree는 마지막 노드를 제외하고 모든 노드의 자식이 0이며 마지막 레벨의 노드는 왼쪽에 채워져 있는 형태이다.

Degenerate Binary Tree

Degenerate Binary Tree는 모든 부모 노드가 왼쪽으로 자식을 갖는 경우이다.

Perfect Binary Tree

Perfect Bianry Tree는 모든 노드의 자식이 0이거나 채워져 있는 형태로 루트 노드를 기준이로 좌 우가 균형이 되어야 한다.

Balanced Binary Tree

Balanced Binary Tree는 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 최대 1만큼 차이가 날 수 있는 이진 트리다.

이진 탐색 트리 Binary Search Tree

이진 탐색 트리는 다음과 같은 조건을 만족하는 이진 트리를 Binary Search Tree라고 한다.

기본 전제 : 트리의 키에는 값이 반드시 존재하며 값들은 비교할 수 있는 집단이 존재하는 전순서 여야 한다.

조건 1 : 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값 보다 작아야 한다.
조건 2 : 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
조건 3 : 같은 키의 값을 갖는 노드는 존재하지 않는다.
조건을 간단하게 정리하자면 한 노드가 있을 때 해당 노드보다 작으면 왼쪽, 크면 오른쪽으로 배치가 된 것들이 이진 탐색 트리(BST)가 된다는 것이다.

이제 간단하게 왜 이진 탐색 트리를 사용하는지에 대해서 알아보자면