트리 | 이진 트리 탐색하기

이진트리 탐색

이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것입니다.

물건을 잘 정리해두면 쉽게 찾을수 있는 것과 같죠. 이진 트리는 자식 노드가 최대 2개인 트리를 말하며 목적에 따라 여러 종류가 있습니다. 여기서는 이진 탐색 트리(binary search tree)를 만들고, 이를 활용해 원하는 노드를 효율적으로 찾는 방법을 알아봅시다.

 

이진 탐색 트리 구축하기

이진 탐색 트리의 대상 데이터가 3 → 4 → 2 → 8 → 9 → 7 → 1 순서로 들어온다고 생각하고 이진 탐색 트리부터 구축합니다. 이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 오니쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있습니다. 다음을 보면 데이터를 전부 삽입한 다음 정렬하는 것이 아니라 데이터를 하나씩 삽입하면서 이진 탐색 트리를 구축합니다. 즉, 삽입과 동시에 정렬을 합니다.

 

 

01단계 

최초의 데이터는 루트 노드가 됩니다. 3을 이진 탐색 트리에 루트 노드로 추가합니다.

 

02단계

현재 삽입하려는 데이터는 4입니다. 3보다 크므로 오른쪽 자식 위치에 배치합니다.

 

03단계

현재 삽입하려는 데이터는 2입니다. 2는 3보다 작으므로 왼쪽 자식 위치에 삽입합니다.

 

04단계

현재 삽입하려는 데이터는 8입니다. 8은 3보다 크므로 오른쪽 자식 위치를 봅니다. 이미 자식이 있는 경우 값을 비교합니다. 8은 4보다 크므로 오른쪽 자식 위치를 봅니다. 위치가 비어 있으므로 8을 배치합니다. 이런 식으로 이진 탐색 트리를 구축할 때는 넣으려는 대상 데이터의 값이 크거나 같으면 오른쪽 자식으로, 작으면 왼쪽 자식으로 배치합니다.

 

05단계

9는 3보다 크므로 오른쪽을 봅시다. 4보다도 크므로 다시 오른쪽을 봅니다. 8보다도 큽니다. 오른쪽에 배치합니다.

 

06단계

7은 3보다 크고, 4보다 크고, 8보다 작으므로 8의 왼쪽 자식에 배치합니다.

 

07단계

1은 3보다 작고, 2보다 작으니 2의 왼쪽 자식에 배치합니다.

 

이진 탐색 트리 탐색하기

이제 탐식하겠습니다. 이진 탐색 트리를 탐색하는 방법은 다음과 같습니다.

1. 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색합니다.

2. 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색합니다.

3. 값을 찾으면 종료합니다. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 겁니다.

 

검색 대삭 트리는 다음과 같습니다. 여기서 5를 찾는다고 생각해봅시다

 

3보다 크니 우선 오른쪽을 봅니다. 6보다 작으니 왼쪽을 봅니다. 왼쪽에는 아무것도 없습니다. 이진 탐색 트리를 구축한 방식대로 찾았을 때 5가 없으므로 이 트리에는 5가 없다고 판단해도 됩니다.

 

배열 탐색과 비교하면 어떨까?

이진 탐색 트리의 탐색 과정은 쉽게 이해했을 겁니다. 그런데 왜 굳이 이렇게 탐색할까요? 그건 배열 탐색과 비교해보면 금방 알 수 있습니다. 배열에서는 (아마 다 알고 있겠지만) 다음과 같이 순차적으로 5를 찾습니다.

5가 없다는 것을 알아내기 위해 7번의 비교 연산을 진행했습니다. 그에 반해 이진 탐색 트리는 단 2번만 비교 연산을 진행하여 알아냈죠. 이런 점에서 배열 탐색보다 이진 탐색 트리의 탐색이 훨씬 빠르다고 할 수 있습니다. 그럴 수 있는 이유는 이진 탐색 트리의 구축 방식에 있습니다.

 

이진 탐색 트리는 크면 오른쪽, 작으면 왼쪽

모든 탐색 알고리즘에서 탐색 효율을 개선하는 방법은 같습니다. 탐색 대상이 아닌 노드를 한 번에 많이 제외할 수 있으면 됩니다. 방에서 핸드폰을 찾는다고 가정해볼까요? 모든 물건을 방 하나에 몰아 놓으면 방에 있는 물건을 전부 확이하며 핸드폰을 찾아야 합니다. 하지마 전자기기만 따로 분류해서 정리해 놓았다면 다른 곳은 아예 찾을 필요가 없겠죠. 이렇게 탐색 대상이 아닌 것들을 빠르게 제외하면 원하는 것을 빠르게 찾을 수 있습니다. 이진 탐색 트리의 원리도 동일합니다. 이진 탐색 트리의 구축 방식 자체가 갖는 특성은 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 검색을 빠르게 만들어줍니다. 앞서 5를 찾을 때를 다시 생각해봅시다. 루트 노드 3보다 크다는 판단을 내리면서 하위의 왼쪽 데이터는 검색 대상에서 제외해버렸습니다.

 

이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 트리 균형에 의존합니다. 트리의 균형이 잡혔다는 건 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 것을 말합니다. 균형이 유지되었다고 가정했을때 삽입과 탐색 연산 시 이진 탐색 트리에 저장된 노드가 N개라고 하면 시간 복잡도는 O(logN)입니다. 하지만 균형이 맞지 않을 때는 시간 복잡도가 배열과 비슷합니다. 왜 그런지 바로 이어서 알아보겠습니다.

※ 균형이 잡혀 있다는 건 왼쪽과 오른쪽 서브 트리의 높이 차가 1 이하인 경우를 말합니다. 그렇지 않을때 균형이 잡혀있지 않다라고 표현합니다.

 

이진 탐색 트리와 배열 탐색의 효율 비교

지금까지의 설명을 읽으면 이런 생각을 할 수 있습니다.

'이진 탐색 트리에서 탐색하는 것이 배열에서 탐색하는 것보다 효율이 좋은 것 같네!'

하지만 두 자료구조의 삽입과 탐색 시간 복잡도는 이진 탐색 트리의 균현이 맞지 않으면, 다시 말해 최악의 경우 "O(N)으로 같다" 라고 이야기합니다. 약간의 전제가 필요하긴 하지만요. 그 이야기를 잠깐 하고 넘어가겠습니다.

 

치우쳐진 형태의 트리

이진 탐색 트리가 만약 이런 형태를 하고 있다면 어떨까요?

이진 트리는 왼쪽 혹은 오른쪽 자식 노드만 있어야 합니다. 그런데 오른쪽 자식만 있는 겁니다. 모든 노드가 루트 노드인 3보다 커서 오른쪽으로 치우쳐졌습니다. 이런 트리에서 9를 찾는다면 모든 노드를 다 탐색해야 하므로 O(N)의 시간 복잡도가 필요합니다. 다만 이렇게 극단적으로 치우친 경우는 지극히 예의 상황입니다. 사실 대부분의 상황에서는 이진 탐색 트리의 탐색 성능이 더 좋습니다. 다만 이렇게 치우쳐지지 않도록 균형을 유지하는 이진 탐색 트리가 있습니다.

 

균형 이진 탐색 트리

그런 이진 탐색 트리들을 균형 이진 탐색 트리(balanced binary search tree)라고 합니다. 균형 이진 탐색 트리는 또 세부적으로 AVL 트리, 레드-블랙 트리 등으로 구분하여 부릅니다. 균형 이진 탐색 트리를 활용하면 이진 트리의 탐색 연산 횟수가 트리 높이에 비례하고 트리의 높이는 logN이므로 탐색시간 복잡도를 O(logN)으로 유지할 수 있습니다.

 

https://jwinjection.tistory.com/343

트리 | 균형 이진 탐색 트리