이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리(BST)는 이진 트리의 한 종류로, 특정 규칙에 따라 데이터를 저장하여 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있습니다.

---

특징

1. 구조:
   • 각 노드는 최대 2개의 자식 노드를 가질 수 있습니다.
   • 노드에는 키(key)와 데이터가 저장됩니다.
2. 속성 (Binary Search Property):
   • 왼쪽 서브트리의 모든 노드 값은 현재 노드 값보다 작습니다.
   • 오른쪽 서브트리의 모든 노드 값은 현재 노드 값보다 큽니다.
   • 이 규칙은 모든 서브트리에서도 동일하게 적용됩니다.
3. 중위 순회(Inorder Traversal):
   • BST를 중위 순회하면 항상 오름차순으로 정렬된 값을 얻을 수 있습니다.
4. 효율성:
   • 일반적으로 연산의 시간 복잡도는 O(h) (h는 트리의 높이)입니다.
   • 트리가 균형을 유지하면 높이는 log₂(n)에 비례하므로, 연산이 매우 효율적입니다.
   • 트리가 한쪽으로 치우치면 최악의 경우 높이가 n이 되어 비효율적입니다.

---

기본 연산

1. 탐색(Search)

• 루트에서 시작하여 값을 비교합니다:
  • 탐색 값이 현재 노드 값보다 작으면 왼쪽 자식으로 이동.
  • 크면 오른쪽 자식으로 이동.
• 값이 일치하면 탐색 성공.
• 트리의 높이를 hhh라 할 때, 시간 복잡도는 O(h).

2. 삽입(Insertion)

• 새 노드는 항상 리프(leaf)로 추가됩니다.
• 삽입 규칙:
  • 삽입 값이 현재 노드 값보다 작으면 왼쪽 자식으로 이동.
  • 크면 오른쪽 자식으로 이동.
• 도착한 위치에 새 노드를 추가.

3. 삭제(Deletion)

• 삭제 대상 노드가:
  • 리프 노드: 바로 삭제.
  • 한 자식만 있는 노드: 자식을 부모 노드에 연결.
  • 두 자식이 있는 노드:
    1. 중위 후속자(Inorder Successor): 오른쪽 서브트리의 최소 값을 가져옴.
    2. 중위 선행자(Inorder Predecessor): 왼쪽 서브트리의 최대 값을 가져옴.
    3. 위 값을 삭제할 노드로 교체한 후, 해당 노드를 삭제.

---

장점과 단점

장점:

1. 효율적인 탐색:
   • 정렬된 데이터를 트리 형태로 저장하여 O(log n)의 시간에 탐색 가능 (평균적으로 균형이 잘 유지된 경우).
2. 동적 데이터 관리:
   • 데이터 삽입과 삭제가 빈번한 경우에도 유용.

단점:

1. 트리 불균형:
   • 삽입과 삭제가 편향되면 트리가 한쪽으로 치우쳐 성능이 O(n)으로 저하될 수 있음.
2. 균형 유지 필요:
   • 레드-블랙 트리, AVL 트리 등 균형 트리를 사용하는 것이 필요할 수 있음.

---

BST 구현 예제 (Java)

Node 클래스

class Node {
    int data;
    Node left, right;

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

BST 클래스

class Bst {
    private Node root;

    // 삽입 연산
    public void insertData(int data) {
        root = insertRecursive(root, data);
    }

    private Node insertRecursive(Node node, int data) {
        if (node == null) {
            return new Node(data);
        }
        if (data < node.data) {
            node.left = insertRecursive(node.left, data);
        } else if (data > node.data) {
            node.right = insertRecursive(node.right, data);
        }
        return node;
    }

    // 탐색 연산
    public boolean searchData(int data) {
        return searchRecursive(root, data);
    }

    private boolean searchRecursive(Node node, int data) {
        if (node == null) {
            return false;
        }
        if (data == node.data) {
            return true;
        } else if (data < node.data) {
            return searchRecursive(node.left, data);
        } else {
            return searchRecursive(node.right, data);
        }
    }

    // 삭제 연산
    public void deleteData(int data) {
        root = deleteRecursive(root, data);
    }

    private Node deleteRecursive(Node node, int data) {
        if (node == null) {
            return null;
        }

        if (data < node.data) {
            node.left = deleteRecursive(node.left, data);
        } else if (data > node.data) {
            node.right = deleteRecursive(node.right, data);
        } else {
            // 노드 찾음
            // 리프 노드
            if (node.left == null && node.right == null) {
                return null;
            }
            // 하나의 자식만 있는 경우
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }
            // 두 자식이 있는 경우
            Node successor = findMin(node.right); // 중위 후속자
            node.data = successor.data;
            node.right = deleteRecursive(node.right, successor.data);
        }
        return node;
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public Node getRoot() {
        return root;
    }
}

BST의 시간 복잡도

연산평균 시간 복잡도최악 시간 복잡도 (편향 트리)

탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

---

추가적으로 고려할 점

• 트리의 균형 문제를 해결하려면 AVL 트리, 레드-블랙 트리 등 균형 이진 탐색 트리를 사용하는 것이 좋습니다.
• BST는 정렬된 데이터를 관리하거나 동적 데이터 삽입/삭제가 필요한 경우 매우 유용합니다.