C++ 기초 : tree (6)

---

map과 같은 역할을 할 클래스 템플릿

cBST를 만들었습니다.

 

20 ~ 36번째 줄에 있는 것이 바로 map과 같은

역할을 해 줄 클래스 템플릿입니다.

 

즉 이진 탐색 트리를 구성하기 위한 클래스 템플릿이죠.

 

첫 번째 노드의 주솟값을 저장할 멤버 pRootNode입니다.

그리고 데이터(노드)의 개수를 나타내는 멤버 iCount도 있습니다.

 

노드의 자료형은 tBSTNode 구조체네요.

(클래스로 구성해도 상관없습니다.)

10 ~ 18번째 줄에 있는 것이죠.

 

 

tBSTNode 구조체는

pair를 저장하고 있으며, 부모 노드와 

왼쪽, 오른쪽 자식 노드의 주솟값을 저장하는

멤버를 두었습니다.

 

pair이 자료형 tPair 구조체네요.

 

 

tPair 구조체는

키-값으로 사용될 멤버 first와

실질적인 데이터인 second를 멤버로 두고 있습니다.

 

 

또한 cBST 클래스 템플릿에는

insert 함수와 생성자가 있습니다.

 

insert 함수는 pair로 구성된 데이터를 

트리 속 노드로 삽입하기 위한 함수이죠.

 

그래서 pair를 인자로 받는데, 

insert 함수는 pair는 노드로서 트리에 삽입하는

역할을 하기 때문에 pair의 값을 수정할 필요가 

없으므로 const가 붙었고, 인자로 받은 pair의 값을

복사할 필요 없이 만들어진 pair를 바로 레퍼런스로 받아

참조하여 복사 비용을 아꼈습니다.

 

생성자는 기본 생성자와 크게 다르지 않습니다.

 

 

 

---

 

 

 

이제 insert 함수의 정의를 볼까요?

 

가장 먼저 인자로 받은 pair 값을 기반으로 

노드를 만들기 위해 동적 할당을 진행합니다.

 

43 ~ 46번째 줄은 동적 할당된 공간을 가리키는

포인터 pNewNode의 멤버를 초기화해 주는 코드입니다.

 

해당 노드가 저장할 pair는 인자로 받은 pair이며

동적 할당되는 시점에는 부모 노드와 자식 노드가 

존재하지 않으므로 모두 nullptr로 초기화해 줍니다.

 

 

위 코드에서 아래 코드를 추가하면

 

insert 함수 정의는 끝이 납니다.

 

 

 

 

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

---