자료구조 관계도

mindmap
  root((자료구조<br/>68개 토픽))
    기초 개념
      자료 구조
      추상 자료형
    선형 구조
      배열 기반
        배열
        동적 배열
        원형 버퍼
        비트맵
      리스트 기반
        연결 리스트
        이중 연결 리스트
        원형 연결 리스트
        다중 연결 리스트
        XOR 연결 리스트
        스킵 리스트
      특수 리스트
        Rope
      스택/큐
        스택
        큐
        덱
        우선순위 큐
        Lock-Free Queue
    트리 구조
      기본 트리
        트리
        이진 트리
        이진 트리 순회
        트리 종류
      탐색 트리
        이진 탐색 트리
        AVL 트리
        Red-Black 트리
        스플레이 트리
        Treap
        Cartesian Tree
        AA 트리
      다진 트리
        2-3 트리, 2-3-4 트리
        B-트리
        B+트리
        Copy-on-Write B-Tree
        LSM 트리
      힙
        힙
        피보나치 힙
        이항 힙
      특수 트리
        트라이
        Radix Tree
        Suffix Tree/Array
        세그먼트 트리
        Lazy Propagation
        Fenwick 트리
        Van Emde Boas Tree
        Dancing Links
      공간 분할 트리
        쿼드트리
        KD-Tree
        R-Tree
    그래프
      그래프
      그래프 표현 방식
      탐색 알고리즘
        DFS
        BFS
      집합 연산
        유니온 파인드
    해시 기반
      해시 테이블
      Hash Collision Resolution
      Open Addressing 심화
      해시 함수 설계
      확장성 해싱
      ConcurrentHashMap
    확률적 자료구조
      필터
        블룸 필터
        Cuckoo Filter
      카운팅
        Count-Min Sketch
        HyperLogLog
    캐시/메모리
      LRU 캐시
    분산/저장소
      SSTable
      Consistent Hashing
      Merkle Tree
    고급 개념
      Persistent Data Structure

배열 (정적) → 동적 배열 (가변)
          → 연결 리스트 → 이중 연결 리스트
                      → 원형 연결 리스트
                      → 다중 연결 리스트
                      → 스킵 리스트

기본: 스택, 큐
  ↓
확장: 덱 (양방향)
  ↓
우선순위: 우선순위 큐 (힙 기반)
  ↓
동시성: Lock-Free Queue

BST (기본, 불균형 가능)
  ↓
균형 트리
  ├─ AVL 트리 (엄격한 균형, 높이 차이 1)
  ├─ Red-Black 트리 (느슨한 균형, 실용적)
  ├─ 스플레이 트리 (자가 조정, 최근 접근 빠름)
  ├─ Treap (랜덤 우선순위)
  └─ Cartesian Tree (최소 힙 + BST 결합)

트리 (일반)
  ↓
이진 트리
  ├─ 트리 종류 (완전/포화/편향)
  └─ 이진 트리 순회 (전위/중위/후위/레벨)
      ↓
  이진 탐색 트리 (BST)

B-트리 (내부 노드 데이터 포함)
  ↓
B+트리 (리프 노드만 데이터, DB 인덱스)
  ↓
Copy-on-Write B-Tree (불변 스냅샷, 트랜잭션)

1D: 이진 탐색 트리
  ↓
2D: 쿼드트리 (4분할)
  ↓
kD: KD-Tree (k차원)
  ↓
공간 객체: R-Tree (MBR 기반)

트라이 (Trie) - 접두사 검색
  ↓
Radix Tree (압축 트라이, 메모리 효율)
  ↓
Suffix Tree/Array - 부분 문자열 검색
  ↓
Rope - 긴 문자열 편집

세그먼트 트리 (완전 이진 트리, 구간 합/최소/최대)
  ├─ Lazy Propagation (구간 업데이트 최적화)
  ↓
Fenwick 트리 (BIT, 누적 합, 메모리 효율)

해시 함수 설계 (기반 이론)
  ↓
해시 테이블 (기본)
  ├─ Hash Collision Resolution (체이닝, 개방 주소법)
  │   └─ Open Addressing 심화 (선형/이차/이중 해싱)
  ├─ 확장성 해싱 (동적 확장)
  └─ ConcurrentHashMap (동시성 지원)

멤버십 테스트
  ├─ 블룸 필터 (존재 여부, False Positive)
  └─ Cuckoo Filter (삭제 지원)

카운팅/집계
  ├─ Count-Min Sketch (빈도 추정)
  └─ HyperLogLog (카디널리티 추정)

LSM 트리 (쓰기 최적화)
  └─ SSTable (정렬된 불변 파일, LSM 구성요소)

Consistent Hashing (분산 키 분배)

Merkle Tree (데이터 무결성 검증, 블록체인)

Copy-on-Write B-Tree (트랜잭션 안전 스냅샷)