길자의 개발 오르막길

중복된 키 또는 값을 저장하는 컨테이너, 레드-블랙 트리 기반이라 항상 정렬된 상태로 유지됨multimap같은 키를 중복해서 저장할 수 있는 맵.즉, 하나의 키 → 여러 개의 value가 들어갈 수 있다.주요 함수insert(pair): 키-값 쌍 삽입erase(key): 키로 요소 제거find(key): 키로 요소 검색 (iterator 반환)equal_range(key): 동일한 키의 요소 범위를 반환샘플 코드#include #include using namespace std;int main() { multimap mm; mm.insert({1, "rtan"}); mm.insert({1, "goong"}); mm.insert({2, "tom"}); // 키가 1인 모든 원소..

트리가 자동으로 균형을 유지하도록 고안된 자기 균형 이진 탐색 트리각 노드를 Red 또는 Black루트는 Black모든 리프는 BlackRed 노드의 자식은 반드시 Black(Red 연속 불가)루트부터 리프까지 Black 노드 수는 동일 → 이를 Black-height 라고함새로 추가 되는 노드의 경우 Red위와 같은 규칙들이 트리의 높이를 최대 2·log₂(n) 수준으로 제한하여 최악 시간복잡도를 O(log n)으로 보장삽입 / 삭제 시 회전 횟수가 작고 안정적메모리 오버헤드가 적음표준 라이브러리 구현에 널리 채택됨c++ : map , set , multimap , multiset새로운 노드가 추가될 때 규칙에 맞춰 균형을 바꾸는데 이걸 회전(Rotation)이라 부른다

트리는 계층적(hierarchical) 데이터 구조로 여러개의 노드 가 부모-자식 관계로 연결 되 있는 자료 구조마치 나무가 땅에 뿌리를 내리고 가지를 뻗어나가는 것 처럼 트리도 하나의 root노드에서 시작해 여러개의 자식 노드를 가진다 A (루트) //0 level / \ B C //1 level / \ \ D E F //2 level 노드(Node)트리에 데이터를 저장하는 요소를 노드라 한다. 각 점이 노드간선(Edge)노드 간의 관계를 나타내는 선, 부모 자식관계를 연결 하는 선A-B , A-C, B-D 는 모두 간선레벨(Level)트리에서 루트로 부터 깊이 개념루트는 0레벨 루트의 자식은 +1레벨 루트(Root) 노드트리..

vector,list,deque 컨테이너는 시퀀스 컨테이너라 하며 순서가 있는 것을 의미하낟.map/set 검색과 중복 방지에 특화된 연관 컨테이너로 노드기반, 균형 이진 트리를 사용한다.레드-블랙 트리로 구현되어 있다. 레드-블랙 트리 (Red-Black Tree)트리가 자동으로 균형을 유지하도록 고안된 자기 균형 이진 탐색 트리각 노드를 Red 또는 Black루트는 Black모든 리프는 BlackRed 노드의 자식은 반드시 Black(Red 연속 불가)루트부터 리프까지 Black 노드codehortus.tistory.com map : key와 value 쌍을 저장하고 키를 통해 → 값을 빠르게 탐색 할 수 있는 자료 구조set : 키만 저장하고 중복은 허용하지 않는 구조map키와 값을 한쌍으로 묶어..