BST에 대해 학교에서도 배우고, 여러 알고리즘 강의에서도 들어 개념은 이해한다 생각했지만, swift로 구현하는 것에 늘 어려움을 느끼고 있었다. 구현하지 못하면 아는것이 아니기에 이번 기회에 제대로 swift로 주요 알고리즘을 구현해보려고 한다.
Reference : Jonathan강의 참고
Node 클래스
class Node {
var key: Int = 0
var left: Node?
var right: Node?
init(_ key: Int) {
self.key = key
}
/// minimum 값 구하기 위한 멤버변수
var min: Node {
if left == nil { // 자신보다 더 작은게 없으면 자기자신 반환
return self
} else { // 그렇지않으면 left 노드의 min 노드 다시 반복
return left!.min
}
}
}
BST에서 사용할 Node 클래스를 선언해준다.
key는 해당 노드가 가지고 있는 값, left right 는 각각 왼쪽 혹은 오른쪽 child 노드이다. child 노드가 없을 수 있으므로 optional로 선언한다.
min은 자신 node를 기준으로 최소값을 찾기 위한 멤버변수이다. 자기자신보다 더 작은 노드가 없으면 자기자신을 반환하고, 작은게 있으면 그 작은 노드에서 다시 min 을 찾는다.
(left인 이유는 트리구조에서는 left child node 가 무조건 parent node 보다 작으니까!)
BST 클래스
이제 본격적으로 BST 클래스를 구현해보자.
우선 트리의 root를 선언해준다.
class BST {
var root: Node?
}find
private func find(_ node: Node?, _ key: Int) -> Node? {
guard let node = node else { return nil }
if node.key == key {
return node
} else if key < node.key { // 찾는 키가 더 작으면
return find(node.left, key) // 왼쪽에서 다시 find() 수행
} else if key > node.key { // 찾는 키가 더 크면
return find(node.right, key) // 오른쪽에서 다시 find() 수행
}
return nil
// Note: duplicate keys not allowed so don't need to check
}
파라미터로 찾고자 하는 노드와 그 노드의 key 값을 받는다.
node의 key값보다 찾는 키가 작으면 왼쪽 child를 기준으로 다시 순회하고, 큰 경우는 오른쪽 child 노드를 기준으로 다시 순회한다.
key값이 같으면 해당 노드를 반환한다.
해당 로직을 이용해 키를 반환하는 멤버함수는 다음과 같이 구현할 수 있다.
func find(key: Int) -> Int? {
guard let root = root else { return nil }
guard let node = find(root, key) else { return nil }
return node.key
}node가 key를 찾을 때 까지 find(node, key) 를 재귀호출하고, 끝끝내 찾지 못하면 nil을 반환한다.
Insert
insert 할 때 핵심은 트리에서 올바른 위치에 넣는 것이다. parent node의 왼쪽은 작게, 오른쪽은 커야하므로 이를 만족하도록 조건을 짜면,
private func insertItem(_ node: Node?, _ key: Int) -> Node {
// 새로운 node 생성, 주어진 Key를 노드에 세팅
guard let node = node else {
let node = Node(key)
return node
}
if key < node.key { // 삽입하려는 key가 더 작은 경우
node.left = insertItem(node.left, key) // 왼쪽 child에 삽입하고
}
if key > node.key { // 삽입하려는 Key가 더 큰 경우
node.right = insertItem(node.right, key) // 오른쪽 child에 삽입한다
}
return node;
}삽입 로직이 담긴 insertItem() 멤버함수를 활용해 다음과 같이 insert 를 수행할 수 있다.
func insert(key: Int) {
root = insertItem(root, key) // root : top에서 시작할거니까
}만약 5 3 2 4 7 6 8 순서로 삽입해 트리를 만든다고 하자.
bst.insert(key: 5)
//
// insertItem(node, key) 가 호출되며 key 값이 5인 노드 삽입 (child가 없으므로 조건문은 패스)
// insertItem(node, key) 가 반환하는 Node가 root로 들어온다
bst.insert(key: 3) // 5가 있는 상태에서 3을 삽입한다. 5보다 작으므로 왼쪽에 삽입된다.
bst.insert(key: 2) // 2는 5보다 작아서 왼쪽 -> 3보다 작아서 왼쪽 -> 반환
bst.insert(key: 4) // 4는 5보다 작아서 왼쪽 -> 3보다 크니까 오른쪽 -> 반환
bst.insert(key: 7) // 7은 5보다 크니까 오른쪽 -> 반환
bst.insert(key: 6) // 6은 5보다 크니까 오른쪽 -> 7보다 작으니까 왼쪽 -> 반환
bst.insert(key: 8) // 8은 5보다 크니까 오른쪽 -> 7보다 크니까 오른쪽 -> 반환 이렇게 트리가 완성되었다.
delete
이제 트리에서 특정 노드를 삭제하는 로직을 구현해보자.
세 가지 경우가 존재할 수 있다.
1) child가 없는 경우 : 해당 node를 그냥 삭제하면 된다
2) child가 하나인 경우 : child node의 key와 대소비교해 자리를 바꾼 후
→ ① child가 작은 경우 (parent 왼쪽에 있는 경우)
② child가 큰 경우 (parent 오른쪽에 있는 경우)
3) child가 세 개인 경우
private func delete(_ node: inout Node?, _ key: Int) -> Node? {
guard let nd = node else { return nil }
if key < nd.key {
nd.left = delete(&nd.left, key)
} else if key > nd.key {
nd.right = delete(&nd.right, key)
} else {
// case 1 : child가 없는 경우 (왼, 오 노드 모두 nil인 경우)
if nd.left == nil && nd.right == nil {
node = nil // 바로 해당 노드를 지우면 된다
}
// case 2 : child가 하나 있는 경우
else if nd.left == nil { // 왼쪽 노드가 nil인 경우
node = nd.right // 현재 노드를 오른쪽 child 노드로 대신해서 현재 노드를 삭제
}
else if nd.right == nil { // 오른쪽 노드가 nil인 경우
node = nd.left // 현재 노드를 왼쪽 child 노드로 대신해서 현재 노드를 삭제
}
// case 3 : child가 두 개 있는 경우
else {
// 1) 노드의 오른쪽에서 최소값을 찾는다 (= 노드의 왼쪽에서 최대값을 찾아도 됨)
let minRight = findMin(nd.right!)
// 2) 찾은 값을 복사해서 노드로 넣어준다
nd.key = minRight.key
// 3) 복사하기 전 노드 ( 1)에서 찾은 노드)를 삭제한다
nd.right = delete(&nd.right, nd.key)
}
}
return nd
}
Case 2 : child가 한 개인 경우
case 2 의 경우 삭제하려는 노드 자리에 child 노드를 넣어주는 것이다.
삭제하려는 노드 (nd 의 왼쪽)이 없으면 오른쪽 노드를 삭제하려는 노드로 바꿔준다.
if nd.left == nil {
node = nd.right
}delete 로직을 호출해 삭제를 진행한다.
func delete(key: Int) {
guard let _ = root else { return }
root = delete(&root, key);
}
delete함수가 호출되면 해당 함수는 재귀적으로 트리를 탐색하며 삭제할 노드를 찾는다- 삭제할 노드를 찾으면, 해당 노드를 삭제하고 변경된 트리의
루트 노드를 반환한다. - 반환된 루트 노드를
root에 다시 할당해 전체 트리의 루트를 업데이트한다.
inout
여기서 파라미터에inout키워드를 붙이게 되면, 참조에 의한 전달 (pass by reference) 을 하게 된다.
(기본적으로는 pass by value 이므로 파라미터로 주어진 값이 변하지 않는다.)
Case 3. Child가 두 개인 경우
5
/ \
3 8
/ \
7 9트리에서 5를 삭제해보자.
- 오른쪽 서브트리에서 최소값을 찾는다. (왼쪽에서 최대값을 찾아도 무방)
: 노드 5의 오른쪽에서 최소값을 찾으면7이다 - 삭제하려는 노드에 해당 노드를 복사한다
: 찾은 최소값7을5로 복사한다.7 / \ 3 8 \ 9 - 복사된 원래 노드 삭제
: 위 과정을 재귀적으로 반복한다. 만약에 서브트리가 있다면, 다시 그 서브트리에서delete(node, key)메서드를 호출하는 것이다.
case 3의 3번 스텝이 이해가지 않았는데, BST의 경우 조건을 만족할 때 까지 재귀적으로 호출하는 것을 이해하는게 핵심이었다.
다음 포스팅에서는 BST를 이용한 문제풀이를 진행할 것이다.
알고리즘 정복하는 그 날까지 쭉!
