[자료구조] 트리, 그래프

[트리]

 

계층적인 자료구조이다.

노드와 간선으로 이루어져서 그래프의 일종으로 볼 수 있고 최소 연결 트리 라고도 불린다. (N=N, E=N-1)

간선의 비용은 따로 없고 사이클이 존재할 수 없다.

 

 

 

트리는 그래프의 일종이므로 인접 배열 또는 인접 리스트로 구현된다.

 

이진 트리, 이진 탐색 트리, 균형 트리(AVL, red-black), 최대/최소 힙 등이 있다.

 

트리의 순회

좌, 우의 순회를 재귀적으로 수행할 때 먼저 수행하면 전위 순회, 재귀함수 사이에 수행하면 중위 순회, 재귀함수 뒤쪽에 수행하면 후위 순회가 된다

 

트라이(trie, Prefix Tree) : n-차 트리의 변종. 각 노드에 문자를 저장하기 때문에 아래쪽으로 순회하면 단어 하나가 나온다.

접두사를 빠르게 찾아보기 위한 흔한 방식이다.

 

 

[그래프]

 

노드와 간선을 하나로 모아놓은 자료구조이다.

 

오일러 경로 : 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.

 

트리와 달리 부모/자식, 루트 노드라는 개념이 없다.

순회는 DFS 또는 BFS로 이루어진다.

무방향 또는 방향 그래프로 나뉜다. 여기에 가중치가 붙을수도 있다.

트리에서는 특정 노드 하나로 다른 모든 노드에 접근이 가능했지만 그래프는 그렇지 않을수도 있다.

 

인접 리스트 또는 인접 행렬로 구현된다.

보통 인접 리스트로 구현된다.

인접 행렬로 구현되는 경우 2차원 배열을 써야하기 때문에 공간 복잡도는 항상 O(N²)이다.