Page 414 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 414
a 3을 검색합니다(검색 성공). b 8을 검색합니다(검색 실패).
1 5를 선택합니다. 3은 5보다 작기 때문에 1 5를 선택합니다. 8은 5보다 크기 때문에 오른
왼쪽으로 검색을 진행합니다. 쪽으로 검색을 진행합니다.
5 5
2 7 2 7
1 4 1 4
3 3
2 2를 선택합니다. 3은 2보다 크기 때문에 2 7을 선택합니다. 8은 7보다 크기 때문에 오른
오른쪽으로 검색을 진행합니다. 쪽으로 검색을 진행합니다. 하지만 오른쪽에
는 자식이 없어 검색에 실패합니다.
5 5
2 7 2 7
1 4 1 4
3 3
3 4를 선택합니다. 3은 4보다 작기 때문에 4 3을 찾았습니다. 검색에 성공합니다.
왼쪽으로 검색을 진행합니다.
5 5
2 7 2 7
1 4 1 4
3 3
[그림 10-11] 이진검색트리에서 노드를 검색하는 과정
검색에 실패하는 경우( b )
이진검색트리에서 8을 검색하는 과정은 다음과 같습니다.
1 루트를 선택합니다(5). 8은 5보다 크기 때문에 오른쪽으로 검색을 진행합니다.
2 7을 선택합니다. 7은 리프이고 오른쪽 자식 노드가 없습니다. 더 이상 검색할 수 없기 때문에 검색에 실패
합니다.
이진검색트리에서 원하는 값을 찾으려면 이런 방법으로 루트부터 시작해 현재 선택한 노드
의 키 값과 목표하는 값을 비교하면서 왼쪽, 오른쪽으로 검색을 진행하면 됩니다. 알고리즘은
다음과 같습니다.
414 C 알고리즘