[Kotlin] Binary Search Tree Kotlin으로 구현해보기 : insert, search

Binary Search Tree 구현하기

이전 글에서 Binary Search Tree가 무엇인지에 대해 살펴보았다. 이번 글에서는 이를 직접 구현해보려고 한다.

 

구현할 Binary Search Tree의 요구사항은 다음과 같다.

• 중복을 허용하지 않는다. 이미 있는 값의 추가 요청이 들어오면 아무런 동작을 하지 않고 반환한다.

 

노드는 임의로 다음과 같이 구성한다.

data class Node(var value: Int) {
    var left: Node? = null
    var right: Node? = null
}

 

insert 메서드 구현하기

새로운 노드를 추가할 때는 다음과 같은 순서를 따른다.

1. 추가 요청이 들어온 노드를 생성한다.(새로운 노드)
2. 루트 노드가 null인지 확인 후 null이라면 새로운 노드를 root에 넣고 반환한다.
3. 루트 노드가 null이 아니라면, 현재 노드를 root 노드로 설정한 후 노드를 넣을 곳의 탐색을 시작한다.
   1. 현재 노드가 값과 같다면 반환한다.
   2. 현재 노드가 새로운 노드 값보다 작을 경우
      1. 현재 노드의 오른쪽 노드가 null 인 경우 오른쪽 노드에 새로운 노드를 삽입한다.
      2. 현재 노드의 오른쪽 노드가 null이 아닌 경우 현재 노드를 현재 노드의 오른쪽 노드로 변경한 후 탐색을 계속 수행한다.
   3. 현재 노드가 새로운 노드 값보다 클 경우
      1. 현재 노드의 왼쪽 노드가 null 인 경우 왼쪽 노드에 새로운 노드를 삽입한다.
      2. 현재 노드의 왼쪽 노드가 null이 아닌 경우 현재 노드를 현재 노드의 왼쪽 노드로 변경한 후 탐색을 계속 수행한다.

 

이에 대한 구현체는 아래와 같다.

class BinarySearchTree() {
    private var root: Node? = null

    fun insert(value: Int) {
        // 1. 노드 생성
        val newNode = Node(value)
        
        // 2. 루트 노드가 null인지 확인 후 null이라면 새로운 노드를 root에 넣고 반환
        if (root == null) {
            root = newNode
            return
        }

        // 3. 루트 노드가 null이 아니라면, 현재 노드를 root 노드로 설정 후 노드를 넣을 곳 탐색
        var currentNode = root!!

        while (true) {
            // 3.1 현재 노드가 값과 같다면 반환
            if (currentNode.value == value) break
            
            if (currentNode.value < value) {
                // 3.2 현재 노드가 새로운 노드 값보다 작다면
                if (currentNode.right == null) {
                    // 3.2.1 현재 노드의 오른쪽 노드가 null인 경우 현재 노드의 오른쪽 노드에 새로운 노드 삽입
                    currentNode.right = newNode
                    break
                } else {
                    // 3.2.2. 현재 노드의 오른쪽 노드가 존재하는 경우 오른쪽 노드로 이동
                    currentNode = currentNode.right!!
                }
            } else {
                // 3.3 현재 노드가 새로운 노드 값보다 크다면
                if (currentNode.left == null) {
                    // 3.3.1 현재 노드의 왼쪽 노드가 null인 경우 현재 노드의 왼쪽 노드에 새로운 노드 삽입
                    currentNode.left = newNode
                    break
                } else {
                    // 3.3.2 현재 노드의 왼쪽 노드가 존재하는 경우 왼쪽 노드로 이동
                    currentNode = currentNode.left!!
                }
            }
        }
    }
}

 

 

search 메서드 구현하기

특정 값을 찾을 때는 다음의 과정을 따른다.

 

1. 루트 노드가 null일 경우 null을 반환한다.
2. 현재 노드가 루트 노드를 가르키도록 만든 후 탐색(while)을 시작한다.
   1. 현재 노드가 null인 경우 탐색을 중단하고 null을 반환한다.
   2. 현재 노드의 값이 탐색값과 같을 경우 현재 노드를 반환한다. 
   3. 현재 노드의 값이 탐색값보다 작을 경우 현재 노드를 현재 노드의 오른쪽 노드로 변경한다.
   4. 현재 노드의 값이 탐색값보다 클 경우 현재 노드를 현재 노드의 왼쪽 노드로 변경한다.

 

이에 대한 구현체는 다음과 같다.

class BinarySearchTree() {
    private var root: Node? = null

    fun search(value: Int): Node? {
        // 1. 루트 노드가 null일 경우 null을 반환한다.
        if (root == null) return null
        
        // 2. 현재 노드가 루트 노드를 가르키도록 만든 후 탐색(while)을 시작한다.
        var currentNode = root

        // 2.1 현재 노드가 null인 경우 탐색을 중단하고 null을 반환한다.
        while (currentNode != null) {
            // 2.2. 현재 노드의 값이 탐색값과 같을 경우 현재 노드를 반환한다. 
            if (currentNode.value == value) return currentNode

            if (currentNode.value < value) {
            	// 2.3. 현재 노드의 값이 탐색값보다 작을 경우 현재 노드의 오른쪽 노드로 이동한다.
                currentNode = currentNode.right
            } else {
	            // 2.3. 현재 노드의 값이 탐색값보다 큰 경우 현재 노드의 왼쪽 노드로 이동한다.
                currentNode = currentNode.left
            }
        }

        return null
    }
}

 

정리

이번 글에서는 Binary Search Tree의 insert와 search 메서드를 구현해보았다. delete 메서드는 구현 가능하지만, 너무 경우의 수가 많으므로 다음에 기회가 되면 구현해보도록 하겠다.