[Data Structure] Tree & Graph

CS공부 6일차. 오늘 정리한 내용은 Tree와 Graph입니다.

Tree

• Tree는 loop나 cycle이 없는 그래프의 일종으로 비선형 자료구조이며 하나의 루트노드를 가집니다. node가 n개이면 n-1개의 edge를 가집니다.

• Binary Tree : 자식노드가 최대 두개로 구성된 트리

  • Full Binary Tree : 단말 노드를 제외한 모든 자식노드들이 2개 또는 0개인 트리
  • Perfect Binary Tree : 단말 노드를 제외한 모든 자식노드들이 2개인 트리
  • Complete Binary Tree : 마지막 레벨을 제외한 모든 레벨이 채워지고 데이터가 왼쪽부터 채워진 트리
  • skewed binary tree : 모든 노드가 부모의 왼쪽 혹은 오른쪽 자식인 트리
  • BST (Binary Search Tree) : 탐색을 위해 이진트리를 사용한 구조로 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크며 inorder로 탐색을 해나가면서 같으면 검색에 성공합니다. 트리가 편향되지 않으면 O(logN)만에 탐색, 삽입, 삭제를 수행할 수 있지만 편향되어 있으며 O(N)만큼 시간이 걸립니다.
  • AVL : 이진 탐색트리의 일종으로 왼쪽 자식 트리와 오른쪽 자식 트리의 높이 차(BF)가 1을 초과하지 않습니다.

• 레드 블랙 트리 : 노드는 black이거나 red인데 루트노드와 리프노드는 항상 블랙이고 red의 자식은 항상 black인 트리이다. 루트부터 리프까지의 black node의 개수는 항상 동일하다.

  • 삽입 : 삽입하려는 node는 red라고 가정하고 부모노드가 black이면 그대로 삽입하고 red이면 부모의 형제 노드가 black인지 red인지 확인합니다. 만약 부모의 형제 노드가 red이고, 조부모가 black이면 조부모와 부모, 부모의 형제의 색깔을 반전시켜주고 삽입합니다. 부모의 형제노드가 black이고 조부모도 black이면 삽입하려는 노드를 조부모에 직접 붙이고 부모의 형제 노드를 부모의 자식노드를 변경시켜 줍니다. 만약 같은 상황에서 삽입하려는 노드가 오른쪽 자식이 되면 삽입 노드를 부모의 부모로 만들어주고 부모 노드는 위와 같이 해줍니다.
  • 삭제 : 삭제하려는 노드가 red이거나 black이어도 자식노드가 red이면 바로 삭제할 수 있다.

• (Binary) heap : 우선순위 큐를 구현하기 위한 자료구조로 이진트리의 일종입니다. 다만 중복값을 허용하는 점이 다릅니다. 최대힙과 최소힙이 있으며 최대힙은 부모노드보다 자식노드가 항상 크고 최소힙은 반대입니다.

  • 삽입 : 제일 끝에 삽입하고 부모와 비교해가면서 조건에 맞게 교환합니다.
  • 삭제 : 루트노드를 삭제하고 제일 끝 노드를 위로 올려서 자식과 조건에 맞게 교환합니다.

• B-Tree와 B+Tree : B-Tree는 이진트리의 일종으로 자식 노드를 2개 이상 가질 수 있으며 항상 정렬되어 있습니다. 한 노드에 최대 M개의 값을 저장할 수 있는 것을 M차 B-tree라고 합니다. B+Tree는 이에 비해서 리프노드에 모든 값이 존재하고 리프노드들은 LinkedList로 연결되어 있습니다. B+Tree는 DB에서 index의 주소값을 저장할때 사용되는 자료구조이기도 합니다.

• HashSetvs TreeSet : HashSet은 해싱으로 구현되어 TreeSet 보다 검색이 빠릅니다. TreeSet은 이진탐색트리형태로 데이터가 저장됩니다.

• Trie : 문자열 검색을 쉽게 해주는 트리 형태로 retriever tree라고도 합니다. 예를 들어서 bell이랑 bear가 있다고 하면 b를 루트 노드로 하며 b를 부모로 가지는 e 노드가 존재하고, l과 a 노드로 분기하며 리프노드로 r가 l을 각각 가지는 트리 형태가 만들어 집니다. 검색시에는 알파벳을 하나하나씩 순차적으로 내려가면서 찾습니다. 문자열을 M개 넣고 가장 긴 문자열의 길이가 L이라고 하면 삽입, 탐색에 걸리는 시간은 O(L)이고 생성에 걸리는 시간은 O(M*L)입니다.

Graph

• Graph는 edge와 vertex로 이루어진 비선형 자료구조로서 트리를 포함하며 트리와는 다르게 cycle이나 loop를 허용합니다. edge는 방향성이 있을수도 있고 없을 수도 있는데 있는 경우에는 digraph라고 부릅니다. 한 vertex에서 나아가는 edge를 degree라고 부르는데 방향이 있는 경우 나가는 edge와 들어오는 edge로 나뉘고 각각 outdegree와 indegree로 불립니다. 그래프는 DFS나 BFS로 탐색할 수 있습니다.

• DFS : 깊이우선탐색 방법으로 연결된 vertex를 최대한 깊이 탐색한 후 인접 vertex로 이동하는 방식입니다. BFS에 비해 최단거리를 보장하지 않으며 stack으로 구현하는 경우가 많습니다.

• BFS : 너비우선탐색 방법으로 같은 level의 인접 vertex들을 모두 탐색한 후 아래 level로 넘어가는 방식입니다. 왼쪽에서 오른쪽으로 탐색하며 최단거리를 보장하고 queue를 사용하여 구현하는 경우가 많습니다.

• MST : Minimal Spanning Tree로서 그래프의 모든 vertex들을 최소 가중치로 연결한 tree입니다. cycle이 포함되지 않으며 vertex가 n개이면 edge가 n-1개 입니다.

  • Kruskal Algorithm : edge들을 오름차순 정렬하여 가중치가 적은 edge부터 연결해나가고 cycle이 있으면 제외하는 방식입니다.
  • Prim Algorithm : 시작 vertex만 MST에 포함시키고 MST에 연결된 edge들 중에 가장 가중치가 낮은 것들만 연결시켜 나가서 모든 vertex가 포함되면 종료시키는 방식입니다. edge가 적으면 kruskal이 적절하고 많으면 prim이 적절합니다.