24.01.22 비선형 자료 구조 2

1. 비선형 자료 구조

    - 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

    - 일반적으로 트리나 그래프를 말함

 

  1) 힙

       - 완전 이진 트리 기반의 자료구조

       - 최소힙과 최대힙 두가지가 있고 해당 힙에 따라 특징을 지킨 트리

         * 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키중에서 가장 커야한다

                         각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이뤄져야 함

         * 최소힙 : 최소힙에서 루트노드에 있는 키는 모든 자식에 있는 키 중 최소값이어야 함

                         각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함

       - 힙에는 어떤 값이 들어와도 특정 힙의 규칙을 지키게 만들어짐

 

     (1) 최대힙의 삽입

           - 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입함

           - 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질은 만족시킴

           - 예) 아래와 같이 8이라는 값을 가진 노드 밑에 15라는 값을 가진 노드를 삽입하는 경우 점차 올라가면서

                   해당 노드 위에 있는 노드와 스왑하느 ㄴ과정을 거쳐 최대힙 조건을 만족함

 

     (2) 최대힙의 삭제

           - 최대힙에서 최대값은 루트노드이므로 루트노드가 삭제되고, 그 이후 마지막 노드와 루트노드를

             스왑하여 또다시 스왑 등의 과정을 거쳐 재구성 됨

 

  2) 우선순위 큐

       - 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다

         먼저 제공되는 자료 구조

       - 힙을 기반으로 구현됨

 

  3) 맵

       - 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조

       - 예) 이승철 : 1, 박동영 : 2 같은 방식으로 string : int 형태로 값을 할당해야 할때 map 을 하용

       - 레드 블랙 트리 자료구조를 기반으로 형성되고 삽입하면 자동으로 정렬

       - 해시 테이블을 구현할 때 쓰며 정렬을 보장하지 않는 unordered_map 과 정렬을 보장하는 map 두가지가 있다

 

  4) 셋

       - 특정 순서에 따라 고유한 요소를 저장하는 컨테이너

       - 중복되는 요소는 없고 오로지 희소한 값만 저장하는 자료구조

 

  5) 해시테이블

       - 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블

       - 삽입, 삭제, 탐색 시 평균적으로 O(1) 의 시간복잡도를 가지며 unordered_map 으로 구현