[자료구조] 11. 이진탐색트리(Binary search tree)

이진 탐색 트리는 이진트리로서, 중위순회(In-order traversal) 시 정렬된 형태라는 특징을 가지고 있다.

ADT

lookup(key): key값을 가지는 노드를 리턴하고, 없다면(NULL일시) NULL의 부모를 리턴한다
put(key): key값을 가지는 노드에 삽입한다.
delete(key): key값을 가지는 노드를 삭제한다.

구현

이진탐색트리 구현의 핵심은 계속 중위순회순으로 정렬된 상태를 유지하는 것이다.

탐색

루트에서 시작해서 노드의 값이 탐색값보다 크면 left child로 탐색, 작으면 right child로 탐색을 반복하면 된다.

삽입

삽입은 탐색을 한 후 값을 변경하거나 추가만 해주니 단순하다. 경우를 나누어 보자면, 탐색하여 노드를 발견했다면 그대로 값을 수정하면 되고, 값을 발견하지 못한다면 탐색으로 얻은 부모의 노드 값을 기준으로 작다면 left child에, 크다면 right child에 노드를 생성하여 삽입하면 된다.

삭제

삭제는 우선 탐색을 진행하여 위치를 찾은 후 3가지 분기로 나뉜다.

1. 자식 노드가 없다면 그대로 삭제하면 된다.

2. 자식 노드가 있다면, left child 하위의 노드 중 가장 큰 값 또는 right child 하위의 노드 중 가장 작은 값((in-order successor)을 삭제한 노드의 위치로 이동해 주면 된다. 이때 아래 노드를 삭제하여 불균형이 한번 발생할 수 있는데, in-order successor의 정의에 따라서 자식은 최대 하나뿐이기 때문에, 이런 불균형은 최대 1번 발생하고, 그에 따라 구현시에 예외처리를 한 번만 해주면 된다.

효율

이진탐색트리의 탐색, 삽입, 삭제는 모두 O(h)의 효율로 가능하다. 그렇기에 트리의 불균형을 최대한 해소하여 트리의 높이를 최소한으로 유지하여야 O(log n)의 최적화된 성능을 낼 수 있다. 불균형을 해소하지 않을 경우에는, 최악의 경우에는 O(n)의 시간이 걸릴 수도 있다. 그렇기에 이런 최적화를 위해서 AVL 트리나, 레드-블랙 트리등의 구현방식이 있다.