[자료구조 CS] 이진탐색트리, 맵, 해시테이블, 셋, 힙, 우선 순위 큐.

 

이진탐색트리

노드 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위트리에는 노드 값보다 작은 값이 들어있는 트리

-> 검색 용이.

요소를 찾을 때 일반적으로 O(logN)이 걸림. 최악의 경우는 O(n)이 걸림.

선형적인 경우 1을 찾으려면 최악으로는 모든 노드를 다 탐색해야 함-> O(N) 

AVL 트리

최악의 경우 선형적인 트리가 되는 것을 방지하고, 스스로 균형을 잡는 이진 탐색 트리. 

두자식 서브트리의 높이는 항상 최대 1만큼 차이난다.(높이 차가 0,1,-1 만 허용. 이를 벗어나면 회전이 필요)

• 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logN)이며, 삽입 삭제 마다 균형이 안맞는 ㄳ을 맞추기 위해 트리 일부를 
• 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡음.

BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이
출처:https://code-lab1.tistory.com/61[코드 연구소:티스토리]

레드 블랙트리

균형 이진탐색 트리. 모든 리프 노드와 루트 노드는 블랙이고, 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이라는 규칙을 기반으로 균형을 잡는다.

• 탐색, 삭제, 삽입 모두 O(logN)
• 빨간색 혹은 검은색 색상을 나타내는 추가 비트를 저장하며, 균형 유지에 사용.
• C++ STL의 set, multiset,map,and multimap이 레드 블랙 트리를 이용하여 구현됨. 

 

힙

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

최소힙과 최대힙이 있고, 해당 힙에 따라 특정한 특징을 지킨 트리.

• 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함.
• 최소힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 함. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함.

 

최대 힙의 삽입

1. 일단 새 노드를 힙의 마지막 노드에 이어서 삽입

2. 부모 노드들과 크기를 비교하며 교환.

최대 힙의 삭제

• 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.

1. 루트노드 삭제

2. 마지막 노드와 루트 노드를 스왑하여 재구성.

(이 교환 과정이 시간을 많이 잡아먹지는 않나?)

 

우선순위 큐

대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조. 

힙을 기반으로 구현

• greater -> 오름차순
• less -> 내림차순

 

맵

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

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

중복 x

map<string, int> 형태

map은 first, second가 있는 pair 객체로 저장되는 데 first- key로 second- value로 저장 

 

• clear() : 모든 요소 삭제
• size() : map 크기
• erase() : 해당 키에 매핑된 값 지움

해시 테이블 구현에 사용. 

• unordered_map : 정렬 보장 x
• map : 정렬 보장

 

셋

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

set<pair<string,int>> _set;
- pair는 두가지 형을 담을 수 있는 구조. first, second로 접근.

 

 

해시 테이블

무한에 가까운 데이터들을 유한한 개수의 해시( 해시의 의미: 임의값을 고정 길이로 변환하는 것 ) 값으로 매핑한 테이블. 

삽입, 삭제, 탐색에 O(1) unordered_map으로 구현.

 

 

?? 맵과 해시 테이블은 뭐가 다른 거지? 

https://dev-record.tistory.com/46

Hash Table과 Map은 언제 사용하면 좋을까?

1. Hash table은 멀티스레드에서 동기화를 지원할 수 있다.

2. Map은 항상 정렬된 상태로 데이터가 유지된다.

3. Hash는 Hash Function을 이용해 O(1)의 검색속도를, Map은 O(logN)의 성능을 지닌다.

 

다만 해시 테이블의 성능은 Hash Function에 지극히 의존적이기 때문에

사전에 Key의 분포를 알고 알맞는 Function을 작성할 수 있을때 사용하는것이 유용하다.

 

 

• Key
  • 고유한 값
  • 저장 공간의 효율성을 위해 Hash Function에 입력하여 Hash로 변경 후 저장
    • Key는 길이가 다양하기 때문에 그대로 저장하면 다양한 길이만큼 저장소 구성이 필요
• Hash Function
  • Key를 Hash로 바꿔주는 역할
  • 해시 충돌(서로 다른 Key가 같은 Hash가 되는 경우)이 발생할 확률을 최대한 줄이는 함수를 만드는 것이 중요
• Hash
  • Hash Function의 결과
  • 저장소에서 Value와 매칭되어 저장
• Value
  • 저장소에 최종적으로 저장되는 값
  • 키와 매칭되어 저장, 삭제, 검색, 접근 가능

• HashTable 동작 과정
  1. Key -> Hash Function -> Hash Function 결과 = Hash
  2. Hash를 배열의 Index로 사용
  3. 해당 Index에 Value 저장
  • HashTable 크기가 10이라면 A라는 Key의 Value를 찾을 때 hashFunction("A") % 10 연산을 통해 인덱스 값 계산하여 Value 조회

• Hash 충돌
  • 서로 다른 Key가 Hash Function에서 중복 Hash로 나오는 경우
  • 충돌이 많아질수록 탐색의 시간 복잡도가 O(1)에서 O(n)으로 증가

• HashTable 단점
  • 충돌 발생 가능성
  • 공간 복잡도 증가
  • 순서 무시
  • 해시 함수에 의존
• HashTable vs HashMap
  • Key-Value 구조 및 Key에 대한 Hash로 Value 관리하는 것은 동일
  • HashTable
    • 동기
    • Key-Value 값으로 null 미허용 (Key가 hashcode(), equals()를 사용하기 때문)
    • 보조 Hash Function과 separating Chaining을 사용해서 비교적 충돌 덜 발생 (Key의 Hash 변형)
  • HashMap
    • 비동기 (멀티 스레드 환경에서 주의)
    • Key-Value 값으로 null 허용
• 충돌 문제 해결
  1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
  2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)
  3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
  4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Hash.md

https://github.com/WeareSoft/tech-interview/blob/master/contents/datastructure.md#hashtable

 

 

각 장단점, 사용처, 시간복잡도 등 이해 필요.