[자료구조] Tree, Graph

자료구조의 분류 

• 선형구조 : array, linked list, stack, queue, deque

• 비선형구조 : tree, graph

---

Tree

트리는 자식이라 부르는 서로 다른 원소를 많이 나열할 수 있는 자료구조이다. (저장보다 표현에 집중하는 자료구조)

노드와 브랜치를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다. 

 

• 사용 예시 : 가족의 족보, 연산 수식, 회사조직도, heap 등을 표현하기에 적합

노드 : 트리의 기본요소. 자료항목과 다른 항목에 가지를 합친 것을 의미한다.
근노드 : 트리의 맨 위에 있는 노드이다.
차수(degree) : 각 노드에서 뻗어나온 가지의 수.
트리의 차수 : 노드들의 차수들 중에서 가장 많은 수. 
단말노드(Terminal Node) = Leaf Node : 자식이 하나도 없는 노드 (차수가 0이다)
비단말노드(Non-Terminal Node) : 자식이 하나라도 있는 노드.
자식노드(Son Node, Children Node) : 어떤 노드에 연결된 다음 레벨의 노드.
부모노드 : 어떤 노드에 연결된 이전 레벨의 노드.
형제노드 : 동일한 부모를 갖는 노드들.
Level : 근노드의 레벨을 1로 가정한 후 어떤 레벨이 L이면 자식노드의 레벨은 L+1이다.
Depth(Height) : 트리에서 노드가 가질 수 있는 최대의 레벨.

 

이진 트리(Binary Tree)

• 기본적인 사용법은 이진트리. 이진트리의 각 원소는 최대 두개의 자식노드를 갖는다.
• 루트 노드를 중심으로 두 개의 서브 트리(왼쪽, 오른쪽)로 나뉘어진다. 또한 나뉘어진 두 서브 트리도 이진 트리여야만 한다.
• 자식 노드가 없으면 트리의 끝에 도착한 것이다.
• 포화 이진 트리(Perfect Binary Tree) : 모든 레벨이 꽉 찬 이진 트리.
• 완전 이진 트리(Complete Binary Tree) : 위 -> 아래 , 왼쪽 -> 오른쪽으로 순서대로 채워진 이진 트리.
• 정 이진 트리(Full Binary Tree) : 모든 노드가 0 or 2개의 자식 노드만을 갖는 이진 트리

 

이진 검색 트리(BST. Binary Search Tree)

• 이진 검색 트리는 데이터 저장 관련 특정 규칙이 있는 이진 트리이다. 

  • 이진 탐색 트리의 노드에 저장된 키는 유니크하다

  • 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

  • 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

  • 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

• AVL트리(Adelson-Velskii and Landis' tree) : 어떤 노드든 모든 자식의 깊이 차이가 1을 넘지 않도록 만든다.
• 보통 트리의 균형이 맞을 때에는 검색이나 삽입, 삭제할때 O (log n)의 시간이 소요된다.

---

Graph

그래프는 현실의 사물이나 추상적인 개념간의 연결관계를 표현한다. 그래프는 어떤 자료나 개념을 표현하는 노드와 노드들을 잇는 간선들로 구성된다. 트리도 그래프에 해당한다.(트리 = 사이클이 허용 되지 않는 그래프)

방향성이 있는 그래프를 Directed Graph, 방향성이 없는 그래프를 Undirected Graph라 한다.

• 사용예시 : 도시를 연결하는 도로망, 사람들간의 인간관계, 웹사이트간의 링크관계 등
• 종류 : directed graph, undirected graph, weight graph, multigraph(다중그래프 : 두 노드사이에 두개 이상의 간선이 있을 수 있는 그래프), bipartite graph(이분그래프 : 그래프의 노드들을 겹치지 않는 두개의 그룹으로 나눠서 서로 다른 그룹에 속한 노드들간에만 간선이 존재하도록 만들 수 있는 그래프)

그래프의 정점을 탐색하는 알고리즘

• 깊이 우선 탐색(DFS : Depth First Search)
  
  • 그래프 상에 존재하는 임의의 한 정점으로 연결되어 있는 한 정점으로만 나아간다는 방법을 우선으로 탐색한다
  • 사용하는 자료구조 : 스택
• 너비 우선 탐색(BFS : Breadth Fist Search)
  • 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. 
  • 사용하는 자료구조 : 큐

Minimum Spanning Tree(최소걸침나무. MST)

TODO : 경영 과학때 공부한 내용을 되살려보자. 추가 정리 예정 

가장 적은 비용으로 모든 노드를 연결하는 트리를 만드는 것이다. 특정 지역의 통신 선을 연결하기 위해 설비 배치 문제를 예시로 들 수 있다.