저번 시간에 이어, 이번엔 트리(Tree) 자료구조에 대해 알아보겠습니다.
Q: 트리 자료구조에 대해 설명해 주세요
노드와 간선들로 이루어진 자료구조로, 사이클이 없는 자료구조입니다. 즉, 루트에서 한 노드로 가는 경로는 유일합니다.
Q: 트리와 그래프의 차이가 무엇인가요?
사이클의 유무입니다. 그래프는 노드, 간선으로 이루어진 자료구조로 방향과 무방향이 존재하며, 트리는 그래프의 한 종류로써 방향성 있는 비순환 그래프입니다.
Q: 완전 이진 트리와 전 이진 트리, 그리고 포화 이진 트리에 대해서 설명해주세요.
- 완전 이진 트리란, 모든 레벨이 왼쪽을 우선으로 채워져 있는 트리이며,
- 전 이진 트리란, 모든 노드가 0개 혹은 2개의 자식 노드를 갖는 트리입니다.
- 그리고 포화 이진 트리란, 완전 이진 트리와 전 이진 트리의 조건을 동시에 만족하는 트리입니다.
Q: 신장 트리(Spanning Tree)와 최소 신장 트리(MST, Minimum Spanning Tree)란 무엇인가요?
신장 트리는 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 만들어진, 사이클이 없는 트리입니다. 최소 신장 트리는, 간선들의 가중치를 합한 값이 최소가 되도록 하는 트리입니다.
Q: 최소 신장 트리는 어떤 알고리즘으로 구하나요?
프림과 크루스칼 알고리즘입니다.
Q: 프림과 크루스칼은 어떤 차이가 있죠?
- 프림은 간선을 정렬하지 않고, 하나의 정점에서 시작하여 트리를 확장합니다. 선택한 정점에 인접한 모든 간선 중 가중치가 가장 낮은 간선을 연결하여 트리를 확장합니다.
- 크루스칼은 간선을 가중치별로 정렬하고, 가중치가 높은 간선을 제거하거나, 가중치가 낮은 간선을 삽입하는 과정을 거칩니다.
자료구조 추천 서적
트리 구조에 대해 다양하게 다룰 수 있는 책 3권 추천해 드립니다. 🙂
마치며
이번 시간에는 트리(Tree)자료구조와 그에 관련된 기초 내용들을 알아보았습니다.
다음 시간에는, BST(Binary Search Tree, 이진 탐색 트리)에 대해 알아보겠습니다.
“이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.”
답글 남기기