C++ 기초 : tree (4)

---

Red - Black tree라는 자가 균형 기능이 들어간,

이진 탐색 트리 기반의 자료 구조로는 'set'이 있습니다.

 

아래 코드가 set의 사용 예시인데요,

 

우선 include 지시문을 통해 set을 포함시킵니다.

 

set이라는 클래스 템플릿 또한 std라는 namespace에

구현이 되어 있기 때문에 바로 사용하기 위해 

using std::set; 코드를 쓰겠습니다.

 

 

그리고 main 함수에서 int형 데이터를

관리하는 set을 생성해 줬습니다. 

 

 

이후 insert 함수를 통해

100과 50, 75를 삽입해 줬습니다.

 

 

set의 구조는 아래 그림과 같을 겁니다.

 

처음 들어온 데이터인 100이 루트 노드가 되고

이후 들어온 50은 100보다 작으므로 왼쪽,

150은 100보다 크므로 오른쪽 자식 노드가 되죠.

 

 

물론 이러한 노드들은 set 클래스를 통해 

만든 객체 안에 들어 있는 게 아니라

heap 영역에 동적 할당된 공간에 

노드들이 있고 이것을 set 클래스를 통해 

만든 객체가 가리키고 있는 겁니다.

 

 

---

 

 

 

사실 set 클래스보다는

map 클래스가 더 많이 쓰입니다. 

 

아래 코드를 보시죠.

 

map 클래스를 사용하기 위해서 

include 지시문을 통해 map 파일을 포함시키고

map 역시 std라는 namespace에 구현되어 있기 때문에

바로 사용할 수 있도록 using std::map; 코드를 적어 줍니다.

 

map은 typename을 두 개 지정해 줘야 합니다. 

18번째 줄처럼 말이죠.

 

첫 번째 typename이 의미하는 것은

map이 관리하는 노드의 키-값의 자료형을 의미합니다.

 

두 번째 typename이 의미하는 것은

map이 관리하는 노드의 실질적으로 들어가 있는 

데이터의 자료형을 의미합니다.

 

 

예를 들어 map으로 학생 데이터를 관리한다고 합시다.

정렬 기준을 이름으로 하고

학생 데이터는 이름과 나이, 성별을 포함하죠.

 

이러한 상황을 map으로 구현하면 

아래 코드와 같습니다.

 

우선 tStdInfo라는 이름의 구조체를 만들었습니다.

 

학생 데이터를 담기 위한 구조체입니다.

 

이름과 나이 성별을 담기 위한 변수를 만들어 줍니다.

나이는 어차피 많아야 200 밑이기 때문에

1Byte인 char형으로 선언하고 나이를 담는 변수에

음수는 필요 없기 때문에 unsigned로 선언합니다.

그래도 0 ~ 255까지 표현할 수 있죠.

 

 

19 ~ 20번째 줄에 있는

define 지시문을 통해 알 수 있듯이

1과 2를 통해 성별을 구분할 것이므로 

성별 또한 unsigned char형으로 선언합니다.

 

이렇게 define 지시문을 통해 MAN이라는 키워드를 보면

실제로는 1로 인식되지만 코드를 보는 사람 입장에서는 가독성이

좋아질 겁니다. 마찬가지로 WOMAN이라는 키워드는 

실제 2로 인식되지만 가독성이 좋아지겠죠.

 

그리고 만약 정수 3을 MAN이라고 인식하도록

바꾸고 싶다면 define 지시문 쪽에서 숫자만

바꿔 주면 실제 MAN이라는 키워드가 사용된 곳들은

수정할 필요 없이 알아서 적용이 될 겁니다.

 

 

그리고 C++에서는 구조체도 

클래스와 같은 역할을 하기 때문에 

생성자와 소멸자를 만들어 줄 수 있습니다.

 

기본 생성자의 경우 모든 변수를 0으로 초기화합니다.

 

인자를 받는 경우도 생성자를 오버로딩하여 구현할 수 있습니다.

이 경우 문자열과 정수 두 개를 받아

각각 이름, 나이, 성별을 표현하는 변수에 대입해 줍니다.

 

특히 문자열은 ROM(Read-Only Memory)에 있기 때문에

이를 포인터로 받으려면 문자열이 수정되지 않도록

const 키워드를 붙여야 합니다. 

 

또한 문자열을 저장하는 구조체 멤버를 초기화할 때

이니셜라이저를 통해 하려고 하면 작동하지 않습니다.

 

그래서 wcscpy_s 함수를 통해 멤버 변수에 문자열을

복사해 줍니다. 

 

 

이제 main 함수에서 map 클래스 템플릿을 통해 

객체를 하나 만듭니다. 

 

이름을 통해 각 노드를 식별하겠습니다.

따라서 첫 번째 typename은 이름과 같은 자료형인

const wchar_t형 포인터로 해 주고,

 

해당 노드가 실질적으로 갖고 있는 데이터의 자료형을

나타내는 두 번째 typename은 tStdInfo로 하겠습니다.

 

 

이후 두 개의 학생 데이터를 만들어 줍니다.

 

이 두 개의 학생 데이터를 map의 insert 함수를 통해 

삽입해 줄 건데 52 ~ 53번째 줄을 보시면

make_pair라는 함수가 나옵니다. 

해당 함수의 인자로 이름과 학생 데이터를 넘겼는데요,

받은 두 개의 데이터를 하나의 pair로 묶어 주는 겁니다. 

 

이렇게 만든 pair를 insert 함수를 통해 삽입하였으니

map이 관리하는 노드에는 pair가 저장되어 있는 거죠.

 

 

---

 

 

아래 코드에서

 

56번째 줄을 보시면 find 함수가 있습니다.

 

map이 관리하는 특정 노드를 반환하는 함수입니다.

위 코드 같은 경우 키-값이 문자열 "이민수"인 것을

찾아 주는 거죠.

 

find 함수는 찾은 노드의 어떤 데이터를 반환하는 게 아니라

iterator를 반환합니다. 찾은 노드를 가리키는

iterator를 반환하는 것이죠.

 

그래서 find 함수의 반환값을 만들어 놓은 iterator에

대입할 수 있는 겁니다.

 

실행한 후 iterator의 값을 확인해 보면

 

find 함수를 통해 찾은 키-값이 "이민수"인

노드의 데이터가 대입된 것을 확인할 수 있습니다. 

 

 

 

---

 

 

 

 

 

iterator는 키-값이 "이민수"인 노드를

가리키고 있는 상황입니다.

 

근데 노드 안은 pair로 구성되어 있죠.

즉 두 개의 데이터가 하나로 묶여 있습니다.

 

예상해 보자면 make_pair 함수가 호출되면서

이때 넘긴 인자로 인해 pair라는 템플릿을 거쳐

pair<const wchar_t* , tStdInfo>형 객체가 만들어졌을 겁니다.

 

struct pair
{
const wchar_t* p;
tStdInfo info;
};

 

더 큰 pair라는 구조체 안에 

직접 만든 tStdInfo 구조체가 멤버로 있는 거죠.

 

그래서 실질적인 데이터를 얻고 싶다면

노드에 접근만 하면 되는 게 아니라

노드에 있는 pair의 멤버에 접근을 해야 하는 겁니다.

 

 

struct pair
{
const wchar_t* fist;
tStdInfo second;
};

 

위 코드처럼 pair가 갖고 있는 첫 번째 데이터를

first, 두 번째 데이터를 second로 

이름이 정해져 있습니다.

 

 

이제 58 ~ 59번째 줄이 의미하는 것을 알겠죠?

 

키-값이 "이민수"인 노드를 가리키는 iterator에 

접근하여 first라는 이름을 가진 멤버에 접근하는 겁니다.

first는 문자열 "이민수"를 가리키는 포인터죠.

 

그리고 키-값이 "이민수"인 노드를 가리키는 iterator에 

접근하여 second라는 이름을 가진 멤버에 접근하는 겁니다.

second는 학생 데이터를 저장하고 있는 멤버이므로

학생 데이터를 얻어낼 수 있는 겁니다.

 

 

iterator는 마치 포인터처럼 작동하도록

구현되어 있습니다. 그렇기 때문에 iterator가 가리키는 

노드를 역참조하여 접근하고, 여기서 멤버에 접근하는 경우

-> 로 접근하는 것이 가능합니다.

 

그래서 위 코드처럼 ->를 통해 노드에 저장된

pair의 멤버에 접근하는 것이 가능하죠.

 

 

 

---

 

 

 

 

근데 여기서

 

find 함수를 통해 존재하지 않는 키-값을 넣어

노드에 접근하려고 하면 어떻게 될까요?

 

이런 경우 사용자가 찾고자 하는 그런 데이터는 

존재하지 않는다는 의미로 end iterator를 반환합니다.

 

 

정말 그런지 확인해 보기 위해 

 

if 문을 추가했습니다. 

 

iterator와 map의 end 함수가 반환하는 값이 같으면

즉 현재 iterator가 end iterator라면

찾으려는 데이터가 없다고 판단하여 

"데이터를 찾을 수 없습니다."라는 문구를 출력합니다.

 

find 함수를 통해 존재하지 않는 데이터를 탐색하였고

이 결과 반환되는 end iterator를 기존 iterator에 대입하였습니다.

 

때문에 기존 iterator는 end iterator가 되어

if 문에 걸리면서 문구가 출력될 겁니다.

 

 

실행 결과 존재하지 않는 데이터를 탐색하였더니

데이터를 찾을 수 없다는 문구가 출력되는 것을 확인할 수 있습니다.

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

 

---