[자료구조] 이진탐색트리(Binary Search Tree)란?

이진탐색트리란?

---

이진탐색트리는 다음의 조건을 만족하는 이진트리이다.

1. 모든 노드는 각각 유일한 키(key)를 가진다.
2. 루트 노드의 왼쪽 서브 트리는 루트 노드 보다 작은 키 값으로 이루어져 있다.
3. 루트 노드의 오른쪽 서브 트리는 루트 노드 보다 큰 키 값으로 이루어져 있다.
4. 좌우 서브 트리 모두 이진탐색트리이다.

이진트리에 정보가 필요하다면 참고하길 바란다.
2023.11.29 - [자료구조/비선형 자료구조(Non-Linear)] - [자료구조] 이진트리(Binary-Tree)란?

[자료구조] 이진트리(Binary-Tree)란?

 

이진탐색트리의 특징

---

• 모든 노드가 최대 2개의 자식 노드를 갖는 이진트리 구조이다.
• 왼쪽 서브 트리는 루트보다 작은 키 값, 오른쪽 서브 트리는 루트보다 큰 키 값으로 이루어진다.
• 루트에서부터 특정 값을 탐색할 때 효율적인 탐색이 가능하다.
• 이진탐색트리의 연산은 삽입, 삭제, 탐색으로 이루어진다.

이진탐색트리의 연산

---

삽입

삽입 연산은 루트 확인 후, 값이 루트의 키 값보다 큰지 작은지에 따라 나뉘게 된다.

1. 루트의 키 값과 비교하여 루트와 값이 같다면 오류를 발생한다.(이는 중복값을 허용하지 않기 때문)
2. 루트의 키 값보다 작을 경우, 왼쪽 서브 트리로 이동한다.
3. 루트의 키 값보다 클 경우, 오른쪽 서브 트리로 이동한다.
4. 1번부터 반복하며 노드가 비어있다면 삽입을 한다.

삭제

삭제 연산은 크게 3가지로 나뉘게 된다.

1. 잎 노드를 삭제할 때
2. 서브 트리가 1개인 노드를 삭제할 때
3. 서브 트리가 2개인 노드를 삭제할 때

잎 노드를 삭제할 때

이 경우, 잎 노드를 찾아 해당 메모리를 null로 바꾸어 연결을 끊어주면 된다.

서브 트리가 1개인 노드를 삭제할 때

이 경우, 자신의 서브 트리를 자신의 부모 노드와 연결시켜주고 자기 자신을 null로 바꿔준다.

서브 트리가 2개인 노드를 삭제할 때

이 경우가 조금 복잡하다.
서브 트리가 2개인 노드를 삭제하고 난 뒤에도 이진트리를 만족해야 하기 때문이다.
루트 노드 또한 서브 트리가 2개인 노드를 삭제하는 경우로 예를 든다면 다음과 같다.

1. 루트 노드의 왼쪽 서브 트리의 가장 오른쪽 값 or 오른쪽 서브 트리의 가장 왼쪽 값을 루트로 가져온다.
2. 가져온 값외 왼쪽 서브 트리와 오른쪽 서브 트리와 연결 시킨다.
3. 루트 노드를 Null로 바꾸어 메모리를 해제한다.

여기서 왼쪽 서브 트리의 가장 오른쪽 값은 왼쪽 서브 트리의 가장 큰 값을, 오른쪽 서브 트리의 가장 왼쪽 값은 오른쪽 서브 트리의 가장 작은 값을 의미한다.
이렇 진행을 하면 이진 트리의 조건을 만족하면서 형태를 유지할 수 있게 된다.

탐색

이진탐색트리에서 특정 데이터를 검색할 때는 루트에서 시작하게 된다.

1. 루트의 데이터와 비교한다.
2. 찾고자 하는 데이터가 루트보다 작으면 왼쪽 서브 트리로, 찾고자 하는 데이터가 루트보다 크면 오른쪽 서브트리로 이동한다.
3. 특정 데이터를 찾을 때 까지 반복한다.

728x90

이진탐색트리의 시간복잡도

---

이진탐색트리는 기본적으로 데이터를 찾는다는 것이 공통된 연산이다.
이진탐색트리의 시간복잡도를 구하는 수식은 다음과 같다.

트리의 데이터를 N개라고 가정한다면,

1. 루트 노드를 확인했을 때, 찾고자 하는 값이라면 시간 복잡도는 O(1)이 된다.
2. 만일 루트 노드의 데이터가 찾고자 하는 값이 아니라면 남은 노드의 수는 $\frac{N}{2}$ 가 된다.
3. 두 번째 노드에서도 찾고자 하는 값이 아니라면 이 역시 남은 노드의 수는 $\frac{N}{2} × \frac{1}{2}$가 된다.
4. 세 번째 노드에서도 찾고자 하는 값이 아니라면 이 역시 남은 노드의 수는 $\frac{N}{2} × \frac{1}{2} × \frac{1}{2}$가 된다.

이렇게, 2, 3, 4번을 통해 규칙을 찾으면 이진탐색트리에서 데이터를 찾을 때 걸리는 시간은 $(\frac{1}{2})^k × N$ 이라는 규칙을 찾을 수 있다.
최악의 경우, $(\frac{1}{2})^k × N$ = 1이 될 때까지 검색을 하게 된다.(이유는 데이터가 1개 남을 때까지 검색을 하기 때문)
이를 O(n) 표기로 변경하면 다음과 같이 나올 수 있다.

$(\frac{1}{2})^k × N = 1$에서 양 변에 $2^k$ 를 곱하면

$2^k = N$

$k = log_2N$

k는 탐색 횟수이므로, 노드 N개를 탐색하는데 걸리는 시간을 O(n)표기로 변경하면 O($log_2N$) 또는 O($logN$) 이라고 표기한다.(시간복잡도 표기는 상수를 무시하기도 한다.)

이진탐색트리의 장단점

---

1. 장점
   • 시간복잡도가 평균적으로 O($logN$)만큼 걸려 데이터 탐색하는데 효율적이다.
   • 중위 순회를 통하여 정렬된 데이터를 얻을 수 있다.
2. 단점
   • 편향트리의 경우, 시간복잡도가 O(N)까지 나올 수 있다.
   • 데이터 삽입, 삭제에 따라 트리의 균형이 깨질 수도 있다.

예제

---

데이터를 확인하기 위해 중위 순회를 통해서 프린트를 출력하였다.
전위순회, 후위 순회를 하고 싶은 경우에는 printSearch 함수 내부에 있는 순서만 바꿔주면 된다.

package TreeExample

class Node(data: Int, left: Node?, right: Node?) {
    var data: Int
    var left: Node?
    var right: Node?

    init {
        this.data = data
        this.left = left
        this.right = right
    }
}

class BinarySearchTree {
    private var head: Node? = null

    fun add(data: Int) {
        if(head?.data == data)
            return

        when {
            (null == head) -> head = Node(data, null, null)
            (head!!.data > data) -> addSearchLeft(head, data)
            (head!!.data < data) -> addSearchRight(head, data)
        }
    }

    fun search(data: Int): Boolean = when {
        (null == head) -> false
        (head!!.data > data) -> searchLeft(head!!.left, data)
        (head!!.data < data) -> searchRight(head!!.right, data)
        else -> true
    }

    fun remove(data: Int) {
        if(null == head)
            return

        when {
            (head!!.data > data) -> removeSearchLeft(head, data)
            (head!!.data < data) -> removeSearchRight(head, data)
            (head!!.data == data) -> {
                when {
                    (null == head?.left && null == head?.right) -> head = null
                    (null == head?.left || null == head?.right) -> {
                        head = if(null == head?.left)
                            head?.right
                        else
                            head?.left
                    }
                    else -> {
                        if(height(head!!.left) > height(head!!.right)) {
                            head?.left?.right = head?.right
                            head = head?.left
                        }
                        else {
                            head?.right?.left = head?.left
                            head = head?.right
                        }
                    }
                }
            }
        }
    }

    fun printBinarySearchTree() {
        if(null == head) {
            println("트리가 비어있음")
            return
        }

        print("print start - ")
        printSearch(head!!)
        println("print end")
    }

    private fun addSearchLeft(node: Node?, data: Int) {
        when {
            (null == node?.left) -> node?.left = Node(data, null, null)
            (node.left!!.data > data) -> addSearchLeft(node.left, data)
            (node.left!!.data < data) -> addSearchRight(node.left, data)
        }
    }

    private fun addSearchRight(node: Node?, data: Int) {
        when {
            (null == node?.right) -> node?.right = Node(data, null, null)
            (node.right!!.data > data) -> addSearchLeft(node.right, data)
            (node.right!!.data < data) -> addSearchRight(node.right, data)
        }
    }

    private fun searchLeft(node: Node?, data: Int): Boolean = when {
        (null == node?.left) -> false
        (node.left!!.data > data) -> searchLeft(node.left, data)
        (node.left!!.data < data) -> searchRight(node.left, data)
        else -> true
    }

    private fun searchRight(node: Node?, data: Int): Boolean = when {
        (null == node?.right) -> false
        (node.right!!.data > data) -> searchLeft(node.right, data)
        (node.right!!.data < data) -> searchRight(node.right, data)
        else -> true
    }

    private fun removeSearchLeft(node: Node?, data: Int) {
        if(null == node?.left)
            return

        when {
            (node.left!!.data > data) -> removeSearchLeft(node.left, data)
            (node.left!!.data < data) -> removeSearchRight(node.left, data)
            (node.left!!.data == data) -> {
                when {
                    (null == node.left?.left && null == node.left?.right) -> removeLeafNode(node, data)
                    (null == node.left?.left || null == node.left?.right) -> removeOneSubTree(node, data)
                    else -> removeTwoSubTree(node, data)
                }
            }
        }
    }

    private fun removeSearchRight(node: Node?, data: Int) {
        if(null == node?.right)
            return

        when {
            (node.right!!.data > data) -> removeSearchLeft(node.right, data)
            (node.right!!.data < data) -> removeSearchRight(node.right, data)
            (node.right!!.data == data) -> {
                when {
                    (null == node.right?.left && null == node.right?.right) -> removeLeafNode(node, data)
                    (null == node.right?.left || null == node.right?.right) -> removeOneSubTree(node, data)
                    else -> removeTwoSubTree(node, data)
                }
            }
        }
    }

    private fun removeLeafNode(node: Node, data: Int) {
        when {
            (node.left?.data == data) -> node.left = null
            (node.right?.data == data) -> node.right = null
        }
    }

    private fun removeOneSubTree(node: Node, data: Int) {
        if(node.left?.data == data) {
            if(null == node.left?.left)
                node.left = node.left?.right
            else
                node.left = node.left?.left
        } else
            if(null == node.right?.left)
                node.right = node.right?.right
            else
                node.right = node.right?.left
    }

    private fun removeTwoSubTree(node: Node, data: Int) {
        if(height(node.left!!.left) > height(node.left!!.right))
            addLeftSubTreeToRoot(node, data)
        else
            addRightSubTreeToRoot(node, data)
    }

    private fun addLeftSubTreeToRoot(node: Node, data: Int) {
        var delete = if(node.left!!.data == data)
            node.left!!
        else
            node.right!!

        var sub = delete
        while(null != sub.right?.right) {
                sub = sub.right!!
        }

        var temp = sub.right!!
        sub.right = temp.right

        temp.left = delete.left
        temp.right = delete.right

        if(node.left?.data == data)
            node.left = temp
        else
            node.right = temp
    }

    private fun addRightSubTreeToRoot(node: Node, data: Int) {
        var delete = if(node.left!!.data == data)
            node.left!!
        else
            node.right!!

        var sub = delete
        while(null != sub.left?.left) {
            sub = sub.left!!
        }

        var temp = sub.left!!
        sub.left = temp.left

        temp.left = delete.left
        temp.right = delete.right

        if(node.left?.data == data)
            node.left = temp
        else
            node.right = temp
    }

    private fun height(node: Node?): Int {
        return if (null == node) {
            0
        } else {
            val leftHeight = height(node.left)
            val rightHeight = height(node.right)
            if (leftHeight > rightHeight) leftHeight + 1 else rightHeight + 1
        }
    }

    private fun printSearch(node: Node) {
        printSearchLeft(node)
        printSearchNode(node)
        printSearchRight(node)
    }

    private fun printSearchLeft(node: Node) {
        if(null == node.left)
            return

        printSearch(node.left!!)
    }

    private fun printSearchNode(node: Node) {
        print("${node.data} - ")
    }

    private fun printSearchRight(node: Node) {
        if(null == node.right)
            return

        printSearch(node.right!!)
    }
}

fun main() {
    var tree = BinarySearchTree()
    tree.printBinarySearchTree()

    tree.add(5)
    tree.add(9)
    tree.add(3)
    tree.add(7)
    tree.add(1)
    tree.add(2)
    tree.add(4)

    tree.printBinarySearchTree()

    tree.remove(3)
    tree.remove(7)

    tree.printBinarySearchTree()

    tree.remove(5)
    tree.printBinarySearchTree()

    println(tree.search(4))
    println(tree.search(3))
}

결과

출처 : [자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현, 이진 탐색 트리 (Binary Search Tree), [Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도