[Data Structure] Binary Search Tree 이진 탐색 트리

병뚜껑 숫자 맞추기 게임이 있다.

어떤이는 한잔을 마시게 하기 위해 up and down을 외치고

또 어떤이는 마시지 않기 위해 필사적으로 범위를 좁혀가며 숫자를 맞춰야만 한다.

 

가장 적은 횟수의 추측으로 이 숫자를 알아내야만 한다.

아무도 1부터 시작해서 순서대로 2, 3, 4... 를 외치는 사람은 없다. -> 요게 단순탐색

 

보통 1~50 사이의 숫자가 표기되어 있다.(소주병 기준)

그럼 50의 중간, 25부터 시작한다.

up이라고 외치면 1부터 25까지의 숫자는 답이 아니고,

down이라고 외치면 26부터 50이 답이 아니게 된다.

그렇게 또 up and down에 맞춰 반절씩 범위를 좁혀 나가는 것이 이진 탐색이다.

 

한 번에 많은 숫자를 답에서 제거해버리기 때문에 이 방법으로 맞출 경우 최대 6번(5.64) 만에 맞출 수 있다.

그래서 이렇게 찾는 방법이 '가장 효율적이다' 라고 할 수 있다.

 

이진 탐색 트리

크기가 9이고, 높이가 3인 이진트리 [출처: 위키디피아]

위의 이미지는 이진 트리이고 이진탐색 트리와의 차이점은 다음과 같다.

이진트리란 노드의 최대 차수가 2인 트리를 의미.
이진 탐색 트리는 이진트리에서 조건이 추가된 것을 의미.
  조건 1. 루트 노드의 왼쪽 자식 노드는 루트 노드보다 크기가 작다.
  조건 2. 루트 노드의 오른쪽 자식 노드는 루트 노드보다 크기가 같거나 크다.

그래서 그림의 노드 값들이 엉망징창인 것이다.

 

아니 그냥 이진 탐색 쓰지 왜 이진 탐색 트리를 쓰냐..

그것은 바로 이진 탐색의 경우 잘 정렬되어 있는 자료에만 효율적이고 자료 입력이나 삭제를 받는 것이 힘들기 때문..(불가능)

 

그래서 이진 탐색과 연결 리스트를 결합하여 나온 것이 이진 탐색 트리다.

연결 리스트의 경우 자료 입력, 삭제에 필요한 계산이 효율적(O(1))이지만 자료를 탐색할 때는 아주 비효율적이기에..

둘을 결합시킨 것은 참 잘한 결정인 것 같다.

 

그래서 위의 엉망(?)이었던 이진 트리를 이진 탐색 트리로 바꿔보면 이렇게 된다.(중복값 제외)

아름답지는 않지만.. 일단 위의 그림이 2로 시작했으니 이렇게 되긴 했는데..

이처럼 노드 수는 적은데 높이가 4나 된다. 이러면 자료가 과연 효율적으로 되어있나.. 싶다.

 

아름답게 바꿔주고 싶다면 위의 그림에서 (얼추)중간값인 7을 부모로 시작하면 된다.

이미지 제공: 규수님

이렇게 정렬을 하면 값을 찾을 때 위의 말했던 병뚜껑 예시처럼 (거의)logN번만에 찾을 수 있다.

그리고 이 친구를 inorder하게, 순서대로 늘어놓는 과정은 다음과 같다.

이미지 출처: visuAlgo에서 내가 만듬

정말 획기적이고 똑소리나며 효율적인 자료 구조 방식인거 같다.