[java] 자바의 이진 탐색 트리(Binary Search Tree) 자료구조에 대해 알아보기

14 Dec 2023

java

이진 탐색 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 갖는 이진 트리를 의미합니다.

이진 탐색 트리의 장점

이진 탐색 트리는 데이터를 효율적으로 삽입, 삭제, 탐색할 수 있는 장점이 있습니다. 또한, 탐색 작업의 시간 복잡도가 O(log n)으로 매우 빠르다는 특징이 있습니다.

이진 탐색 트리의 구현

이진 탐색 트리는 다음과 같이 자바로 구현할 수 있습니다.

class Node {
    int data;
    Node left, right;

    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    BinarySearchTree() {
        root = null;
    }

    void insert(int value) {
        root = insertRec(root, value);
    }

    Node insertRec(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }

        if (value < root.data) {
            root.left = insertRec(root.left, value);
        } else if (value > root.data) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    void inOrder() {
        inOrderRec(root);
    }

    void inOrderRec(Node root) {
        if (root != null) {
            inOrderRec(root.left);
            System.out.println(root.data);
            inOrderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        tree.inOrder();
    }
}

결론

이진 탐색 트리는 데이터를 효율적으로 탐색할 수 있는 자료구조로, 여러 알고리즘 및 데이터 구조에서 활용되고 있습니다.