[C++ - TIL] 인접 리스트의 시각화 및 이진 탐색 트리(BST)의 안정적 삽입 설계

🎮 주제 : 인접 리스트의 시각화 및 이진 탐색 트리(BST)의 안정적 삽입 설계

태그 : #C++ #자료구조 #인접리스트 #이진탐색트리 #BST #포인터 #메모리관리

---

📌 학습 요약

• 인접 리스트 출력 시스템 : operator<< 오버로딩을 통해 각 정점과 연결된 노드들을 A : B -> C 형태로 시각화하여 그래프의 논리적 연결 상태를 직관적으로 확인
• BST 삽입 로직의 정교화 : 포인터가 nullptr인 지점에 데이터를 직접 대입하려는 오류를 수정하고, new 연산자를 통한 노드 생성과 부모 노드의 링크 갱신 과정을 정립
• 트리의 구조적 특징 파악 : 완전 이진 트리와 달리 한쪽으로 치우친 **편향 트리(Skewed Tree)**가 BST의 탐색 성능($O(n)$)에 미치는 부정적 영향 인지
• 방어적 프로그래밍 : 포인터 참조 전 nullptr 체크의 필수성을 체감하고, 동적 할당되지 않은 포인터에 값을 쓰려는 시도가 일으키는 런타임 크래시 예방

---

🛠 주요 코드 및 구현 상세

1. 인접 리스트 기반 Graph 출력 (friend operator<<)

friend ostream& operator<<(ostream& os, const Graph<T>& graph) {
    for (int i = 0; i < graph.size; i++) {
        os << graph.vertex[i] << " : ";
        // 리스트의 헤드부터 시작하여 null까지 순회
        typename Graph<T>::Node* currentNode = graph.list[i];
        while (currentNode != nullptr) {
            os << currentNode->data;
            if (currentNode->next != nullptr) os << " -> ";
            currentNode = currentNode->next;
        }
        os << endl;
    }
    return os;
}

2. BST insert() 함수의 안정적 구현

void insert(T data) {
    if (root == nullptr) {
        root = new Node{data, nullptr, nullptr};
        return;
    }
    
    Node* currentNode = root;
    while (true) {
        if (data < currentNode->data) {
            // 왼쪽 자식이 없으면 새 노드 생성 후 연결
            if (currentNode->left == nullptr) {
                currentNode->left = new Node{data, nullptr, nullptr};
                break;
            }
            currentNode = currentNode->left;
        } else {
            // 오른쪽 자식이 없으면 새 노드 생성 후 연결
            if (currentNode->right == nullptr) {
                currentNode->right = new Node{data, nullptr, nullptr};
                break;
            }
            currentNode = currentNode->right;
        }
    }
}

---

✅ 주요 문법 및 개념 정리

구분 인접 리스트 출력 BST insert

핵심 로직	선형 순회 (while)	조건부 분기 (if data < node)
주의 사항	typename 키워드로 의존 타입 명시	nullptr 체크 후 new 할당
성능 특징	간선 개수만큼 반복 ($O(E)$)	트리 높이만큼 탐색 ($O(h)$)
메모리	추가 공간 불필요 (조회만 수행)	새로운 노드 동적 할당 발생

💡 주의 : 포인터와 메모리 할당

• 실수 : Node* left = curr->left; left->data = data;
  • left가 nullptr인 상태에서 내부 멤버(data)에 접근하면 즉시 프로그램이 종료됨
• 정석 : 반드시 new Node(...)를 통해 실제 메모리 공간을 확보한 뒤, 그 주소값을 부모의 left나 right에 대입해야 함

---

느낀 점

• 코드를 쓸 때 nullptr 체크를 빼먹으면 치명적인 런타임 오류가 발생할 수 있다는 점을 다시 깊이 느꼈음
• 노드 생성 시 new Node 없이 포인터를 직접 접근하면 안 된다는 점을 실습을 통해 명확히 알게 됨
• 단순한 삽입 코드라도 포인터가 복잡하게 얽히면 디버깅이 매우 어려우므로 기초 설계부터 꼼꼼하게 해야겠다고 생각함
• C++의 operator<< 오버로딩을 활용하면 복잡한 자료구조를 시각적으로 보기 좋게 출력할 수 있어 개발 효율성이 높아짐을 체감함