이진 탐색 트리(Binary Search Tree)

이진 탐색 트리 : BST

 정의

 이진 탐색 트리 정의에 앞서 이진 트리(binary tree)를 정의하자. 이진 트리란 왼쪽, 오른쪽 최대 두 개의 자식 노드를 가질 수 있는 트리를 의미한다. 이때 자식 노드들은 배열이 아닌 포인터로 left와 right를 담는 객체로 구현한다. 단, left 노드 값은 부모 노드보다 작은 값이고 right 노드 값은 부모 노드보다 큰 값이어야 한다.

 

 이진 탐색 트리는 이런 이진 트리 구조에 이진 탐색(binary search)의 아이디어를 가져와 만든 트리이다. 이진 탐색이란 N개 원소 중 원하는 값을 찾을 때, 매번 탐색 값을 절반씩 줄여가며 탐색하는 것을 의미한다. 이렇게 되면 O(lgN) 시간에 원하는 값을 찾을 수 있다.

 

BST 구조 예

 

 순회 및 검색

 순회 및 검색을 할 때 이진 탐색과 비슷한 속도로 자료를 찾을 수 있다. 예를 들어 가장 큰 원소를 찾고자 하면 오른쪽 노드만 타고 가면 된다. 또 다른 예로 어떤 특정 원소를 찾는다 하자. 그럼 이때 루트 값만으로 어디로 가야 하는지 쉽게 유추할 수 있다.

 

 조작(삽입과 삭제)

 순회 및 검색에서 소개한 특성들은 정렬된 배열과 비교하면 나을 것이 없다. 이진 탐색 트리의 진가를 드러내는 곳은 집합에 원소를 추가하거나 삭제할 때 나타난다.

 

 예를 들어 원소를 추가한다고 하자. 배열인 경우 들어갈 위치를 찾고, 그 이후의 값들을 한 칸씩 뒤로 밀어야 한다. 그러나 이진 탐색 트리 구조인 경우 선형 구조의 제약이 없기 때문에 삽입 위치에서 노드만 물려주면 된다.

 

 삭제인 경우 추가에 비해 까다롭다. 추가하는 경우 잎 노드만 생기지만, 삭제는 트리 어디에서도 일어날 수 있기 때문이다. 한 예로 루트를 지우는 경우가 있다.

 

 이진 탐색 트리에서 삭제를 구현하는 많은 방법이 있지만, 그중 간편한 방법으로 합치기 연산이 있다. 합치기 연산 구현은 다소 쉽다. 삭제하는 노드의 left와 right 서브 트리가 있다고 하자. right 서브 트리의 값들은 항시 left 서브 트리의 값보다 크므로 right 서브 트리를 left 서브 트리의 right 자식 노드에 서브 트리를 합치면 된다. 그림을 보면 이해가 간다.

 

특정 노드의 삭제 전, 후