자료구조 구현하기(C++) - 비선형 자료구조

C++에서 다양한 자료구조는 STL(Standard Template Library) 컨테이너를 활용하여 간단하게 구현할 수 있습니다. 각 자료구조에 대해 어떤 STL 컨테이너를 사용할 수 있는지 설명하겠습니다.

---

대표적인 비선형 자료구조의 목록과 권장 STL 컨테이너를 요약하면 다음과 같습니다.

(가중치 그래프의 경우 std::map이나 std::unordered_map을 사용하여 각 간선에 가중치를 부여할 수 있습니다)

 

std::vector 관련 글

https://coding-potato-record.tistory.com/15

std::list 관련 글

https://coding-potato-record.tistory.com/18

std::set 관련 글

https://coding-potato-record.tistory.com/267

std::map 관련 글

https://coding-potato-record.tistory.com/28

std::queue 관련 글

https://coding-potato-record.tistory.com/23

---

 

1. 트리 (Tree)

(1) 이진 트리 (Binary Tree)

• 적합한 STL 컨테이너: C++ STL에는 기본적으로 이진 트리를 직접 구현하는 컨테이너는 없습니다. 이진 트리는 주로 노드 연결로 구현되므로, std::vector 또는 std::list와 같은 동적 배열을 사용하거나 직접 구조체와 포인터를 사용하여 트리를 구현해야 합니다.
• 구현 예시:

(2) 이진 검색 트리 (Binary Search Tree, BST)

• 적합한 STL 컨테이너: std::set 또는 std::map을 사용하여 이진 검색 트리를 구현할 수 있습니다. std::set은 내부적으로 이진 검색 트리를 사용하여 원소를 정렬된 상태로 저장합니다.
• 구현 예시:

(3) 힙 (Heap)

• 적합한 STL 컨테이너: std::priority_queue는 내부적으로 힙을 사용하여 구현됩니다. 기본적으로 최대 힙으로 동작하지만, 최소 힙으로 변경할 수도 있습니다.
• 구현 예시:

(4) AVL 트리

• 적합한 STL 컨테이너: STL에서 AVL 트리는 기본적으로 제공되지 않지만, std::map이나 std::set은 내부적으로 균형 잡힌 트리를 사용합니다. C++ STL에서 사용하는 트리 구조는 기본적으로 레드-블랙 트리이지만, AVL 트리와 유사하게 동작합니다.
• 구현 예시: std::map이나 std::set을 사용할 때, 자동으로 균형 잡힌 트리가 관리됩니다.

(5) B-트리, B+트리

• 적합한 STL 컨테이너: STL에는 직접적으로 B-트리나 B+트리를 구현한 컨테이너는 없지만, std::map과 std::set은 내부적으로 균형 잡힌 트리인 레드-블랙 트리를 사용합니다. B-트리 또는 B+트리를 직접 구현하려면, 자신만의 구조체를 만들고 포인터를 사용하여 트리를 관리해야 합니다.

2. 그래프 (Graph)

(1) 방향 그래프 (Directed Graph)

• 적합한 STL 컨테이너: std::vector 또는 std::list를 사용하여 그래프의 인접 리스트를 구현할 수 있습니다. 각 노드는 다른 노드를 가리키는 포인터를 가질 수 있습니다.
• 구현 예시:

(2) 무방향 그래프 (Undirected Graph)

• 적합한 STL 컨테이너: 방향 그래프와 동일하게 std::vector 또는 std::list를 사용하지만, 무방향 그래프의 경우 간선을 양방향으로 추가합니다.
• 구현 예시:

(3) 가중치 그래프 (Weighted Graph)

• 적합한 STL 컨테이너: std::map이나 std::unordered_map을 사용하여 각 간선에 가중치를 부여할 수 있습니다. std::vector 또는 std::list에 가중치 정보와 함께 인접 리스트를 저장할 수 있습니다.
• 구현 예시:

(4) 단방향 그래프 (Directed Acyclic Graph, DAG)

• 적합한 STL 컨테이너: 방향 그래프와 동일하게 std::vector 또는 std::list를 사용합니다. DAG의 경우 사이클이 없다는 특성을 가지고 있으므로, 간선을 추가할 때 사이클을 체크하는 로직이 필요할 수 있습니다.
• 구현 예시:

 

요약

• 트리와 그래프 자료구조는 대부분 C++ STL에서 제공하는 컨테이너(std::vector, std::list, std::set, std::map, std::priority_queue 등)를 조합하여 구현할 수 있습니다.
• 이진 트리, 이진 검색 트리, 힙, 그래프와 같은 자료구조를 구현할 때, STL 컨테이너를 적절히 선택하여 사용해야 합니다.
• C++ STL은 대부분의 기본적인 자료구조를 이미 제공하므로, 특별한 요구사항이 없으면 이를 활용하는 것이 효율적입니다.

STL 컨테이너 - vector