자료구조(12)

이진 탐색 트리

이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다해도, 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가? 예를 들어서 '연결 리스트'에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정하자. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다. 반면 이진 트리의 경우에는 위치를 알고 있다면, 다시 말해 데이터에 이르는 길을 알고 있다면 루트노드에서 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 있다 물론 여기에는 다음과 같은 가정이 존재한다 "이진 트리는 단말 노드에 이르는 길의 갈래가 매우 많다. 따라서 찾는 데이터가 존재하는 제대로된 길을 선택할 수 있어야 한다" 참고로 말하자면 "이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다" 쉽게 말해서 '이진 트리'에 "데이터를 저장 규칙'을 더해놓은 것이 '이진  탐색 트리'이다.

 

이진 탐색 트리가 되기 위한 조건(참고로 '탐색 키'는 정수라 가정하였으며, 간단히 Key로 표현)

• 이진 탐색 트리의 노드에 저장된 키는 유일하다
• 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다
• 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다

 

키에는 유일하다는 의미가 포함되어 있음을 언급하였다. 그럼 위의 조건을 만족하는 트리의 예를 보겠다.

 

                      12

               8              17

           4     9        13   21

        2                    

 

위의 그림을 통해서 다음 수식이 어디서나 만족함을 알 수 있다.

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 (서브 트리에서도 조건이 만족함을 볼 수 있다)

 

이진 색 트리를 대상으로 숫자 10을 저장한다고 가정해보자. 그러면 루트 노드를 시작으로 하여 다음의 과정을 거쳐서 저장될 위치를 결정하게 된다.

1. 10 < 12 이므로 왼쪽 자식 노드로 이동
2. 10 > 8 이므로 오른쪽 자식 노드로 이동
3. 10 > 9 이므로 오른쪽 자식 노드로 이동
4. 오른쪽에 아무것도 없으니 그 위치에 저장!

 

이렇듯 이진 탐색 트리는 '작으면 왼쪽으로, 크면 오른쪽으로'라는 원칙을 기준으로 데이터를 삽입한다.

따라서 탐색의 과정에서도 이를 그대로 따르면 된다. 찾는 키의 값이 비교대상보다 작으면 왼쪽 자식 노드로, 찾는 키의 값이 비교대상보다 크면 오른쪽 자식 노드로 이동하는 것이다. 때문에 이진 탐색트리는 탐색의 과정에서 길을 잃을 일이 없다. 그리고 몇 단계 지나지 않아서 탬색 대상을 찾을 수 있다. 효율은 두말하지않겠다

 

"왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식" 이 조건이 이진 탐색 트리가 되기위한 조건은 아니다.

즉, 이진 탐색 트리가 항상 만족하는 조건과 이진 탐색 트리가 되기 위한 조건은 다른것이다.

예시) 루트 노드인 12보다 큰 값이 왼쪽 서브 트리에 두 개나 존재한다. 때문에 이는 이진 탐색 트리가 아니다.

                   12

               9       생략

            4     18

         2  21