C로 만드는 자료구조 - 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)란?

 이진 탐색 트리는 이진 트리에서 탐색(Search)란 단어가 들어가 있다. 탐색이 뜻하는 바와 같이 이진 트리에서 '자료의 검색'이 주된 기능이 된다. 이진 탐색 트리는 효율적인 자료 검색을 목적으로 기존 이진 트리에 몇 가지 제약 사항을 추가한 트리이다. 위 설명만 보면 앞서 설명 했던 힙(Heap)과 비슷하다. 힙 또한 이진 트리에서 최댓값 또는 최솟값을 빠르게 반환하도록 이진트리에서 몇가지 제약 사항을 추가했기 때문이다. 

 이진 탐색 트리는 힙과는 다르게 특정 값에 해당하는 노드를 빠르고 효율적으로 찾는 것을 목적으로 한다.

이진 탐색 트리는 다음 특성을 만족해야 한다.

1. 트리의 모든 노드는 유일한 값을 가진다.

2. 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작다.

3. 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 크다.

4. 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리다.

 힙은 같은 값이 여러개 존재해도 상관 없었지만 이진 탐색트리에서는 모든 노드의 값이 서로 달라야 한다. 또한 현재 노드를 기준으로 왼쪽 서브트리의 노드의 값은 모두 현재 노드보다 작아야 하고 오른쪽 서브트리의 모든 노드들은 현재 노드의 값보다 커야한다.

아래 그림은 이진 탐색 트리의 예시이다.

이진 탐색 트리의 추상 자료형

이진 탐색 트리 사용에 필요한 기본 연산을 정리한 이진 탐색 트리의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다. 

이름		입력	출력	설명
이진 탐색 트리 생성	createBST()		이진탐색트리 T	이진 탐색 트리 T 생성
이진 탐색 트리 삭제	deleteBST()	이진탐색트리 T	N/A	이진 탐색 트리 T 메모리 해제
노드 추가	inseertBSTNode()	이진탐색트리 T 원소 e	성공/실패 여부	이진 탐색 트리에 새로운 원소 추가
노드 제거/반환	deleteBSTNode()	이진탐색트리 T 값 k		이진 탐색 트리에 값 k를 제거
검색	search()	이진탐색트리 T 값 k		이진 탐색 트리의 노드중 k와 같은 값을 가지는 노드 반환

 이진 탐색 트리의 주요 연산은 노드 추가,제거와 검색 연산이다. 이진 탐색 트리의 특별한 제약 사항은 위 연산들로 이루어 진다.

이진 탐색 트리에서의 검색 연산

 앞서 이진 탐색 트리만의 특별한 제약 사항 4가지를 설명했는데 이것만으로 어떻게 원하는 값이 있는 노드를 찾는것을 효율적으로 할 수 있는지 설명하겠다. 

 다시 한번 이진 탐색 트리의 특징을 살펴보자

1. 트리의 모든 노드는 유일한 값을 가진다.
2. 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 크다.
4. 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리다.

 여기서 검색을 효율적으로 하는데 중요한 역할을 하는 것이 2,3 번의 특징이다. 우리가 현재 방문하고 있는 노드를 기준으로 왼쪽 서브트리에 있는 노드들은 현재 노드보다 값이 작고 오른쪽 서브트리에 있는 노드들은 값이 크기 때문에 우리는 노드를 방문할때 3가지 가능성이 존재하게 된다.

1) '입력 값'과 현재 노드의 값이 같은 경우  --> 검색 완료(원하는 노드 찾기 성공)
2) '입력 값'이 현재 노드의 값보다 작은 경우 --> 왼쪽 서브트리로 이동
3) '입력 값'이 현재 노드의 값보다 큰 경우 --> 오른쪽 서브트리로 이동

 이진 탐색 트리의 특징을 이용해 현재 노드와 값을 비교하여 검색을 종료할지 왼쪽 또는 오른쪽 서브트리로 이동할지 결정하여 연산을 지속하면 원하는 노드를 찾을 수 있다.

 아래 그림의 이진 탐색 트리에서 값이 12인 노드를 규칙을 이용해 탐색해보자

탐색 연산

 먼저 루트 노드인 30보다 12가 작기 때문에 왼쪽으로 이동하고 15와 비교 후 왼쪽으로 이동하는데 10과 비교하면 12가 더 크기 때문에 이번에는 오른쪽으로 이동한다. 오른쪽으로 이동한 노드가 12이기 때문에 같은 값을 가지는 노드를 찾았다.

이진 탐색 트리에서의 추가 연산

이진 탐색 트리의 특징을 유지하기 위해서는 새로운 노드를 추가 할때 어떤 자리에 삽입해야 할 지 적절한 위치를 찾아야 한다. 이를 찾기 위해서 추가하려는 노드의 값을 이용해 탐색을 해야한다. 앞서 설명한 탐색 연산과 마찬가지로 현재 노드와의 값 비교를 통해 삽입될 위치를 찾을 수 있다.

아래 그림의 이진 탐색 트리에서 19를 추가한다고 생각 해보자

삽입연산

  가장 먼저 루트 노드인 30과 비교하면 19가 더 작기 때문에 왼쪽 서브트리로 이동한다. 그 다음 15와 비교 후 오른쪽 서브트리로 이동 20과 비교 후 왼쪽 서브트리로 이동 하는데 20의 왼쪽 자식 노드가 없기 때문에 그 빈공간에 19를 삽입해준다.

이진 탐색 트리에서의 삭제 연산

 추상 자료형을 보면 이진 탐색 트리에서의 삭제 연산은 입력 값을 받으면 해당 값과 똑같은 값을 가지는 노드를 삭제한다. 따라서 우리는 삭제하고자 하는 노드를 찾아주어야 하는데 이 역시 탐색 연산과 똑같이 방식을 사용하여 해당 노드를 찾을 것이다. 근데 막상 해당 노드를 찾았다 하더라도 무작정 삭제할 수는 없다. 해당 노드가 서브트리를 가지고 있으면 서브트리를 잘 이어주어야 하기 때문이다. 따라서 삭제 연산에서 삭제하려는 노드를 찾았다면 3가지 경우로 나누어 생각해야한다,

1) 삭제하려는 노드의 자식 노드가 없는 경우
2) 삭제하려는 노드의 자식 노드가 1개인 경우
3) 삭제하려는 노드의 자식 노드가 2개인 경우

- 1) 삭제하려는 노드의 자식 노드가 없는 경우

 이진 탐색 트리의 삭제 연산 중 가장 간단한 경우이다. 삭제하려는 노드의 자식 노드가 없는 경우는 해당 노드가 단말 노드라는 뜻이다. 따라서 단순히 해당 노드의 메모리를 해제하고 부모 노드의 연결만 NULL처리를 해주면 끝이다.

아래 그림은 자식 노드가 존재하지 않는 25를 제거 할때이다.

- 2) 삭제하려는 노드의 자식 노드가 1개인 경우

삭제하려는 노드가 1개인 경우에는 1번과 마찬가지로 해당 노드를 제거하고 부모 노드와 자식 노드를 연결 시켜주어야한다. 기존 부모 노드의 새로운 자식 노드가 '자식 노드의 자식 노드'가 되는 것이다. 이렇게 그냥 연결시켜주어도 이진 탐색 트리의 특징은 유지된다.  

- 3) 삭제하려는 노드의 자식 노드가 2개인 경우

 삭제하려는 노드가 2개인 경우에는 1개인 경우와는 좀 더 복잡하다. 부모 노1드의 새로운 자식 노드로 어떤 노드를 선택 해야 될지 결정해야 하기 때문이다. 새로운 자식 노드가 되기 위해서는 삭제하려는 노드와 같이 왼쪽 서브트리, 오른쪽 서브트리를 잘 나눌 수 있는 값이 와야한다. 이런 조건을 만족하는 노드는 2개가 있는데 하나는 왼쪽 서브트리에서 가장 큰값을 가지는 노드이고 나머지 하나는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드이다. 우리는 둘 중 하나를 찾아내고 삭제하려는 노드의 위치로 이동시켜 주어야 한다. 

 - 왼쪽 서브트리에서 가장 큰 값을 가지는 노드를 찾는 방법
가장 간단하게 왼쪽 서브트리에서 계속 NULL값을 만날때까지 오른쪽 서브트리로 이동하면 가장 큰 값을 가지는 노드를 찾을 수 있다.

 - 오른쪽 서브트리에서 가장 작은 값을 가지는 노드를 찾는 방법
마찬가지로 오른쪽 서브트리에서 계속 NULL값을 만날때까지 왼쪽 서브트리로 이동하면 가장 작은 값을 가지는 노드를 찾을 수 있다.