5.3 비선형 자료 구조

코난·2024년 11월 27일

CS 면접 정리

목록 보기

65/67

그래프

여러 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조로, 정점간의 관계를 표현한 조직도이다. 두 정점 사이를 이어주는 간선과 정점으로 이루어진다.
즉, 정점과 그 정점을 연결하는 간선을 하나로 모아 놓은 자료 구조다.

정점 : 데이터가 저장되는 그래프의 기본 원소
간선 : 정점 간의 관계를 나타내는 선

방향 그래프 VS 무방향 그래프

방향 그래프

두 정점을 연결하는 간선에 방향이 없는 그래프이다.

무방향 그래프

두 정점을 연결하는 간선에 방향이 있는 그래프이다.

가중치 그래프

간선에 비용이나 가중치가 할당된 그래프이다.

연결 그래프 VS 비연결 그래프

연결 그래프

그래프에서 모든 노드가 최소한 하나의 경로로 연결된 그래프이다.

비연결 그래프

그래프에서 일부 노드가 다른 노드와 연결되지 않은 그래프이다.

순환 그래프 VS 비순환 그래프

순환 그래프

그래프에 사이클이 존재하는 그래프로 한 노드에서 시작하여 다시 해당 노드로 돌아올 수 있는 경로(사이클)이 있는 그래프이다. 적어도 한 개 노드에서 시작하여 다른 노드들을 거쳐 다시 자기 자신으로 돌아오는 경로를 가지는 그래프이다.

비순환 그래프

그래프에 사이클이 존재하지 않는 그래프로 한 노드에서 시작하여 해당 노드로 돌아오는 경로가 없는 그래프이다. 어떠한 경로도 자기 자신으로 돌아오지 않는 순환이 없는 그래프이다.

트리

그래프의 일종으로 방향성이 있는 연결된 비순환 그래프이다. 하지만 일반 그래프와는 달리, 계층 구조를 가진다는 특수성이 있다.

트리의 특징

트리는 사이클이 없는 비순환 구조이다.
- 한 정점에서 출발하여 다시 자기 자신으로 돌아오는 경로가 존재하지 않는다.
하나의 루트 노드와 0개 이상의 하위 트리를 가진다.
- 루트 노드는 반드시 하나여야 하며, 두 개가 될 수 없다.
모든 노드는 단 하나의 부모 노드를 가진다.
- 루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가져야 한다.
노드는 N개인 트리는 항상 N-1개의 간선을 가진다.
- 간선은 항상 정점의 개수 - 1 만큼을 가진다.
모든 노드로 갈 수 있는 경로는 루트 노드를 거쳐야만 가능하다.
- 다른 노드들이 모든 경로를 지나기 위해서는 반드시 루트 노드를 거치는 구조를 가진다.

이진트리

자식 노드의 개수가 두 개 이하인 트리를 말한다.

정 이진 트리 : 자식 노드가 0 또는 2개인 이진 트리
완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진 트리로 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있는 트리
변질 이진 트리 : 자신 노드가 하나밖에 있는 이진 트리
포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리로 반드시 노드의 개수가 2^(h + 1) - 1의 개수를 가짐
균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리

이진탐색트리

탐색을 위한 이진 트리의 일종으로 특수한 노드 값을 가지는 형태의 이진 트리를 말한다.

왼쪽 노드에는 부모 노드보다 작은 값이 저장되고 오른쪽 노드에는 부모 노드보다 큰 값이 저장된다. 또한 모든 노드는 중복된 값을 가지지 않는다.
비선형적인 구조로 잘 만들어진 이진탐색트리는 O(log n)의 시간 복잡도를 가지지만 데이터 삽입 순서에 따라 선형적인 구조를 가지게 된 경우에는 최악의 경우 O(n)의 시간복잡도를 가지게 될 수도 있다.

AVL 트리

균형 이진 트리의 일종으로 이진 탐색 트리에 균형 트리의 특징을 넣은 트리를 말한다.
이진 탐색 트리와 같은 특징을 가지고 있지만, ACL 트리는 균형 트리의 특징을 가져 서브 트리의 좌, 우 높이 차이가 1을 초과하지 않도록 동작한다.
AVL 트리는 항상 균형을 맞춰 높이를 유지하기 때문에 평균, 최악의 경우 모두 시간 복잡도를 O(log n)을 가지게 된다.