Page 415 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 415
1. 루트부터 선택하여 검색을 진행합니다. 여기서 선택하는 노드를 p라고 합니다.
2. p가 널이면 검색에 실패합니다.
3. 검색하는 값 key와 선택한 노드 p의 키 값을 비교하여
• 값이 같으면 검색에 성공(검색 종료)합니다.
• key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입합니다(왼쪽으로 검색 진행).
• key가 크면 선택한 노드에 오른쪽 자식 노드를 대입합니다(오른쪽으로 검색 진행).
4. 2번 과정으로 되돌아갑니다.
Search 함수는 이 알고리즘을 바탕으로 이진검색트리에서 노드를 검색합니다.
실습 10-2[B] •완성 파일 chap10/BinTree.c
01 /*--- 검색 ---*/
02 BinNode *Search (BinNode *p, const Member *x)
03 {
04 int cond;
05 if(p == NULL)
06 return NULL; /* 검색 실패 */
07 else if((cond = MemberNocmp(x, &p->data)) == 0)
08 return p; /* 검색 성공 */
09 else if(cond < 0)
10 Search(p->left, x); /* 왼쪽 서브 트리에서 검색 */
11 else
12 Search(p->right, x); /* 오른쪽 서브 트리에서 검색 */
13 }
14 (실습 10-2[C]에서 계속)
이 함수를 호출하면서 매개변수 p에 이진검색트리의 루트 노드 포인터를 전달합니다. 그런
다음 x가 가리키는 구조체 Member형 객체와 같은 키 값을 갖는 노드를 검색합니다. 검색에
성공하면 해당 노드에 대한 포인터를 반환합니다. MemberNoCmp 함수는 Member.c에 있습니다.
노드를 삽입하는 Add 함수
노드를 삽입할 때 주의해야 할 점은 노드를 삽입한 다음에 트리의 형태가 이진검색트리의 조건
을 유지해야 한다는 점입니다. 따라서 노드를 삽입할 때는 알맞은 위치에 삽입해야 합니다. 이
때 삽입할 노드의 키와 같은 값을 가지는 노드가 이미 있다면 노드를 삽입해서는 안 됩니다.
그러면 그림 10-12를 보면서 좀 더 자세히 살펴보겠습니다. 4개의 노드(2, 4, 6, 7)로 이루어진
10•트리 415
