[자료구조] 이진 탐색 트리 : 탐색, 삽입, 삭제 연산의 구현

이진 탐색 트리는 탐색을 효율적으로 하기 위한 자료구조로서, 이진트리이자 모든 원소는 서로 다른 key를 가지는 특성을 가지고 있다. 

 

이진탐색에서의 탐색은 searchBST() 연산을 이용하여 진행된다. 우선 루트에서 시작하여, 탐색할 key값 x를 루트 노드의 key값과 비교한다. key값보다 루트 노드의 key값이 클 경우 왼쪽 서브트리에서, key값이 루트노드의 key값보다 클 경우 오른쪽 서브트리에서 탐색을 진행한다는 기본 메커니즘을 기반으로 탐색을 진행한다. 

 

이진탐색에서 탐색의 구현은 반복/재귀가 있다.

반복적 방법은 while p != NULL을 이용하여 p값을 찾을 때까지 삽입 연산을 계속 수행하는 방법이고, 재귀적 방법은 찾고자하는 key값이 해당 key값보다 클 경우 범위를 제한하여 다시 루프를 돌아 값을 찾는 방법이다.

 

이진탐색에서의 삽입은 먼저 탐색 연산을 수행한 다음 진행된다. 우선 삽입할 노드를 탐색하고, 삽입할 노드를 생성한 후, 삽입 노드를 부모 노드와 연결시키는 일련의 프로세스를 통해 진행된다. 삽입 시 새로운 노드의 좌우 노드의 NULL처리가 중요하다.

 

이진탐색에서의 삭제 연산은 삽입시와 마찬가지로 먼저 탐색연산이 수행된 이후에 진행된다. 탐색하여 찾은 노드를 삭제하기 위한 방법은 3가지인데, 삭제할 노드의 차수에 따라 달라진다.

 

1) 삭제할 노드의 차수가 0인경우: 부모의 해당 자식 필드를 NULL 처리 후 노드 삭제

2) 삭제할 노드의 차수가 1인경우: 삭제할 노드의 자식을 삭제될 노드의 부모 노드에 연결 후 노드 삭제

3) 삭제할 노드의 차수가 2인경우: 삭제할 노드의 자손들 중 후계자를 선택하여 자리를 물려준다.