[C++ - TIL] 해시 테이블 안정화, 레드-블랙 트리 기초 및 그래프 구조 이해

🎮 주제 : 해시 테이블 안정화, 레드-블랙 트리 기초 및 그래프 구조 이해

태그 : #C++ #자료구조 #해시테이블 #레드블랙트리 #그래프 #동적배열

---

📌 학습 요약

1. 해시 테이블 소멸자 : 체이닝 구조에서 모든 버킷의 연결 리스트 노드를 전수 조사하여 해제하고, 최종적으로 버킷 배열까지 삭제하는 완전한 메모리 관리 로직 구현
2. 참조 반환의 위험성 : 연산 결과로 생성된 임시값(R-value)을 참조(&)로 반환할 때 발생하는 댕글링 참조 문제를 파악하고, 값 반환(Return by Value)의 안전성 확인
3. 레드-블랙 트리(RBT) : 다섯 가지 핵심 규칙을 통해 자가 균형을 유지하는 이진 탐색 트리의 원리와 높이 균형의 중요성 습득
4. 그래프(Graph)의 표현 : 정점과 간선의 관계를 인접 행렬(밀집 그래프)과 인접 리스트(희소 그래프)로 표현하는 방식의 차이 및 공간 효율성 분석
5. 2차원 동적 할당 : 포인터의 포인터(int**)를 이용한 수동 할당 방식과 현대적인 std::vector를 이용한 안전한 행렬 생성 방식 비교

---

🛠 주요 코드 및 구현 상세

1. 안전한 해시 테이블 소멸자

~HashTable() {
    for (int i = 0; i < size; i++) {
        Node* current = bucket[i].head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current; // 개별 노드 메모리 해제
            current = next;
        }
    }
    delete[] bucket; // 버킷 배열 자체 해제
}

2. 현대적인 2차원 배열 관리 (Vector)

#include <vector>

// 3행 4열 행렬을 생성하고 0으로 초기화
int rows = 3, cols = 4;
std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols, 0));

// 사용 예시: matrix[1][2] = 10;
// 별도의 delete 과정 없이 범위를 벗어나면 자동으로 메모리 해제

---

✅ 주요 문법 및 개념 정리

자료구조 핵심 특징 시간 복잡도 (탐색)

해시 테이블	키-값 매핑, 충돌 시 체이닝 활용	평균 $O(1)$, 최악 $O(n)$
레드-블랙 트리	자가 균형, 엄격한 5규칙 적용	항상 $O(\log n)$
인접 행렬	2차원 배열 활용, 연결 여부 즉시 확인	$O(1)$
인접 리스트	연결된 정점만 저장, 공간 효율적	$O(Degree(V))$

⚠️ C++ 실무 팁 : 값 반환 vs 참조 반환

• 잘못된 예 : const float& getRatio() { return count / capacity; }
  • 함수가 종료되면서 계산된 임시값이 소멸하므로, 반환된 참조는 쓰레기값을 가리키게 됨
• 올바른 예 : float getRatio() const { return (float)count / capacity; }
  • 기본 자료형(int, float 등)은 값으로 반환하는 것이 훨씬 빠르고 안전함

---

✨ 느낀 점

• 자료구조에 대한 정확한 개념 이해 없이 구현만 하면 메모리 누수나 런타임 오류라는 위험이 따름을 실감함
• 특히 소멸자나 참조 반환처럼 C++에서 자주 실수하는 메모리 관련 이슈를 정리하며 언어의 깊은 원리를 파악함
• 그래프, 트리, 해시 등 각 자료구조가 별개가 아니라 데이터의 효율적 관리라는 목적 아래 상호 연결되어 있음을 이해함
• 수동적인 2차원 배열 할당보다 std::vector를 사용하는 방식이 코드의 안정성과 가독성을 얼마나 높여주는지 다시금 체감함