트리와 그래프

트리

트리는 루트 노드를 가지는 계층적 구조의 자료구조 입니다.

루트 노드로 부터 하위 노드로 연결되어지며 사이클이 없습니다. 비순환적 그래프로 볼 수 있습니다.

임의의 2개의 노드 사이에는 하나의 경로가 존재합니다.

트리의 노드는 자식 노드를 1개 이상 가질 수 있습니다. 

 

트리를 기반으로 이진 트리, 힙 트리, b 트리 등의 다양한 자료구조를 만들 수 있습니다.

 

그래프

 

그래프 비선형 데이터 구조로, 여러 개의 노드와 이를 연결하는 간선으로 구성됩니다.

노드 간에는 부모-자식 관계가 없습니다. 각각의 노드들은 간선으로 연결 될 수도 있습니다.

간선을 가지기 때문에 무방향, 단방향, 양방향 그래프등의 다양한 그래프가 존재합니다.

그래프는 사이클을 가질 수 있습니다. 노드 간에 복잡한 형태를 그래프로 표현 가능합니다.

 

그래프는 인접 행렬, 인접 리스트를 기반으로 만들 수 있고 인접 행렬을 기반으로 그래프를 생성하면 메모리를 더 사용한다는 단점이 있지만 간선의 존재 여부를 상수 시간에 빠르게 확인 가능합니다.

인접 리스트를 기반으로 그래프를 생성하면 메모리를 적게 사용하여 간선이 있는 노드들끼리만 연결한다는 장점이 있지만, 간선의 존재 여부를 확인 할 때 리스트를 탐색해야한다는 단점이 있습니다.