[알고리즘설계] 이진 탐색 트리1
[알고리즘 설계] 이진 탐색 트리
- 이진 탐색 트리에 대한 기본 연산은 트리의 높이에 비례하는 시간에 수행.
- 완전 이진 탐색 트리의 기본 연산은 최악의 경우 O(logn) 에 실행.
- 트리가 n개의 노드가 선형으로 연결된 모양인 경우 평균 Θ(n) 시간에 수행된다.
- 기본 연산들에 대해서 최악의 경우에 빠른 실행 속도를 보장할 수 있는 이진 검색 트리의 변형을 설계할 수 있음.(BBST)
이진 탐색 트리의 개념
- x를 이진 탐색 트리의 한 노드라고 할 때, y가 x의 왼쪽 서브트리의 한 노드면 y.key<= x.key를 만족하고 y가 x의 오른쪽 서브 트리의 한 노드면, y.key >=x.key를 만족한다.
- 이진 탐색 트리 특성에 의해 중위 트리 순회를 이용하여 이진 검색 트리의 모든 키를 정렬된 순서로 출력할 수 있다.
INORDER-TREE-WALK(x)
if x != NILL
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)
- 이진 검색 트리를 순회하는데는 Θ(n) 시간이 걸린다.
이진 탐색 트리 순회 증명 (Θ(n))
- n개의 노드로 이루어진 서브트리의 루트에 대해서 호출했을 때 걸리는 시간을 T(n)이라 할때, n개의 노드들 모두를 방문하기 때문에 하계는 T(n)=Ω(n)이 된다.
- T(n)=O(n)을 증명하면 된다.
- 빈트리인 경우 경미한 상수 시간이 걸리므로 T(0)=c (c>0) 이 된다.
- n>0 인 경우 왼쪽 서브트리는 k개의 노드를 가지고, 오른쪽 서브트리는 n-k-1 개의 노드를 가지는 노드 x에 대해 호출되었다고 가정하면, T(n)<= T(k)+T(n-k-1)+d 이고, d는 재귀 호출에 걸리는 시간외의 상한을 반영한 값.
- T(n) <= (c+d)n + c 를 보이면 된다.
n=0 일 때, (c+d)*0+c=c=T(0) 이므로 만족.
n>0 일 때,
T(n) <= T(k)+T(n-k-1)+d
<= ((c+d)k+c)+((c+d)(n-k-1)+c)+d
= (c+d)n+c 이므로 만족.
이진 탐색 트리에 대한 질의
- search, minimum, maximum, successor, predecessor 에 대해서 다뤄본다.
검색
- 이진 탐색 트리에서 주어진 키를 가지는 노드를 검색할 때, 트리의 루트에 대한 포인터와 키 k가 주어진다. 키가 k인 노드가 존재하면 이 노드에 대한 포인터를 리턴, 존재 하지 않을 경우에는 NIL을 리턴한다.
TREE-SEARCH(x,k)
if x==NIL or k==x.key
return x
if k < x.key
return TREE-SEARCH(x.left,k)
else return TREE-SEARCH(x.right,k)
- 루트에서 검색을 시작해 트리의 단순 경로 하나를 따라 내려가게 된다. 만나게 되는 노드 중 키값이 주어진 키 값과 일치하면 반환, 리프 노드까지 내려가서 없으면 끝난다. 그 경로 외에는 이진탐색 트리의 특징에 의해 키값이 존재할 수 없다.
- 트리의 높이가 h일 때, TREE-SEARCH의 수행시간은 O(h)가 된다.
최소원소와 최대원소
- 최소원소는 루트로부터 NIL을 만날때까지 왼쪽자식을 계속 따라가면 된다. 최대 원소 또한 루트로부터 NIL을 만날때까지 오른쪽 자식을 계속 따라가면 된다.
TREE-MINIMUM(x)
while x.left != NIL
x = x.left
return x
TREE-MAXIMUM(x)
while x.right != NIL
x = x.right
return x
- 이진탐색트리의 특성은 TREE-MINIMUM과 TREE-MAXIMUM의 정확함을 보장한다.
- 역시 모두 높이가 h인 트리에 대해 O(h) 수행시간을 가지는데, 만나게 되는 모든 노드가 루트로부터 내려가는 하나의 단순 경로에 존재하기 때문이다.
직후원소와 직전원소
- 하나의 노드의 직후 원소와 직전 원소를 구하는 방법은 간단하다. 이진 탐색 트리의 구조를 통해서 한 노드의 직후원소와 직전원소를 를 키 값의 비교 없이 찾을 수 있다.
- x의 직후 원소를 구하려 할때, x가 오른쪽 서브트리가 있는 경우는 그 오른쪽 서브트리의 가장 작은 원소가 x의 직후 원소가 된다.
- x가 오른쪽 서브트리가 없는 경우는 y가 x의 직후원소라 할때, y는 자신의 왼쪽 자식도 x의 조상인(자신도 자신의 조상으로 간주) 조상 노드 중 가장 낮은 노드가 된다.
- 높이가 h인 트리에 대한 TREE-SUCCESSOR의 수행 시간은 O(h)이다. 트리의 단순 경로 하나를 따라 올라가거나 내려가기 때문.
댓글남기기