이진탐색트리 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는 이진 탐색트리가 매우 한쪽으로 편향되어 있는 경우,