비선형 자료구조

자료구조

---

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

 

 

 

 

비선형 자료구조

---

 

자료가 비선형으로 저장되어 있는 자료구조입니다.

비선형 자료구조의 종류는 다음과 같습니다.

 

그래프

정점과 간선으로 이루어진 자료구조입니다.

정점과 정점 사이에는 간선이 존재할 수 있고 여기에 정점간 이동을 위한 비용인 가중치가 있을 수 있습니다.

 

그래프는 뒤에 말할 비선형 자료구조의 토대가되는 자료구조입니다. 따라서 고정된 시간복잡도는 없습니다.

 

 

트리

그래프 중 하나로 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 계층적 데이터의 집합입니다.

위 그림과 같이 트리는 루트 노드, 내부 노드, 리프 노드로 이루어져 있고 노드의 규칙에 따라 종류가 나뉘어 집니다.

 

• 종류
  • 이진 트리
    • 어떤 노드가 있을 때 자신의 아래에 존재하는 노드를 자식 노드라고 합니다. 자식 노드의 수가 두개 이하인 트리를 이진 트리라고 합니다.
    • 보통 트리를 말할 땐 대부분 이진 트리입니다.
  • 완전 이진 트리
    • 왼쪽에서 부터 전부 채워져 있는 이진 트리입니다.
  • 이진 탐색 트리
    • 이진 탐색과 연결 리스트를 결합한 자료구조입니다. 
    • 이진 탐색의 효율적인 탐색 능력을 유지하면서, 자료 입력과 삭제가 연결 리스트의 빠른 속도로 가능합니다.
    • 노드의 오른쪽 하위 트리에는 ‘노드 값보다 큰 값’이 있는 노드만 포함되고, 왼쪽 하위 트리에는 ‘노드 값보다 작은 값’이 있는 노드만 포함됩니다.
    • 시간복잡도
      • O(logn) ~ O(n)
      • 최악의 경우 트리가 선형의 모양을 가져 시간복잡도가 O(n)이 됩니다.
  • AVL 트리
    • 이진 탐색 트리에서 최악의 경우인 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리입니다.
    • 시간 복잡도를 O(n)에서 O(logn)으로 개선했습니다.
  • 레드 블랙 트리
    • AVL 트리와 마찬가지로 스스로 균형을 맞추는 균형 이진 탐색 트리로 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용합니다.
    • 시간 복잡도는 마찬가지로 O(logn)입니다.
   

힙

이진 트리 기반의 자료구조이며, 최소힙과 최대힙 두 가지가 있습니다.

 

• 최소힙
  • 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다.
• 최대힙
  • 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 합니다.

이진 탐색 트리와 다르게 배열로 구현하며 시간 복잡도는 O(logn)입니다.

 

 

우선순위 큐

우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 먼저 제공되는 자료 구조입니다.

 

힙을 기반으로 구현하며 최소힙, 최대힙의 특성을 이용해 가장 작은 값이나, 가장 높은 갚. 즉, 힙에서 루트 노드를 최우선순위로 둡니다.

 

※ 잘못된 정보, 혹은 다른 의견이 있다면 댓글로 말해주세요. 감사합니다.