그래프와 트리의 차이점/ 이진트리, 힙, 이진검색트리 설명

1. 그래프와 트리를 설명하고 차이점

네트워크 모델인 그래프는 노드와 노드 간을 연결하는 간선으로 구성된 자료구조이다. 순환 또는 비순환 구조를 이루며, 방향이 있는 그래프와 방향이 없는 그래프가 있고 부모-자식 관계라는 개념이 없으며 2개 이상의 경로가 가능하다.  계층형 모델인 트리는 그래프 중에서도 특수케이스에 해당하며 반드시 1대의 경로만을 가지고 사이클이 존재하지 않는 방향 그래프이다. 부모-자식관계가 성립하고 노드가 n이면 간선은 n-1개,이며 전위/중위/후위순회 3가지 종류가 있다. 대표적인 그래프는 네비게이션의 최단거리, 트리는 폴더구조 생각하면 편하다.

 

2. 이진트리, 이진검색트리, 힙의 차이점

이진트리는 각 노드가 최대 2개의 자식노드만을 가질 수 있는 트리이다. 이진 검색트리는 자료들을 일정한 순서에 때라 정렬한 상태로 저장하며 검색트리는 이 점을 이용해 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부확인 등의 다양한 연산을 빠르게 수행한다. 가장 흔하게 사용되며 각 노드의 왼쪽 서브트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이 오른쪽 서브트리에는 보다 큰 원소를 가진 노드들이 들어간다. 마지막으로 힙은 가장 크거나 작은 원소를 찾는 데에 최적화되어 있다.새 원소를 추가하는 연산과 가장 크거나 작은 원소를 꺼내는 연산을 모두 O(logN) 시간에 수행할 수 있다. 힙은 특정규칙(대소관계)을 만족하도록 구성된 포화 이진 트리 or 완전 이진 트리이다.