[이진트리] map, set c++ 구현

 

목차

 

 

 

들어가기전

https://be-senior-developer.tistory.com/17

[이진트리] 기본 c++구현 및 이진 트리 순회 설명(전위, 중위, 후위)

위 글에서 기본적인 이진트리의 설명을 보고 오시면 이해하는데 도움이 될 것 같습니다!

 

 

 

 

Map에 대한 설명

• map은 각 노드가 key와 value로 이루어진 트리입니다. 주요한 특징은 중복을 허용하지 않습니다.
• map은 first , second로 이루어진 pair 객체로 저장되게 됩니다.
• map은 검색, 삽입, 삭제의 시간복잡도가 o(logn)인 레드블랙트리로 구성됩니다.

여기서 레드블랙트리란 자가 균형 이진 탐색 트리로 최악의 경우까지 고려해

만들어낸 다소 복잡한 트리라고 할 수 있습니다

 

 

 

 

 

 

 

 

 

이미지 출처: https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

 

 

map의 간단 사용법

#include <iostream>
#include<map>

using namespace std;
//map 간단 사용법
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    map<string, int> m; // 기본구조: map <key type, value type> 이름 

    m.insert(make_pair("abc", 1)); //값 넣기

    for (auto iter = m.begin(); iter != m.end(); iter++) //반복문으로 데이터 접근하기
    {
        cout << iter->first << " " << iter->second << endl;  //first, second로 접근
    }
    if (m.find("abc") != m.end()) {   //데이터를 끝까지 못찾으면 map.end() 반환
        cout << "find" << endl;
    }
    else {
        cout << "not find" << endl;
    }

    m.erase("abc"); //key값을 기준으로 삭제

    m.clear(); //모든 요소 삭제

}

 

 

 

map을 이용한 트리 구현

#include<iostream>
#include<map>
using namespace std;

map<char, pair<char, char> > tree;

void preOrder(char node) // 전위 순회 
{
	cout << node;
	if (tree[node].first != '*') preOrder(tree[node].first);
	if (tree[node].second != '*') preOrder(tree[node].second);
}

void inOrder(char node) // 중위 순회
{
	if (tree[node].first != '*') inOrder(tree[node].first);
	cout << node;
	if (tree[node].second != '*') inOrder(tree[node].second);
}

void postOrder(char node) // 후위 순회
{
	if (tree[node].first != '*') postOrder(tree[node].first);
	if (tree[node].second != '*') postOrder(tree[node].second);
	cout << node;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n;
	char left, right, data;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> data >> left >> right; 
		tree[data] = make_pair(left, right);    // 왼쪽 오른쪽 쌍으로 넣기
	}
	
	

}

 

 

 

 

set에 대한 설명

• set은 map과 달리 key로만 이루어진 트리입니다. set또한 중복을 허용하지 않습니다
• set은 검색, 삽입, 삭제의 시간복잡도가 o(logn)인 레드블랙트리로 구성됩니다.
• 중복 원소를 허용하고 싶다면 multiset을 사용하면 됩니다.

 

set의 간단 사용법

map과 유사한 것을 볼 수 있다

#include <iostream>
#include <set>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    set<string> s; // 기본 구조 set<key type> 이름

    s.insert("abc"); // 값 넣기

    for (auto iter = s.begin(); iter != s.end(); iter++) {  //반복문으로 데이터 접근하기
        cout << *iter << endl; // 값에 직접 접근
    }

    if (s.find("abc") != s.end()) {   //데이터를 끝까지 못찾으면 map.end() 반환
        cout << "find" << endl;
    }
    else {
        cout << "not find" << endl;
    }

    s.erase("abc");    //key값을 기준으로 삭제

    s.clear();   //모든 요소 삭제

}

 

 

set은 그 자체로 이진 탐색 트리의 특성을 제공하므로, set으로 트리를 구현하지 않아도

필요한 기능을 사용하여 데이터를 삽입, 삭제, 검색할 수 있다

 

 

참고

https://headf1rst.github.io/c++/binaryTree-using-map/

[C++] 포인터 없이 map으로 이진트리 만들기 $($+ 전위, 중위, 후위 순회)