Tree

Tree는 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 일종이다. 마치 나무가 뿌리에서 시작해 줄기로 잎으로 뻗어 나가듯한 모습을 가지고 있다. 나무를 뒤집어 놓은 모습을 가지고 있으며, 나무는 위로 뻗어나가지만 Tree는 밑으로 파고 들어간다.

Root

트리는 그래프의 일종이기 때문에 정점과 간선으로 이루어 진다. tree에 대해서 정점을 노드(Node)라고 부르며, Root는 노드중 최 상단의 꼭짓점 데이터를 의미 한다. 루트로 부터 시작해 간선을 따라 점차 아래로 가지를 치며 내려가며 상위 노드와 하위 노드간에 부모 자식 관계가 생긴다. 루트를 기준으로 노드를 타고 한단계씩 내려갈때 마다 깊이(Depth)는 깊어 진다. 루트는 Level 0의 깊이다.

Node

• Level : 루트에서 자신까지의 거리를 Level이라 한다. Level 0는 루트 자신이며 Level 1은 루트로 부터 1거리 만큼 떨어져 있고 Level 2는 루트로 부터 2거리 만큼 떨어져 있다.
• Height : 루트로 부터 가장 안쪽에 있는 노드까지의 레벨을 높이라고 한다.
• Sibiling Node : 같은 레벨에 있는 다른 노드들을 해당 노드의 형제 노드라 한다.
• Leaf Node : 자식을 가지지 않는 노드를 의미한다. 뿌리에서 시작해 줄기를 따라 가다 보면 끝에 잎이 있고 잎에서 부턴 나무가 이어지지 않는다.

Tree 구조의 사용 예

Tree 구조의 가장 대표적인 예는 컴퓨터의 디렉토리 구조가 있다. C 드라이브 안에는 여러 폴더가 있고(C 드라이브를 루트로 둔 레벨1 노드들) 해당 폴더의 안에는 또 여러개의 폴더가 그리고 그 폴더 안에는 여러개의 폴더가 있다.

• 토너먼트 방식 대진표
• 가계보

이진 트리(Binary Tree)

하나의 노드는 자식 노드를 여러개를 가질수도 있고 하나만 가질수도 있고 아예 가지지 않을 수도 있다. 그리고 이런 여러 형태의 트리구조중 부모노드가 2개의 자식노드만 가진 경우를 이진 트리라 한다.

• 정 이진 트리 : 각 노드가 0개 혹은 2개의 자식 노드를 갖는 경우
• 완전 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하며(2개씩) 마지막 레벨의 노드는 전부 차 있지 않아도 되지만, 왼쪽은 전부 채워져 있어야 한다.
• 포화 이진 트리 : 정 이진 트리 이면서 완전 이진 트리인 경우, 마지막 레벨 까지 모든 노드가 채워져 있다.

BST(Binary Search Tree)

이진 탐색 트리는 이진 트리의 한 종류로 다음과 같은 특징을 지닌다.

• 모든 왼쪽 자식들은 루트나 부모보다 작은 값이다.
• 모든 오른쪽 자식들은 루트나 부모보다 큰 값이다.
• 이진 탐색 트리에서의 검색은 다음과 같다
  • 검색 값을 루트노드와 비교한다. 일치할 경우 루트노드를 리턴한다.
  • 일치하지 않을 경우, 검색 값이 루트노드보다 작을 경우 왼쪽 자식을 타고 간다.
  • 일치하지 않을 경우, 검색 값이 루트노드보다 클 경우 오른쪽 자식을 타고 간다.

그 밖의 Tree

• 루트 이진 트리 : 하나의 루트 노드를 가지는 이진트리
• 무한 완전 이진 트리 : 모든 노드는 두 개의 자식 노드를 갖는 트리, 재귀적으로 계속 늘어난다.
• 균형 이진 트리 : 이진 트리를 균형 이진 트리로 구성 하면 잎 노드에 대해 가능한 최대의 최소 깊이를 갖는다.
• 변질 트리 : 각 노드가 하나의 자식만을 갖는 트리를 의미한다. 이 때 트리는 인접 리스트의 구조와 동일 하다.

Tree순회

tree의 순회는 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 의미한다.

• 트리의 (연결된) 모든 노드를 방문해야 한다.
• 한 번씩 방문 해야 한다. 여러번 방문하는 것은 의미가 없다.(한번 방문한 노드는 재탐색을 하지 않아야 한다.)

이진 트리 탐색

루트를 언제 들리느냐에 따라 나뉜다.

• 전위 순회(Preorder)
  • 제일 처음 루트 노드를 방문한다.
  • 루트를 기준으로 왼쪽의 노드를 방문한다. 계속 해서 왼쪽 노드를 타고 가며 잎 노드에 도달할 때 까지 반복 한다.
  • 잎 노드에 도달하면 오른쪽 노드를 탐색 한다.
• 중위 순회(Inorder)
  • 제일 처음 왼쪽 끝의 잎 노드를 방문한다.
  • 계속 해서 왼쪽 노드를 탐색 한다. 루트를 중심으로 첫 왼쪽 자식의 하위 노드 중 왼쪽 노드를 확인 했다면 오른쪽 노드를 확인한다.
  • 루트 노드를 방문 한다.
  • 루트 노드의 오른쪽 자식 노드 부터 하위 노드 중 왼쪽 노드를 확인한다.
  • 나머지 오른쪽 노드를 확인한다.
• 후위 순회(Postorder)
  • 제일 왼쪽 끝의 잎 노드를 방문한다.
  • 루트를 거치지 않고 오른쪽 노드를 방문한다.
  • 루트를 가장 마지막에 방문 한다.

BSF(Breathed First Search)

너비 우선 탐색은 그래프의 탐색 방법이다. 트리도 그래프의 일종이기 때문에 트리의 탐색에서도 유효하다. 너비 우선 탐색은 Queue 자료구조를 이용하여 구현한다.

BSF의 탐색 논리

특정 정점을(노드를) 기준으로 목표 정점 까지 가는 경로를 찾을때 기준 정점에서 가까운 정점들을 먼저 탐색한다. 기준 정점을 Level 0라 했을때 Level 1에 목표 정점이 없다면 Level 2를 탐색한다. 목표 정점과 일치 하는 결과를 찾을때 까지 Level을 늘리며 탐색한다.

BSF의 장점

출발 정점에서 목표 정점 까지의 최단 길이 경로를 보장한다.

BSF의 단점

• 출발 정점에서 목표 정점 까지의 경로가 매우 길 경우에는 탐색 가지가 급격히 증가하여 매우 큰 Queue를 필요로 할수 있다.
• 목표 정점이 존재하지 않는다면 모든 정점을 방문할 때 까지 결과를 내지 못한다. 다시 말해 최악의 경우 모든 정점을 방문 하지 않으면 끝나지 않는다.
• 무한 그래프의 경우에는 결코 해를 찾지 못하며, 끝내지도 못한다.

BSF는 출발 정점에서 목표 정점까지 가는 경로가 분명히 존재하는 경우, 그리고 그런 경로가 여러개인 경우 경로중 최단 경로를 찾아내는데 유용하다.

DSF(Depth-First Search)

깊이 우선 탐색도 그래프의 탐색 방법이다. 역시 트리에도 적용 가능하다. 깊이 우선 탐색은 Stack 자료구조(재귀)를 이용하여 구현한다.

DFS의 탐색 논리

시작 정점 에서 다음 Level의 정점을 추가 시키며 추가된 자식 노드가 목표 노드일 때까지 계속 해서 Level을 추가시킨다.

깊이 제한

목표 노드가 나올때 까지 계속해서 깊이가 깊어지므로 깊이가 무한히 깊어 질수 있다. 이를 막기 위해 깊이 제한을 두고 깊이 제한에 도달할 경우 부모 노드로 돌아가 다른 기준의 자식 노드를 추가하고 새로 추가된 자식 노드쪽으로 다시 들어간다. 이렇게 다시 부모 노드로 되돌아오는 것을 백트래킹이라 한다.

DFS의 장점

• 현재 경로상의 노드들만 기억하면 되기 때문에 상대적으로 작은 저장공간을 필요로 한다.
• 목표 노드가 깊은 곳에 있을 경우 상대적으로 빨리 찾을 수 있다.

DFS의 단점

• 해가 없는 경로인데 너무 깊이 들어갈 가능성이 있다. 이때는 오히려 탐색 시간이 증가 한다.
• 시작 정점부터 목표 정점까지의 경로가 최단 경로라는 보장이 없다.

DSF는 목표 정점 까지 가는 경로의 존재가 불투명한 경우, 경로의 존재를 확인하기 위해 유용하다. 단 경로의 존재 여부는 알 수 있어도 해당 경로가 최단 경로인지는 보장할 수 없다.