[자료구조] 배열로 이진탐색트리 만들기 :: 늦깎이 IT

이번 시간에는 배열을 이진트리로 변환하는 방법에 대해서 설명한다.

정렬이 되어있고, 정수로만 이루어진 배열이 있을 때 이 배열로 이진검색트리로 변환해보자.

아래와 같이 숫자 0부터 9까지 정렬된 배열이 있다고 가정하자. 이 배열을 이진탐색트리로 변환할 때 알아야 할 것은 이진탐색트리의 전제조건이다.

[ 이진탐색트리의 조건 ]

• 모든 키는 유일하다.

• 왼쪽 서브트리의 키 값은 부모노드의 키 값보다 작다.

• 오른쪽 서브트리의 키 값은 부모노드의 키 값보다 크다.

• 루트노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다.

이진탐색트리의 연산에는 크게 삽입, 삭제, 탐색이 있는데 각각의 연산은 이진트리의 높이에 따라 시간 복잡도 효율성을 갖게된다.

즉, 트리의 높이가 낮을 수록(logN에 가까울 수록) 좋은 연산속도를 갖게되므로, 주어진 배열을 이진탐색트리로 변환할 때에도 이와 같은 점을 유의한다.

[ 이진탐색트리로 변환하기 ]

1. 배열에서 중간 값을 찾고, 그 값을 기준으로 왼쪽, 오른쪽 데이터로 나눈다.

2. 이때 중간 값을 기준으로 왼쪽에 있는 데이터는 왼쪽 서브트리, 오른쪽에 있는 데이터는 오른쪽 서브트리가 된다.

3. 이때 중간 값을 기준으로 왼쪽, 오른쪽으로 나뉜 데이터들을 가지고 다시 재귀함수를 호출하며 이진트리를 완성한다.

위와 같은 과정을 슬라이드로 표현해보았다. 과정을 천천히 살펴보면 이해하기 쉬울 것이다.

0123456789

[ JAVA 코드 ]

 
public class ArrayToBST {
 
    public static void main(String[] args) {
 
        int[] arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        BST bst = new BST();
        bst.makeTree(arr);
        bst.traverseInOrder(bst.root);
    }
}
 
class BST {
 
    Node root;
 
    static class Node {
        int data;
        Node left;
        Node right;
 
        public Node(int data) {
            this.data = data;
            this.left = this.right = null;
        }
 
    }
 
    public void makeTree(int[] arr) {
        root = makeTree(arr, 0, arr.length - 1);
    }
 
    public Node makeTree(int[] arr, int start, int end) {
 
        if (start > end)
            return null;
 
        int mid = (start + end) / 2;
        Node node = new Node(arr[mid]);
        node.left = makeTree(arr, start, mid - 1);
        node.right = makeTree(arr, mid + 1, end);
        return node;
    }
 
    public void traverseInOrder(Node root) {
 
        if (root == null)
            return;
 
        traverseInOrder(root.left);
        System.out.print(root.data + " ");
        traverseInOrder(root.right);
    }
 
}