gksrudtlr
|2025. 2. 6. 02:48
Map & Set
- Map
- Map이란?
- key, value을 한 쌍으로 묶어서 관리
- 키는 유일하며 검색 삽입 삭제가 평균적으로 O(logN)
- 이는 내부적으로 이진 탐색트리중 레드블렉트리로 구현되어있기 때문
- 주요함수
- insert(pair) : 키 값 쌍 삽입
- erase(key) : 키로 요소 제거
- find(key) : 키로 요소 검색(iterator 반환)
- key가 있으면 해당 key의 iteraor를 반환하나 없으면 end()를 반환
- operator[key] : 키로 값에 접근 또는 삽입
- size() : 요소의 개수를 반환
- Set
- Set이란?
- 키만 저장, 즉 value가 따로 필요 없을때 사용
- 중복이 불가능하며 이미 원소가 존재하면 다시 넣어도 들어가지 않음
- 검색 삽입 삭제가 평균 O(logN)
- 내부적으로 레드블렉트리를 이용하여 구현되어 있지만 키만 존재함
- 주요 함수
- insert(value) : 요소의 추가
- erase(value) : 요소 제거
- find(value) : 요소 검색(iterator 반환)
- size() : 요소 개수 반환
- lower_bound(value) : 지정된 값 이상의 첫번째 요소 반환
- upper_bound(value) : 지정된 값 보다 큰 첫번째 요소 반환
multimap, multiset
- multimap
- 정의
- 주요함수
- insert(pair) : 키-값 쌍 삽입
- erase(key) : 키로 요소 제거
- find(key) : 키로 요소 검색(iterator)
- equal_range(key) : 동일한 키의 요소 범위를 반환
- multiset
- 정의
- 주요함수
- insert(value) : 요소 추가
- erase(value) : 요소 제거
- find(value) : 요소 검색(iterator 반환)
레드 블렉 트리
- 레드 블렉 트리란?
- 이진 탐색 트리의 일종으로 편향되지 않고 트리의 높이를 logN으로 유지하는것이 매우 중요
- 노드가 빨간색인지 검은색인지 판단하여 균형잡힌 트리를 만들어 탐색 속도가 빨라짐
- 규칙
- 균형을 이뤄야함
- 깊이를 기준으로 검은 리본의 갯수가 어디서나 같아야함(균형 유지)
- 빨간 리본이 이어지면 안됨
- 빨간 리본을 단 나무가 연달아 나오면 재배치
- 이 규칙 덕분에 균형을 이루게됨
- 최상위 부모 노드는 검은색이어야함
- 데이터 추가
- 새로 추가하는 노드는 빨간색
- 새로 추가하는 노드는 무조건 빨간색이며, 두번째 조건에 충족하기 위해 나무의 위치를 바꿔서 균형을 맞춰야함
- 데이터 삭제
- 검은색 리본이 없어지면 같은 층의 검은 리본 개수가 깨질 수 있어 나무의 위치를 조정하거나 리본 색을 바꿔가며 균형을 유지해야함
- 이를 통해 항상 균형잡힌 상태를 유지 가능
