[검색 트리] 이진 검색 트리(Binary Search Tree, BST)
특성
1. 각 노드는 unique한 key 값을 하나씩 가진다.
: 이 때 key 값은 여러 개의 field로 구성될 수 있다. 만약 여러 개의 field로 구성될 경우, lexicographical order를 따르면 된다.
2. 각 노드는 최대 2개의 child node를 가진다.
3. 모든 노드에 대해 그 key 값을 x라고 하면, 해당 노드의 left subtree에는 x보다 작은 key 값을 가진 노드가 들어가고, right subtree는 그 반대이다.
$\rightarrow$ 트리의 모양이 한쪽으로 skew되어 있을 수도 있다.
: BST에서의 검색, 삽입, 삭제 연산의 시간복잡도는 트리의 높이에 따라 달라지므로, 각 연산의 최악의 경우 시간복잡도는 $O(n)$에서 $O(logn)$ 사이에서 결정된다.(라고 책에 되어 있는데, 평균 시간복잡도와 관련이 어떻게 있는 것인지? 평균 시간복잡도는 $O(logn)$이다. 출처 : stackoverflow.com/questions/30116387/time-complexity-of-bst)
검색
핵심 기능 : 트리의 root node와 찾고자 하는 key값을 받아서, 해당 key값을 가진 노드가 존재하는 경우 해당 노드를 return하고, 그런 노드가 존재하지 않을 경우 NIL값을 return한다.
구현 : Recursive한 방식으로 구현한다.
treeSearch(t, x)
{
if(t=NIL or key[t]=x) then return t
//t=NIL : x에 해당하는 노드를 찾지 못하고 트리 끝에 도달한 경우
//-> 이 때 NIL을 리턴하면 호출한 곳에서 못찾았구나! 라고 이해
//key[t]=x : x에 해당하는 노드를 찾은 경우
if(x<key[t])
then return treeSearch(left[t], x);
// BST의 성질에 의해
// 현재 보고 있는 노드보다 찾는 key가 작기 때문에 left subtree에서 다시 검색한다.
else
return treeSearch(right[t], x);
// BST의 성질에 의해
}
삽입
1. 겹치는지 search
2. 겹치지 않으면 삽입 : 삽입할 곳을 찾으면 거기 삽입한 후에 삽입이 완료된 노드를 리턴한다.
treeInsert(t, x){
//t==NIL -> 앞선 과정이 제대로 수행되었다면 여기가 target노드가 들어갈 자리이다.
if(t=NIL) then
key[r] <- x; left[r] <- NIL; righr[r] <-NIL;
return r;
//아닌 경우, 어느 subtree에 들어갈 노드인지 판단하여 재귀호출.
//직접적으로 트리의 구조가 바뀌기 때문에 재귀호출이 끝난 뒤 받은 값(수정된 subtree)을
//지금 보고 있는 노드의 원래 subtree에 넣어주는 과정이 필요하다.
if(x<key[t]) then
left[t] <- treeInsert(left[t], x) return t;
else right[t]<- treeInsert(right[t], x) return t;
}
삭제
: 삭제의 경우 삭제 target이 해당 트리의 child node에 따라 트리에 구멍이 뚫릴 수 있다.
: 상황에 맞게 구멍을 메꾸는 작업을 해야 할 수 있으므로 여러 Case를 나눈다.
CASE 1 - target 노드의 child노드 개수 == 0
CASE 2 - target 노드의 child노드 개수 == 1
CASE 3 - target 노드의 child노드 개수 == 2
CASE 1 - target 노드의 child노드 개수 == 0
: target노드는 리프노드이거나 루트이다.
: 이 경우 삭제해도 트리에 구멍이 없으니 그냥 삭제한다.
CASE 2 - target 노드의 child노드 개수 == 1
: target노드는 왼쪽 호은 오른쪽 child를 가진다.
: 이 경우 삭제하면 target node의 child를 루트로 하는 subtree가 원래 tree와 끊어짐
해결방법 ) BST의 성질에 의해, target node의 왼쪽 child를 루트로 하는 subtree의 모든 노드들의 key는 target node의 parent node의 key보다 작다. $\rightarrow$ 즉, 해당 subtree를 target node의 parent node의 왼쪽(원래 target node의 자리)에 바로 붙여도 트리 성질을 만족할 수 있다.(vice versa)
CASE 3 - target 노드의 child노드 개수 == 2
: target노드는 양쪽 child를 가진다.
: 이 경우 삭제하면 target node의 child를 루트로 하는 subtree가 원래 tree와 끊어짐
해결방법 ) 이 경우 CASE2처럼 바로 붙일 수 없다. 이 경우 subtree 내에서 target node를 대신할 무언가 찾아서 target node를 대체하고, 대체가 완료된 subtree를 target node의 parent의 왼쪽 혹은 오른쪽에 붙이면 된다.(어디에 붙일지는 원래 target node가 어디에 붙어있었느냐에 따라 결정된다.) target node를 대체할 노드는 트리 성질을 만족시켜야 하므로, target node의 successor 혹은 preccesor가 되어야 한다.
종합 수도코드 :
treeDelete(t, r)
//t는 tree의 root, r은 삭제될 노드이다.
{
if(t=NIL) then
deleteNode(t);
}