이전 글에 이어서, 이진 탐색 트리 구조의 알고리즘을 구현해보겠습니다.
이진 탐색 트리의 특징을 활용한 알고리즘은 크게 3가지가 있습니다.
>> 탐색/삽입/삭제
탐색 알고리즘
이진 탐색 트리의 특징을 이용하면 아래와 같은 개념-순서를 통해서 탐색 알고리즘을 구현할 수 있습니다.
1️⃣ 찾고자 하는 값을 루트 노드의 값과 비교합니다.
2️⃣ 찾고자 하는 값이 루트 노드의 값보다 작으면 >> 탐색은 루트 노드 기준으로 왼쪽 서브 트리를 기준으로 다시 시작합니다.
3️⃣ 찾고자 하는 값이 루트 노드의 키 값보다 크면 >> 탐색은 루트 노드 기준으로 오른쪽 서브 트리를 기준으로 다시 시작합니다.
위의 규칙을 바탕으로 swift 언어로 구현을 해보겠습니다.
func search(from data: T) -> Bool {
// 루트 노드가 비어있다면 종료
if root == nil { return false }
// 루트 노드의 값과 사용자가 찾고자 하는 값을 비교
var currentNode = root
while let node = currentNode {
// 만약 값이 동일하다면, true 반환
if node.data == data {
return true
}
// 만약 사용자가 찾고자 하는 값이 상위 노드의 값보다 작으면 왼쪽 서브 트리로 이동해서 탐색
if node.data > data {
currentNode = node.left
} else {
// 만약 사용자가 찾고자 하는 값이 상위 노드의 값보다 크면 오른쪽 서브 트리로 이동해서 탐색
currentNode = node.right
}
}
return false
}
삽입 알고리즘
삽입 알고리즘은 트리 구조의 특정 위치에 해당 값을 넣는 것을 말합니다.
가장 먼저 특정 값을 넣고자 하는 위치를 알아야 합니다. 그 위치를 알아야 데이터를 삽입할 수 있기 때문입니다. 그리고 해당 데이터가 이미 존재하는 값인지, 추가해도 되는 값인지 알아야 하므로 탐색을 먼저 해야 합니다.
>> 탐색 후 그 값이 없는 위치가 해당 데이터를 삽입하는 위치가 됩니다.
🤔 왜 탐색이 실패한 위치가 새로운 노드를 삽입하는 위치가 되는가?
✔️ 9를 넣고자 할 때, 루트 노드부터 시작해서 이진트리 구조를 탐색하게 됩니다.
✔️ 18보다 작은 값이므로, 왼쪽 서브 트리로 이동합니다. 9는 7보다 큰 값이므로 오른쪽 서브 트리로 이동합니다.
✔️ 이동 후, 다시 값을 비교했을 때 여전히 9와 일치하지 않기 때문에 탐색 알고리즘에 따라 false로 종료됩니다.
func insert(_ data: T) {
guard let root = self.root else {
return self.root = Node.init(data: data)
}
var currentNode = root
// 탐색 이후 값이 일치 하지 않게 되는 그 위치가 특정 값을 삽입하는 위치가 되므로 해당 위치에 노드를 생성/삽입합니다.
while true {
if currentNode.data > data {
guard let nextNode = currentNode.left else {
return currentNode.left = Node.init(data: data)
}
currentNode = nextNode
} else {
guard let nextNode = currentNode.right else {
return currentNode.right = Node.init(data: data)
}
currentNode = nextNode
}
}
}
삭제 알고리즘
삭제 알고리즘은 이진 탐색 트리 알고리즘 중에서 가장 복잡합니다.
삭제 알고리즘도 삽입 알고리즘과 마찬가지로 탐색을 먼저 해야합니다. 삭제하고자 하는 키 값이 트리 구조 안 어디에 위치하는지 알아야 삭제할 수 있기 때문입니다. 노드를 탐색했다면, 아래의 3가지 경우를 고려해야 합니다.
- 삭제하려는 노드가 단말 노드일 경우
- 삭제하려는 노드가 하나의 서브 트리를 갖고 있는 경우
- 삭제하려는 노드가 두 개 이상의 서브 트리를 모두 갖고 있는 경우
먼저, 첫번째 경우에 대해서 알아보겠습니다.
✔️ 단말 노드일 경우
>> 이 경우는 단순합니다.
1️⃣ 삭제하고자 하는 값을 갖고 있는 노드의 부모 노드를 찾습니다.
2️⃣ 부모 노드와의 연결을 끊기 위해 해당 노드의 값을 nil로 지정하면 됩니다.
✔️ 하나의 서브 트리만 갖고 있는 경우
>> 특정 노드가 삭제되면 특정 노드의 부모와 특정 노드의 자식이 연결되어야 합니다. 이때, 특정 노드의 자식이 하나이므로 값에 대한 분기 처리가 필요하지 않고 바로 연결하면 됩니다.
1️⃣ 삭제하고자 하는 값을 갖고 있는 노드(= 특정노드)의 부모 노드를 찾습니다.
2️⃣ 부모 노드의 브랜치와 연결된 값을 특정 노드와 연결하면 됩니다.
✔️ 두 개 이상의 서브 트리를 모두 갖고 있는 경우
>> 위의 그림에서 18의 값을 삭제하는 상황이라고 가정해보겠습니다. 크게 두 가지 단계를 통해서 삭제할 수 있습니다.
1️⃣ 18을 삭제
2️⃣ 35와 연결할 값을 찾아서 연결
>> 🤔 어떤 값을 연결해야 하는가?
- 18의 왼쪽 서브 트리에서 가장 큰 값을 탐색 >> 12
- 18의 오른쪽 서브 트리에서 가장 작은 값을 탐색 >> 22
- 12 또는 22의 값 중에 하나의 값을 연결하면 됩니다.
또 다른 예시로 살펴보겠습니다.
>> 위의 그림에서 16의 값을 갖고 있는 노드를 삭제해보겠습니다.
1️⃣ 16의 노드를 삭제합니다.
2️⃣ 16의 부모 노드인 10과 연결될 노드를 찾습니다.
✔️ 이 때, 16의 왼쪽 서브 트리에 속한 노드들의 모든 값은 16보다 작고,
✔️ 오른쪽 서브 트리에 속한 노드들의 모든 값은 16보다 큽니다.
>> 16의 왼쪽 서브 트리에 연결된 노드 중 가장 큰 값은 13입니다. (-> predecessor)
>> 16의 오른쪽 서브 트리에 연결된 노드 중 가장 작은 값은 20입니다. (-> successor)
✅ 이 경우에, 삭제할 노드인 16의 위치에 20을 복사해놓고, 기존 20의 위치에 있던 노드를 삭제하면 정렬된 순서를 유지하면서도 원하는 결과를 얻을 수 있습니다.
✅ 이진 탐색 트리 구조 상, predecessor와 successor는 한 개이거나 또는 하나도 존재하지 않습니다.
func delete(from data: T) -> Bool {
guard let root = self.root, root.data != data else { return false }
var parentNode = root
var currentNode: Node? = root
// 삭제할 노드 탐색
while let node = currentNode {
if node.data == data {
break
}
if node.data > data {
currentNode = node.left
} else {
currentNode = node.right
}
parentNode = node
}
// 탐색 실패
guard let deleteNode = currentNode else {
return false
}
// 1. 단말 노드 삭제(Leaf Node)
if deleteNode.left == nil && deleteNode.right == nil {
if parentNode.data > data {
parentNode.left = nil
} else {
parentNode.right = nil
}
return true
}
// 2. 자식이 1개 있는 노드 삭제
if (deleteNode.left != nil) && (deleteNode.right == nil) {
if parentNode.data > data {
parentNode.left = deleteNode.left
} else {
parentNode.right = deleteNode.left
}
return true
}
if (deleteNode.left == nil) && (deleteNode.right != nil) {
if parentNode.data > data {
parentNode.left = deleteNode.right
} else {
parentNode.right = deleteNode.right
}
return true
}
// 3. 자식이 2개 있는 노드 삭제
guard let rightNode = deleteNode.right else { return false }
var changeNode = rightNode
var changeParentNode = rightNode
while let nextNode = changeNode.left {
changeParentNode = changeNode
changeNode = nextNode
}
if let rightNode = changeNode.right {
changeParentNode.left = rightNode
} else {
changeParentNode.left = nil
}
if parentNode.data > data {
parentNode.left = changeNode
} else {
parentNode.right = changeNode
}
// 삭제할 노드의 왼쪽/오른쪽 노드를 바꿀 노드와 연결
changeNode.left = deleteNode.left
changeNode.right = deleteNode.right
return true
}
각 연산의 시간 복잡성
탐색 알고리즘
루트 노드부터 해당 값이 있는 노드까지 이르는 브랜치/엣지의 수가 h일 때, 탐색 연산에 소요되는 시간 복잡성은 𝑂(ℎ)입니다. 최악의 경우, 단말 노드까지 탐색해야 하기 때문입니다.
(h번 비교 연산을 수행합니다.)
삽입 알고리즘
탐색 알고리즘에 더해서 삽입하는 계산이 추가되므로 시간이 더 필요하지만, 연결 리스트 삽입의 시간 복잡성은 𝑂(1)이므로 무시할 수 있습니다. 그러므로 탐색 알고리즘은 𝑂(ℎ)에 해당합니다.
삭제 알고리즘
빅-오 표기법으로 표시하기 위해서는 최악의 경우를 생각해야 하므로 삭제 알고리즘에 대해 가장 최악의 경우는 앞서 언급했던 삭제 알고리즘의 세 가지 경우 중 마지막 경우인, 삭제하고자 하는 노드의 자식 노드가 2개인 경우입니다.
이 경우에 successor 노드를 찾기 위해서 삭제 대상 노드의 서브 트리 높이에 해당하는 (h-d) 비교 연산을 수행해야 합니다. 그 이후로 각 노드를 복사하고 위치를 바꾸어 삭제하는 과정은 𝑂(1)이므로 무시할 수 있습니다.
>> 결과적으로, 𝑂(𝑑+ℎ−𝑑)O(d+h−d), 즉 𝑂(ℎ)의 시간 복잡도를 갖고 있습니다.
전체 코드는 아래 더보기를 통해서 확인할 수 있습니다.
class Node<T: Comparable> {
var data: T
var left: Node?
var right: Node?
init(data: T) {
self.data = data
}
}
class BinarySearchTree<T: Comparable> {
var root: Node<T>?
func insert(_ data: T) {
guard let root = self.root else {
return self.root = Node.init(data: data)
}
var currentNode = root
while true {
if currentNode.data > data {
guard let nextNode = currentNode.left else {
return currentNode.left = Node.init(data: data)
}
currentNode = nextNode
} else {
guard let nextNode = currentNode.right else {
return currentNode.right = Node.init(data: data)
}
currentNode = nextNode
}
}
}
func search(from data: T) -> Bool {
if root == nil { return false }
var currentNode = root
while let node = currentNode {
if node.data == data {
return true
}
if node.data > data {
currentNode = node.left
} else {
currentNode = node.right
}
}
return false
}
func delete(from data: T) -> Bool {
guard let root = self.root, root.data != data else { return false }
var parentNode = root
var currentNode: Node? = root
// 삭제할 노드 탐색
while let node = currentNode {
if node.data == data {
break
}
if node.data > data {
currentNode = node.left
} else {
currentNode = node.right
}
parentNode = node
}
guard let deleteNode = currentNode else { //탐색 실패
return false
}
// 1. 자식이 없는 노드 삭제(Leaf Node)
if deleteNode.left == nil && deleteNode.right == nil {
if parentNode.data > data {
parentNode.left = nil
} else {
parentNode.right = nil
}
return true
}
// 2. 자식이 1개 있는 노드 삭제
if (deleteNode.left != nil) && (deleteNode.right == nil) {
if parentNode.data > data {
parentNode.left = deleteNode.left
} else {
parentNode.right = deleteNode.left
}
return true
}
if (deleteNode.left == nil) && (deleteNode.right != nil) {
if parentNode.data > data {
parentNode.left = deleteNode.right
} else {
parentNode.right = deleteNode.right
}
return true
}
// 3. 자식이 2개 있는 노드 삭제
guard let rightNode = deleteNode.right else { return false }
var changeNode = rightNode
var changeParentNode = rightNode
while let nextNode = changeNode.left {
changeParentNode = changeNode
changeNode = nextNode
}
if let rightNode = changeNode.right {
changeParentNode.left = rightNode
} else {
changeParentNode.left = nil
}
if parentNode.data > data {
parentNode.left = changeNode
} else {
parentNode.right = changeNode
}
// Delete Node의 왼쪽, 오른쪽 자식을 changeNode에게 이식
changeNode.left = deleteNode.left
changeNode.right = deleteNode.right
return true
}
func drawDiagram() {
print(diagram(for: self.root))
}
private func diagram(for node: Node<T>?,
_ top: String = "",
_ root: String = "",
_ bottom: String = "") -> String {
guard let node = node else {
return root + "nil\n"
}
if node.left == nil && node.right == nil {
return root + "\(node.data)\n"
}
return diagram(for: node.right, top + " ", top + "┌──", top + "│ ")
+ root + "\(node.data)\n"
+ diagram(for: node.left, bottom + "│ ", bottom + "└──", bottom + " ")
}
}'Algorithm' 카테고리의 다른 글
| 프로그래머스 - 약수의 개수와 덧셈 (0) | 2022.04.14 |
|---|---|
| 프로그래머스 - 두 개 뽑아서 더하기 (0) | 2022.04.12 |
| BST (이진탐색트리) - 개념 (0) | 2022.04.01 |
| 알고리즘에 많이 사용되는 Swift Basic (0) | 2022.04.01 |
| 시간 복잡도 (+빅오 표기법) / 공간 복잡도 (0) | 2022.03.30 |