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 알고리즘
   409   410   411   412   413   414   415   416   417   418   419