이진 탐색 트리(Binary Search Tree, BST)
#DataStructure #DataStructure-Tree #DataStructure-Binary_Tree #DataStructure-BST
이진 탐색 트리(Binary Search Tree, BST) 일부 복붙
1. 이진 탐색 트리 (Binary Search Tree, BST)
===> 왼쪽 자손노드의 값은 부모 노드의 값보다 작고, 오른쪽 자손 노드의 값은 부모 노드의 값보다 큰 값을 가지도록 만들어진 이진 트리 (각 노드의 값은 트리 내에서 유일해야 한다.) ==
위와 같이 데이터를 저장하기 때문에 탐색에 매우 유리하다.
또한 위의 규칙으로 트리를 구성하기 때문에 가지는 몇가지 특성이 있다.
- 맨 왼쪽 노드는 (마지막 레벨이 아니여도, preorder traversal을 했을 때 가장 먼저 선택되는 노드) 트리 전체에서 가장 작은 값을 가진다.
- 맨 오른쪽 노드는 트리 전체에서 가장 큰 값을 가진다.
- BST를 중위 순회(Inorder Traversal)하면 오름차순으로 정렬할 수 있다.
2. 구현
- 노드 클래스
data class Node(
var height: Int = 0,
var left: Node? = null,
var right: Node? = null,
val key: Int
)
2-1. 이진 탐색 트리에 데이터 추가하기
class BST() {
var root: Node? = null
private set
@Throws
fun insertKey(key: Int) {
var currentNode = root
while(true) {
when {
currentNode == null -> {
currentNode = Node(key = key)
root = currentNode
return
}
currentNode.key > key -> {
if (currentNode.left != null) {
currentNode = currentNode.left!!
} else {
currentNode.left = Node(height = currentNode.height+1, key = key)
return
}
}
currentNode.key < key -> {
if (currentNode.right != null) {
currentNode = currentNode.right!!
} else {
currentNode.right = Node(height = currentNode.height+1, key = key)
return
}
}
else -> { // BST 긱 노드의 값은 유일해야 한다.
throw IllegalArgumentException()
}
}
}
fixHeight(root)
}
fun fixHeight(node: Node?): Int {
if (node == null) return -1
node.height = Math.max(fixHeight(node.left), fixHeight(node.right)) + 1
return node.height
}
//...
}
2-2. 이진 탐색 트리에 데이터 삭제하기
BST에 있는 데이터를 삭제하는 것은 루트 노드라던가, 리프노드 뿐만이 아니라 원하는 그 사이에 있는 원하는 노드를 삭제할 수 있다. 때문에 삭제 대상이 되는 노드가 연결된 형태에 따라 몇가지 경우가 생긴다. 이진 탐색 트리(Binary Search Tree) 구현-삭제, Keunjae Song 을 참고하자.
- 삭제하려는 노드가 리프 노드인 경우
- 삭제하려는 노드가 왼쪽 자식 서브트리만 가지고 있는 경우
- 삭제하려는 노드가 오른쪽 자식 서브트리만 가지고 있는 경우
- 삭제하려는 노드가 왼쪽과 오른쪽 자식 서브트리를 모두 가지고 있는 경우
1.의 경우는 삭제하려는 노드를 날려주면 된다.
2.의 경우는 왼쪽 자식 서브트리의 노드들 중에서 가장 큰 값을 삭제될 노드의 자리에 연결시켜주면 된다.
3.의 경우는 오른쪽 자식 서브트리의 노드들 중에서 가장 작은 값을 삭제될 노드의 자리에 연결시켜주면 된다.
4.의 경우는 2.의 경우 혹은 3.의 경우 하나를 선택해 실행해주면 된다.
class BST() {
var root: Node? = null
private set
// ...
fun deleteKey(key: Int) {
val targetNode: Node = findNode(key) ?: return
val targetParentNode: Node = findParentNode(key) ?: return
when {
// 왼쪽 자식 서브트리가 있으면 왼쪽 자식 서브트리의 가장 큰 노드를 찾아서 대체
targetNode.left != null -> {
val maxNode = findMaxKeyNode(targetNode.left!!)
val maxNodeParentNode = findParentNode(maxNode.key)!!
disconnectFromParent(maxNode, maxNodeParentNode)
targetParentNode.left = maxNode
}
// 오른쪽 자식 서브트리가 있으면 오른쪽 자식 서브트리의 가장 작은 노드를 찾아서 대체
targetNode.right != null -> {
val minNode = findMinKeyNode(targetNode.right!!)
val minNodeParentNode = findParentNode(minNode.key)!!
disconnectFromParent(minNode, minNodeParentNode)
targetParentNode.right = minNode
}
// 리프 노드이면 부모 노드에서 연결 끊음
else -> {
disconnectFromParent(targetNode, targetParentNode)
}
}
fixHeight(root)
}
fun disconnectFromParent(targetNode: Node, targetParentNode: Node) {
when(targetNode.key) {
targetParentNode.left?.key -> {
targetParentNode.left = null
}
else -> {
targetParentNode.right = null
}
}
}
fun findMaxKeyNode(node: Node): Node {
return node.right?.let {
findMaxKeyNode(it)
} ?: run {
node
}
}
fun findMinKeyNode(node: Node): Node {
return node.left?.let {
findMinKeyNode(it)
} ?: run {
node
}
}
fun findParentNode(key: Int): Node? {
var currentNode = root
while(true) {
if (currentNode == null) return null
if (currentNode.key > key) {
when (currentNode.left?.key) {
null -> return null
key -> return currentNode
else -> currentNode = currentNode.left
}
} else if (currentNode.key < key) {
when (currentNode.right?.key) {
null -> return null
key -> return currentNode
else -> currentNode = currentNode.right
}
} else {
return null
}
}
}
fun findNode(key: Int): Node? {
var currentNode = root
while(true) {
when {
currentNode == null -> {
return null
}
currentNode.key == key -> {
return currentNode
}
currentNode.key > key -> {
currentNode = currentNode.left
}
else -> {
currentNode = currentNode.right
}
}
}
}
// ...
}
테스트
class BST() {
var root: Node? = null
private set
// ...
fun inOrderTraversal(node: Node?) {
if (node == null) return
inOrderTraversal(node.left)
print("${node.key}, ")
inOrderTraversal(node.right)
}
fun bfs(node: Node?) {
if (node == null) return
val queue: Queue<Pair<Node, Int>> = LinkedList()
queue.offer(node to 0)
var currentLevel = node.height
while(queue.isNotEmpty()) {
val pair = queue.poll()
if (pair.second != currentLevel) {
currentLevel = pair.second
println("")
}
print("${pair.first.key}(${pair.first.height}) ")
pair.first.left?.let {
queue.offer(it to currentLevel+1)
}
pair.first.right?.let {
queue.offer(it to currentLevel+1)
}
}
}
}
fun main(args: Array<String>) {
val bst = BST()
bst.insertKey(3)
bst.insertKey(2)
bst.insertKey(1)
bst.insertKey(7)
bst.insertKey(6)
bst.insertKey(5)
bst.insertKey(4)
bst.insertKey(10)
bst.insertKey(9)
bst.insertKey(11)
// bst.inOrderTraversal(bst.root)
bst.bfs(bst.root)
println("\n-----------------")
bst.insertKey(12)
bst.insertKey(13)
bst.bfs(bst.root)
println("\n-----------------")
bst.deleteKey(5)
bst.bfs(bst.root)
// bst.inOrderTraversal(bst.root)
}
/*
3(4)
2(1) 7(3)
1(0) 6(2) 10(1)
5(1) 9(0) 11(0)
4(0)
-----------------
3(5)
2(1) 7(4)
1(0) 6(2) 10(3)
5(1) 9(0) 11(2)
4(0) 12(1)
13(0)
-----------------
3(5)
2(1) 7(4)
1(0) 6(1) 10(3)
4(0) 9(0) 11(2)
12(1)
13(0) */