이진 탐색 트리(BST) 개념

* 이진 탐색 트리(BST, Binary search tree)

  이진 트리에서 사용할 수 있는 이진 탐색 트리 개념과 단점 그리고 그 개선안에 대해 작성하고자 한다.

- 이진 탐색 트리에서 사용하는 구조체에 쓰이는 데이터는 아래와 같다.

  1. left - 왼쪽 자식 포인터. left.key <= key를 만족한다.

  2. right - 오른쪽 자식 포인터. right.key >= key를 만족한다.

  3. key - 비교 대상 데이터.

  4. satellite data - 부속 데이터.

  5. p - 부모 노드 포인터.

- 정렬된 데이터 얻기

  1. y가 x의 왼쪽 서브 트리의 한 노드라면 y.key <= x.key를 만족한다.

  2. y가 x의 오른쪽 서브 트리의 한 노드라면 y.key >= x.key를 만족한다.

  따라서 중위 순회 결과(Inorder)는 정렬된 데이터를 얻을 수 있음을 알 수 있다.

* 기능

1. 검색

  딱 맞는 키가 있거나 그 값이 NIL이면 해당 노드 포인터를 반환한다.

  시간 복잡도는 O(h)

2. 최대 원소와 최소 원소

  최소는 왼쪽 자식으로만 찾아간다. 최대는 오른쪽 자식으로만 찾아가면 된다. 이것이 가능한 이유는 이진 검색 트리의 특성때문이다.

  시간 복잡도는 O(h)

3. 직후 원소(SUCCESSOR), 직전 원소(PREDECESSOR)

  직후 원소는 현재 노드 x에 대해 x.key보다는 큰 노드들 중에 가장 작은 키를 가지는 노드를 말한다. 마찬가지로 직전 원소는 x.key보다는 작은 노드들 중에서 가장 큰 키를 가지는 노드를 말한다.

  직후원소와 직전원소는 SEARCH, MINIMUM, MAXIMUM으로 구현이 가능하다. 직후 원소의 경우 x.right가 존재한다면 TREE-MINIMUM으로 찾을 수 있고, 없다면 이 x가 포함하는 서브트리를 왼쪽 자식(left)로 갖는 조상을 찾으면 된다.

  시간 복잡도는 O(h)

4. 삽입

  순회할 변수와 그의 부모 변수를 지정하여 검색과 비슷하게 iterative하게 위치를 찾는다. 부모 변수가 필요한 이유는 삽입하는 데이터 위치는 찾으면 그 값은 NIL이니 그 이전 값이 필요하기 때문이다. 다음으로 삽입할 위치를 선택한다.

  시간복잡도 O(h)

5. 삭제

  세 가지 경우가 있다.

  1. 자식이 없는 경우

단순 삭제. 부모에 대한 자식 포인터를 NIL로 변경한다.

  2. 자식이 하나 있는 경우

그 자식 트리를 그대로 삭제 노드 위치에 이식(Transplant)한다.

  3. 자식이 두 개 있는 경우

핵심은 직후 원소를 삭제 노드에 이식하는 것이다. 우측 서브트리의 직후 원소는 TREE-MINIMUM으로 쉽게 찾을 수 있다. 삭제 노드를 z, z의 우측 노드 r, 직후 원소 y, y의 오른쪽 자식 x라고 하자.

우선 y를 z위치로 옮기기 전에, y에 x를 이식한다. 다음으로 y를 z 위치로 이식하기 위해 y.right와 r.p를 재설정한다. 마지막으로 z위치에 y를 이식하고, 왼쪽 자식에 대한 y.left와 왼쪽 자식의 p 변수를 설정한다.

  시간복잡도 O(h)