이진탐색트리 BST(Binary Search Tree) Feat. kotlin
참조한 자료
유튜브 - https://www.youtube.com/watch?v=i57ZGhOVPcI
정의
*이진 트리(binary tree)- 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
이진 탐색 트리(BST: binary search tree)
이진 트리중 아래와 같은 특징을 지니는 트리
- 모든 노드는 값(value)을 가진다.
- 값은 대소관계가 존재한다. 즉 비교 가능하다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
- 좌우. 서브 트리는 각각이 다시 이진 탐색 트리 이다.
search / insert / delete
*search 는 Insert 및 delete를 위해 필수적으로 발생하기 때문에 생략한다.
Insert (삽입)
- 트리를 검색한 후 키와 일치하는 노드가 없으면, 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.
delete (삭제)
-트리를 검색한 후 키와 일치하는 노드가 있다면 삭제한다. 삭제시 자식노드의 숫자에 따라 다르게 작동한다.
- 자식노드가 0개 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
예시) delete(20)
- 자식노드가 1개 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다
예시) delete(30)
- 자식노드가 2개 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
예시) delete(50)
구현
fun main() {
val bst = BinarySearchTree()
bst.add(10)
bst.add(50)
bst.add(20)
bst.add(7)
bst.add(1000)
bst.print()
println(bst.getSize())
bst.delete(10)
bst.print()
println(bst.getSize())
}
data class Node(
var key: Int,
var left: Node? = null,
var right: Node? = null
)
class BinarySearchTree(private var root: Node? = null) {
private var size: Int = if (root == null) 0 else 1
fun getSize() = size
/*
search
재귀함수를 통해 구현 가능하다.
*/
fun search(node: Node? = root, value: Int): Node? =
if (node == null || node.key == value)
node
else if (node.key > value) {
search(node = node.left, value = value)
} else {
search(node = node.right, value = value)
}
private fun addNode(parent: Node?, value: Int) {
if (parent == null || parent.key == value) {
// 이미 존재하는 key 라면 추가 하지 않는다.
return
} else if (parent.key > value) {
if (parent.left == null) {
parent.left = Node(key = value)
size += 1
} else
addNode(parent.left, value)
} else {
if (parent.right == null) {
parent.right = Node(key = value)
size += 1
} else
addNode(parent.right, value)
}
}
fun add(value: Int) {
if (root == null) {
root = Node(key = value)
size += 1
} else {
addNode(root, value)
}
}
fun delete(value: Int): Boolean {
// 1. 삭제할 노드와 그 노드의 부모 노드의 참조를 얻는다.
var node = root
var parentNode: Node? = null
// 삭제할 노드가 부모의 왼쪽, 오른쪽 자식인지 확인.
var isFromLeft = false
while (true) {
// root node가 null 이거나 모든 리프노드 까지 탐색을 했는데 키값을 못 찾은 경우
if (node == null) {
return false
}
if (node.key == value)
break
else if (node.key > value) {
parentNode = node
node = node.left
isFromLeft = true
} else {
parentNode = node
node = node.right
isFromLeft = false
}
}
// 2-1 삭제할 노드가 leaf 노드
if (node?.left == null && node?.right == null) {
// root 만 남아 있는 상황.
if (parentNode == null) {
root = null
size = 0
return true
}
// 삭제할 노드가 부모의 left, right 노드 인지 확인 후 삭제.
if (isFromLeft) {
parentNode.left = null
} else {
parentNode.right = null
}
}
// 2-2 삭제할 노드가 자식을 1개인 경우
// 삭제할 노드가 왼쪽 자식을 가진 경우
else if (node.right == null) {
if (parentNode == null)
root = node.left
else if (isFromLeft) {
parentNode.left = node.left
} else {
parentNode.right = node.left
}
}
// 삭제할 노드가 오른쪽 자식을 가진 경우
else if (node.left == null) {
if (parentNode == null)
root = node.right
else if (isFromLeft) {
parentNode.left = node.right
} else {
parentNode.right = node.right
}
}
// 2-3 삭제할 노드가 자식을 2개인 경우
// 삭제할 노드의 predecessor(자신의 보다 작으면서 가장 큰것)
parentNode = node
var left = parentNode?.left
isFromLeft = true
// successor를 찾음.
while (left?.right != null) {
parentNode = left
left = left.right
isFromLeft = false
}
node?.key = left?.key!!
// predecessor 니까 오른쪽 자식은 없다.
if (isFromLeft){
parentNode?.left = left.left
}else
parentNode?.right = left.left
size -= 1
return true
}
fun print() {
printSubTree(root)
}
/*
inOrder 순회로 이진탐색 트리의 오름 차순 순으로 출력 한다.
*/
private fun printSubTree(node: Node?) {
if (node != null) {
printSubTree(node.left)
println("node key = ${node.key}")
printSubTree(node.right)
}
}
}시간복잡도
root 노드에서 원하는 값을 찾는 다면 best case로 상수시간.
평균적으로는 대소 비교에 따라 탐색할 노드를 절반으로 줄이기 때문에 logN
worst case는 이진 탐색트리가 매우 한쪽으로 편향되어 있는 경우,
