이진탐색트리란?
이진 탐색 트리는 데이터를 이진트리 자료구조에 넣은 뒤 검색하는 방법입니다.
굉장히 좋은 검색 퍼포먼스를 자랑합니다.
이진 탐색 트리 만들기
먼저 만들어진 이진 탐색 트리 그림과 이진 탐색 트리를 만드는 조건에 대해 설명드리겠습니다.
- 이진 탐색 트리에 있는 데이터 하나하나를 '노드'라고 표현합니다.
- 노드별로 최대 2개의 하위 노드 즉 서브 트리를 가질 수 있습니다. (왼쪽 서브 트리, 오른쪽 서브 트리)
- 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있어야 합니다.
- 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있어야 합니다.
- 중복된 노드는 없어야 합니다. (검색 목적의 자료구조임으로 중복을 가져가 속도를 낮출 필요 없음)
이진트리 순회하기
이진트리를 순회하는 방법에는 3가지 방법이 있습니다.
1. 전위 순회 (pre order)
전위 순회는 루트 노드에서 시작하여 노드 > 왼쪽 서브 트리 > 오른쪽 서브 트리 순서로 순회합니다.
최상단 그림을 기준으로 전위 순회 조회를 하게 되면 아래와 같은 결과가 도출됩니다.
결과: 10, 5, 3, 1, 4, 7, 9, 20, 30, 75
* 이 방법은 이진트리를 복사할 때 주로 사용, 해당 결과를 그대로 이진트리를 만들면
원래 형태와 똑같은 이진트리를 만들 수 있습니다.
2. 중위 순회 (in order)
중위 순회는 루트 노드에서 시작하여 왼쪽 서브 트리 > 노드 > 오른쪽 서브 트리 순서로 순회합니다.
최상단 그림을 기준으로 중위 순회 조회를 하게 되면 아래와 같은 결과가 도출됩니다.
결과: 1, 3, 4, 5, 7, 9, 10, 20, 30, 75
* 값에 크기대로 정렬되는 것을 볼 수 있습니다.
3. 후위 순회 (post order)
후위 순회는 루트 노드에서 시작하여 왼쪽 서브 트리 > 오른쪽 서브 트리 > 노드 순서로 순회합니다.
최상단 그림을 기준으로 후위 순회 조회를 하게 되면 아래와 같은 결과가 도출됩니다.
결과: 1, 4, 9, 75, 3, 7 , 30, 5, 20, 10
탐색 (retreive)
상단 그림을 기준으로 '7'이라는 값을 찾는다고 가정해 보겠습니다.
- 루트 노드(10)와 7을 비교합니다. 7은 10보다 작기 때문에 왼쪽 서브 트리로 이동합니다.
- 노드(5)와 7을 비교합니다. 7은 5보다 크기 때문에 오른쪽 서브 트리로 이동합니다.
- 노드(7)와 7을 비교합니다. 7을 찾았습니다^^
다음은 '6'이라는 값을 찾을 때의 가정입니다.
- 루트 노드(10)와 6을 비교합니다. 6은 10보다 작기 때문에 왼쪽 서브 트리로 이동합니다.
- 노드(5)와 6을 비교합니다. 6은 5보다 크기 때문에 오른쪽 서브 트리로 이동합니다.
- 노드(7)와 6을 비교합니다. 6은 7보다 작기 때문에 왼쪽 서브 트리로 이동합니다.
- 왼쪽 서브 트리가 존재하지 않습니다. --> '값을 찾지 못함' 반환 후 탐색 종료합니다.
위처럼 이진 탐색 트리의 검색은 최대 (루트 노드 -> 잎새 노드에 이르는 에지수의 최댓값)만큼 입니다.
(위 그림 기준은 4번) 효율적으로 데이터를 찾을 수 있는 것입니다.
잎새 노드란? 하위 서브 트리가 없는 노드
삽입 (insert)
이진 탐색 트리에서의 입력 중 가장 중요한 것은 이진 탐색 트리의 속성이 깨지지 않아야 한다는 것입니다.
따라서 삽입은 반드시 잎새 노드에서 이뤄지게 됩니다.
탐색을 진행하여 값을 찾지 못한 곳에 새로운 노드를 입력합니다.
상단 그림을 기준으로 '8'이라는 값을 입력한다고 가정해 보겠습니다.
- 루트 노드(10)와 8을 비교합니다. 8은 10보다 작기 때문에 왼쪽 서브 트리로 이동합니다.
- 노드(5)와 8을 비교합니다. 8은 5보다 크기 때문에 오른쪽 서브 트리로 이동합니다.
- 노드(7)와 8을 비교합니다. 8은 7보다 크기 때문에 오른쪽 서브 트리로 이동합니다.
- 노드(9)와 8을 비교합니다. 8은 9보다 작기 때문에 왼쪽 서브 트리로 이동합니다.
- 왼쪽 서브 트리가 존재하지 않습니다 --> 해당 위치에 노드(8)를 삽입합니다.
'4'처럼 이미 존재하는 중복 노드는 입력되지 않습니다
삭제 (delete)
삭제는 탐색, 삽입보다 조금 복잡합니다.
삭제처리로 인해 자칫 이진 탐색 트리의 속성이 깨질 수 있기 때문입니다.
삭제는 세 가지 경우에 따라 다른 로직으로 진행합니다.
1. 삭제할 노드의 자식 노드(서브 트리)가 없는 경우
자식 노드가 없는 노드를 삭제할 경우 그냥 해당 노드를 삭제해 주면 됩니다. 제일 간단합니다.
2. 삭제할 노드의 자식 노드(서브 트리)가 한 개 있는 경우
해당 노드를 삭제하고 해당 노드의 자식 노드를 부모 노드와 연결해 주면 됩니다.
즉, 상단 그림 트리에서 '7'을 삭제할 경우 삭제 후 '9'를 '7'자리에 옮겨줍니다.
3. 삭제할 노드의 자식 노드(서브 트리)가 두 개 있는 경우
해당 노드를 삭제하고 해당 노드의 우측 서브 트리 중 가장 작은 값,
즉 우측 서브 트리 내에서 최하단, 최자 측 노드를 삭제 한자리에 올려줍니다.
상단 그림에서는
> '5'를 삭제하는 경우 '7'을 '5'자리에 놓습니다.
> '3'을 삭제하는 경우 '4'를 '3'자리에 놓습니다.
우측 서브 트리(삭제하는 노드보다 큰 값들) 중 최 좌측 & 하단 노드(가장 작은 값)를 삭제된 자리에 대체함으로써
이진 탐색 트리의 속성이 깨지지 않도록 할 수 있습니다.
이진 탐색 트리의 한계
이진 탐색 트리는 탐색을 효율적으로 빠르게 하기 위한 자료구조입니다.
서브 트리가 한 개로만 구성된 이진 탐색 트리의 경우 결국 모든 노드 개수만큼 비교를 해야 할 수 도 있습니다.
위처럼 서브 트리가 한 개로만 구성된 이진 탐색 트리라면
'75'라는 값을 찾기 위해 결국 모든 노드를 비교해야 하는 형태가 됩니다.
이런 식의 이진 탐색 트리는 탐색 속도가 빠르다고 하기 힘듭니다.
그래서 입력, 삭제 단계에서 트리 전체의 균형을 맞추는 AVL Tree가 있다고 합니다.