Algorithm - 9. BST

Mingi Shin·2023년 10월 22일

algorithm

목록 보기

9/23

무순리스트에 대한 사전 탐색은 선형탐색을 사용하고 순서리스트에 대한 사전 탐색은 이진탐색을 사용한다. 해당 포스팅에서는 리스트로 구현한 사전이 아닌 이진트리로 구현한 사전 탐색 방법을 알아볼 것이다.

이진트리를 구현하는 방식에 따라 탐색 트리를 이진탐색트리, AVL 트리, 스플레이 트리 3가지로 나눌 수 있다. 먼저 이진탐색트리(Binary Search Tree)를 알아보자.

이진탐색트리

u, v, w는 모두 트리 노드이며 u와 w가 각각 v의 왼쪽과 오른쪽 부트리에 존재할 때, key(u) < key(v) < key(w)가 성립하는 이진트리를 이진탐색트리라 한다.

이진 탐색의 정의는 이렇다. 어렵게 쓰여진 것 같지만 그림으로 이해하면 매우 쉽다.

이진탐색드리는 중복키를 허용하지 않는다는 전제에서 부모, 왼쪽 자식, 오른쪽 자식이 있을 때 트리 전체는 왼쪽 자식 < 부모 < 오른쪽 자식 을 만족해야 한다. 이렇게 구현이 되면 이진탐색트리를 중위순회하였을 때 노드를 오름차순으로 방문한다. (1, 2, 7, 9, 11, 15).

BST 역시 사전 데이터 구조 중 하나며 탐색, 삽입, 삭제가 주요 메서드다.

탐색

Alg searchBST(v, k)
	input node v, key k
    output node with key k or externalNode

if(isExternal(v))
	return v

if(key(v) = k){
	return v
} else if(key(v) > k){		//키값보다 크면 작은 걸 찾아야 함.
	return searchBST(left(v), k)
} else{						//키값보다 작으면 큰 걸 찾아야 함.
	return searchBST(right(v), k)
}

BST를 탐색하는 함수는 재귀로 짜여진다. 키값과의 비교를 통해 적절하게 자식을 찾아 내려간다. 그런데 여기서 외부노드를 만나도 NoSuchKey와 같은 Exception을 반환하지 않고 해당 외부노드 그대로를 반환하고 있다.

삽입

Alg insert(k, e)
	input key k, element e
    output none

insertNode <- searchBST(root(), k)

if(!isExternal(insertNode)){	//searchBST 했는데 원소가 있는 노드를 만나면
	return
} else{
	key(insertNode) <- k, element(insertNode) <- e
    expandExternal(insertNode)
}
return

searchBST()는 탐색 이외에 삽입을 위한 메서드이기도 하다(삭제에서도 쓰인다.). 성공적인 insert 작업을 하기 위해서는 k에 대한 노드를 찾으면 안 된다.

8을 삽입한다고 하자. insertNode는 searchBST(root(), 8)의 리턴값으로 노드를 찾는다. 그 결과는 7 노드의 오른쪽 자식이 되는데 이는 left와 right가 NULL상태로 초기화된 외부노드다.

else 구문의 마지막 expandExternal()을 주목할 필요가 있다. 메서드 이름에서 유추할 수 있듯이 키와 원소를 집어넣고 외부노드 상태인 현재노드를 내부노드로 확장시키는 삽입을 위한 메서드다.

노드 확장 메서드

Alg expandExternal(node)
	input external node
    output none

left(node), right(node) <- getNode()

parent(left(node)), parent(right(node) <- node
left(left(node)), right(left(node)) <- NULL
left(right(node)), right(right(node)) <- NULL
return

파라미터 노드는 자식들을 확장하고 자신을 내부노드로 만든다. 확장된 자식들은 외부노드가 된다.

삭제

탐색, 삽입에 비해 삭제는 조금 머리가 아프다. remove()의 메서드 로직이 기본적으로 복잡하고 여기에 중위순회후계자를 찾는 메서드가 새롭게 추가된다. 또한, 연결리스트 트리 구조로 구현된 힙의 삭제 메서드에 쓰이는 reduceExternal()이라는 메서드도 생각을 요구한다.

기본적인 BST의 삭제 알고리즘 의사코드는 다음과 같다.

Alg remove(k)
	input key k
    output element with key k

rmNode <- searchBST(root(), k)

if(isExternal(rmNode))
	return NoSuchKey

retKey <- element(rmNode)	//추후 리턴해줄 것

rmChild <- left(rmNode)		//rmNode에게 자식이 있는가?
if(!isExternal(rmChild))
	rmChild <- right(rmNode)

if(isExternal(rmChild)){	//rmNode에게 자식이 하나라도 없으면
	reduceExternal(rmChild)
} else{						//rmNode에게 자식이 모두 있으면
	succ <- inOrderSucc(rmNode)
    succChild <- left(succ)
    key(rmNode) <- key(succ), element(rmNode) <- element(succ)
    reduceExternal(succChild)
}
return retKey

먼저 삭제할 노드를 찾는데 탐색 결과가 외부노드라면 Exception을 리턴한다.

다음은 삭제할 노드에게 자식이 있는지 없는지 검사한다. 여기서는 2가지 케이스를 나누기 위함인데, 왼쪽 오른쪽 모두 자식이 내부노드로 있는 경우와 그 외의 경우다.

만약 자식이 꽉 차 있는게 아니라면(rmChild가 외부노드라면), rmChild를 reduceExternal()에 전달해 작업한다.

자식이 꽉 차 있는 경우라면, 삭제할 노드의 중위순회후계자를 찾고 삭제할 노드 위치에 키와 원소를 중위순회후계자의 데이터로 덮어버린다. 그리고 중위순회후계자의 왼쪽 자식을 reduceExternal()에 전달해 작업한다.

노드 축소 메서드

Alg reduceExternal(exNode)
	input external node exNode
    output exNode's sibling replacing parent node of removed exNode
    
exParent <- parent(exNode)
exSibling <- sibling(exNode)

if(isRoot(exParent)){
	root <- exSibling
    parent(exSibling) <- NULL
} else{
	exGrandParent <- parent(exParent)
    exSibling <- exGrandParent
    
    if(left(exGrandParent) = exParent){
    	left(exGrandParent) <- exSibling
    } else{
    	right(exGrandParent) <- exSibling
    }
}

putNode(exParent)
putNode(exSibling)
return exSibling

노드 축소 메서드는 외부노드를 전달 받아 그 외부노드의 형제를 리턴한다. remove()에서 자식 여부를 case로 나눈 이유다. 어느 한 쪽이라도 자식이 없다면 바로 그 노드를 전달해서 reduceExternal() 작업을 하면 되기 때문이다.

먼저 외부노드의 부모노드와 형제노드를 설정한다. 그리고 이 부모노드가 루트인지 아닌지를 확인한다. 만약 부모노드가 루트라면 루트와 형제노드를 바로 연결시킨다.

부모노드가 누군가의 자식노드라면 부모노드의 부모를 찾아 연결해준다.

중위순회후계자 탐색

remove()에서 자식이 꽉 차 있으면 중위순회후계자를 찾는 작업을 추가로 했다. BST 자체가 중위순회를 돌면 오름차순이 되어야 하는 트리의 규칙을 유지하기 위해 중위순회후계자를 찾아 데이터를 삭제할 곳에 덮어버리기 위해서다.

Alg inOrderSucc(node)
	input internal node that will be removed
    output inorder successor of node

succ <- right(node)

if(isExternal(succ))
	return invalidException

while(!isExternal(left(succ)){
	succ <- left(succ)
}
return succ

해당 알고리즘은 전달된 노드의 중위순회후계자를 찾아 반환한다.

먼저 succ 변수에 전달된 노드의 오른쪽 자식을 전달한다. 그리고 succ에 대한 유효성 검사를 한다. succ이 외부노드를 가리키고 있다면 exception을 터트린다. 왜 그럴까?

현재 함수는 자식이 꽉 차 있는 case에서 호출이 된다. 따라서 오른쪽 자식이 없는 경우는 유효한 경로가 아니다.

이후 succ은 반복문을 타고 왼쪽 자식이 내부노드인 동안 왼쪽 자식으로 계속 내려간다. 진행 중 왼쪽 자식이 외부노드인 것을 만나면 더 이상 내려가지 않고 루프를 빠져 나와 반환한다. 이 반환 노드가 전달된 노드(삭제 메서드에서는 삭제할 노드)의 중위순회후계자가 된다.

else{						//rmNode에게 자식이 모두 있으면
	succ <- inOrderSucc(rmNode)
    succChild <- left(succ)
    key(rmNode) <- key(succ), element(rmNode) <- element(succ)
    reduceExternal(succChild)
}

여기서 remove() 알고리즘의 일부를 다시 확인해보자. inOrderSucc() 작업을 마치고 succ을 찾은 후 reduceExternal()에 succ의 왼쪽 자식을 전달하는 이유가 바로 inOrderSucc()이 이미 왼쪽 자식을 검사했기 때문이다. 왼쪽 자식이 외부노드임을 알고 succ을 반환했기 때문에 succ의 left child는 무조건 외부노드일 수밖에 없다.

성능

지금까지 BST의 탐색, 삽입, 삭제를 공부했다.

탐색은 값을 비교하며 트리의 높이를 계속해서 내려 간다. 삽입은 탐색을 통해 삽입할 노드 위치를 잡고 데이터를 삽입 후 노드를 확장한다. 삭제는 탐색을 통해 삭제할 노드를 찾고 노드의 자식이 꽉 차 있는지 아닌지에 따라 case를 나눈다. 그 후 reduceExternal() 작업을 수행하는데 자식이 꽉 차 있는 경우에는 중위순회후계자를 찾아 그 왼쪽 자식을 reduceExternal()의 파라미터로 전달한다.

세 메서드 모두 공통적으로 트리의 깊이만큼 시간이 소요되는 탐색 작업을 하고 있다. 삽입은 이외에 데이터를 넣고 노드를 확장하지만 이들은 O(1)에 수행된다. 삭제는 reduceExternal()이 코드 상 복잡해 보이지만 결국 노드를 떼었다 이어붙이는 작업에 불과해 O(1)이다. 중위순회후계자를 찾는 작업 역시 트리의 높이에 의존한다.

결과적으로 주요 메서드들의 성능은 트리의 높이에 의존한다.