C++87 C++ 기초 : tree (7) enum class를 추가하여 이진 탐색 트리 역할을 하는 cBST 클래스 템플릿의 insert 함수를 더 간략하게 표현해 봅시다. enum class인 NODE_TYPE을 만들어 줍니다. 부모 노드는 0, 왼쪽 자식 노드는 1,오른쪽 자식 노드는 2로 표현하고 끝은 3으로 표현합니다. 따로 숫자를 대입해 주지 않으면0부터 시작하여, 1씩 더한 수를 해당 키워드가 할당받게 되죠. 기존 insert 함수에서는tBSTNode형으로 동적 할당된 공간의멤버를 하나씩 초기화해 주었죠? 이제는 tBSTNode 클래스 템플릿의 생성자를 만들어서 동적 할당되면서 초기화가진행될 수 있도록 합시다. 30번째 줄을 보시면첫 번째 인자로 const tPair형 레퍼런스를받습니다. tBSTNode형 객체가 만들어.. 2024. 4. 30. C++ 기초 : enum BST의 insert 함수를 구현한 아래 코드에서 61 ~ 75번째 줄에 있는 if 문과 76 ~ 90번째 줄에 있는 else if 문이 대칭으로 구성되어 있는 것이 느껴지시나요? 두 구문 모두 같은 동작이지만if 문은 왼쪽 자식 노드에 대한 동작이고 elese if 문은 오른쪽 자식 노드에 대한 동작입니다. 이런 코드는 'enum'이라는 것을 통해 코드를 줄여줄 수 있습니다. 아래 코드를 보시면 57번째 줄에 있는 것이 바로 enum입니다.열거형이라고도 부르죠. 중괄호 안에 단어를 적어 주면 됩니다.간단하죠. 이제 해당 단어를 사용하게 되면특정 값으로 인지하게 됩니다. 아무런 대입을 하지 않을 시, 가장 처음 적은키워드를 0으로 보고 다음에 추가되는 키워드는 값을 하나 높여 인지하게 되죠. 실제 .. 2024. 4. 29. C++ 기초 : tree (6) map과 같은 역할을 할 클래스 템플릿cBST를 만들었습니다. 20 ~ 36번째 줄에 있는 것이 바로 map과 같은역할을 해 줄 클래스 템플릿입니다. 즉 이진 탐색 트리를 구성하기 위한 클래스 템플릿이죠. 첫 번째 노드의 주솟값을 저장할 멤버 pRootNode입니다.그리고 데이터(노드)의 개수를 나타내는 멤버 iCount도 있습니다. 노드의 자료형은 tBSTNode 구조체네요.(클래스로 구성해도 상관없습니다.)10 ~ 18번째 줄에 있는 것이죠. tBSTNode 구조체는pair를 저장하고 있으며, 부모 노드와 왼쪽, 오른쪽 자식 노드의 주솟값을 저장하는멤버를 두었습니다. pair이 자료형 tPair 구조체네요. tPair 구조체는키-값으로 사용될 멤버 first와실질적인 데이터인 second를 멤버로.. 2024. 4. 27. C++ 기초 : tree (5) 이제 find 함수를 통해 찾은 노드에 실질적으로 저장된데이터를 출력하기 위한 코드를 작성합시다. 61번째 줄에 있는 if 문에 걸리지않아 else 구문으로 넘어갔다면 find 함수를 통해찾은 노드가 존재한다는 의미겠죠? 67 ~ 68번째 줄에서 find 함수가 찾은 노드를 iterator로 반환합니다.이를 기존에 있던 iterator에 대입하였으니이제 iterator는 찾은 노드를 가리키게 되죠. 해당 노드에는 pair가 들어 있으며pair의 두 번째 멤버에는 학생 정보가 들어 있습니다.이 학생 정보에는 이름이 들어 있죠.그래서 iterator가 가리키는 pair에 접근하고 여기서 학생 정보가 들어 있는 두 번째 멤버에 접근합니다.그 학생 정보에 들어 있는 이름을 출력하는 것이죠. 마찬가지로 나이 .. 2024. 4. 27. 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보다 크므로 오른쪽 자식 노드가 되죠.. 2024. 4. 26. C++ 기초 : tree (3) 아래와 같은 이진 탐색 트리가 있습니다. 이때 150이라는 데이터를 넣으려고 합니다. 그럼 일단 루트 노드부터 비교를 하겠죠? 150은 100보다 크니까 오른쪽으로 갑니다.그곳에는 300이 있네요. 150은 300보다 작으므로 왼쪽에 자식 노드로 배치될 겁니다. 보면 처음 루트 노드를 비교할 때부터 자리를 잡을 때까지노드를 비교한 후, 한 쪽을 선택하기 때문에나머지 절반을 배제하고 있습니다. 이진 탐색 트리는 데이터를 탐색할 때뿐만 아니라,데이터를 입력하는 과정도 O( log N )이네요. 반면에 vector와 list는 비교할 것 없이 바로 데이터를 입력하죠. 빅오 표기법으로 나타내면O ( 1 )입니다. 대신 탐색할 때는 O( N )이죠. 이진 탐색 트리는 입력과 탐색 모두O ( logN )으로 .. 2024. 4. 26. 이전 1 2 3 4 5 6 ··· 15 다음
