비선형 자료구조 - 이진 탐색 트리 (Binary Search Tree) 정의 및 탐색, 삽입, 삭제 구현

시작하며.

앞서 트리가 무엇인지 이진 트리는 무엇인지 이진 트리의 성격에 따라
포화 이진 트리, 완전 이진 트리, 정 이진 트리, 편향 이진 트리 등등 어떤 종류가 있는지
그리고 어떻게 순회할 수 있는지 등을 알아봤습니다.
오늘은 이진 트리의 종류 중 하나인 이진 탐색 트리에 알아보며 데이터를 삽입하고 삭제하는 방법도 정리하고자 합니다.

이진 탐색 트리(Binary Search Tree, BST)를 알아야 하는 이유

탐색 효율성: 이진 탐색 트리는 데이터를 효율적으로 탐색할 수 있는 구조입니다. 각 노드는 특정한 값을 가지고 있으며, 왼쪽 서브트리에는 작은 값의 노드가, 오른쪽 서브트리에는 큰 값의 노드가 위치합니다. 이를 통해 탐색 시 비교를 통해 탐색 범위를 반씩 줄여나가므로, 탐색 속도가 빠릅니다. 이진 탐색의 시간 복잡도는 O(log N)으로 매우 효율적입니다.

정렬된 데이터 관리: 이진 탐색 트리는 데이터가 정렬된 상태로 유지됩니다. 새로운 데이터가 추가될 때마다 적절한 위치에 삽입되어 정렬된 상태를 유지합니다. 이러한 특성은 데이터의 검색, 삽입,삭제 등 다양한 작업에서 유용합니다.

범위 검색과 순회: 이진 탐색 트리는 특정 범위의 데이터를 검색하거나 순회할 수 있는 기능을 제공합니다. 주어진 범위에 속하는 데이터를 찾는 작업이나 데이터를 정렬된 순서로 순회하는 작업을 빠르고 간편하게 수행할 수 있습니다.

데이터의 삽입과 삭제: 이진 탐색 트리는 데이터의 삽입과 삭제를 효율적으로 처리할 수 있습니다. 데이터의 삽입은 정렬된 위치에 적절하게 삽입되며, 데이터의 삭제는 트리 구조를 유지하면서 삭제될 노드를 대체하는 방식으로 수행됩니다.

다양한 응용 분야: 이진 탐색 트리는 데이터의 탐색과 관리에 널리 사용됩니다. 예를 들어, 데이터베이스 시스템의 인덱스 구조, 파일 시스템의 파일 검색, 자료 구조의 구현 등 다양한 응용 분야에서 이진 탐색 트리가 활용됩니다.

이진 탐색 트리를 알고 있다면 데이터의 효율적인 탐색과 관리를 할 수 있으며, 다양한 문제를 해결하는 데에 활용할 수 있습니다. 이러한 이유로 이진 탐색 트리는 컴퓨터 과학에서 중요한 자료 구조 중 하나입니다.

 

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

위 그림은 아래와 같은 규칙으로 구성 된 이진 트리입니다.
- 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
   (왼쪽 서브트리의 모든 노드는 현재 노드보다 작은 값을 가집니다.)
- 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
   (오른쪽 서브트리의 모든 노드는 현재 노드보다 큰 값을 가집니다.)
- 각각의 서브트리도 이진 탐색 트리를 유지
  (왼쪽과 오른쪽 서브트리도 이진 탐색 트리여야 합니다.)
- 중복된 키를 허용하지 않습니다.

이런 규칙으로 구성 된 트리를 이진 탐색 트리라고 합니다.

이진 탐색 트리의 특징.

이진 탐색 트리의 특징은 위와 같은 규칙에 따라 데이터가 정렬 되며
이진 트리에 비해 탐색 속도가 빠릅니다.(균형이 유지되었을 때)
- 균형 상태 : O(logN)
- 불균형 상태 : O(N)

이진 탐색 트리의 탐색.

찾고자 하는 데이터를 루트 노드부터 비교합니다.
찾고자 하는 데이터가 루트 노드보다 작다면 왼쪽으로, 크다면 오른쪽 노드로 이동해 반복 합니다.
찾는 데이터가 없다면 null을 반환합니다.
어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어지기 때문에 효율적입니다.

 

이진 탐색 트리 삽입.

루트 노드부터 비교를 시작합니다. (중복 키 발견 시 노드 추가하지 않고 종료)
삽입할 키가 현재 노드의 키보다 작다면 왼쪽으로 이동합니다.
삽입할 키가 현재 노드의 키보다 작다면 오른쪽으로 이동합니다.
Leaf 노드에 도달한다면 키를 비교해 작다면 왼쪽, 크면 오른쪽에 삽입해 줍니다.

이진 탐색 트리 삽입 코드로 구현하기.

위 그림과 같은 결과가 나올 수 있도록 재귀 형태로 코드를 구현해봅시다.
삽입하는 순서가 달라도 루트 기준으로 이진 트리 규칙대로 삽입됩니다.
출력은 Level order traversal(레벨 순회)로 너비 우선 순서로 순회하는 방법으로 출력하겠습니다.

// Node 클래스 생성 - Node 클래스를 만들어 데이터와 왼쪽, 오른쪽 자식 노드 정보를 저장할 수 있게 구현합니다.

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

// 이진 탐색 트리 클래스 및 데이터 추가 메서드

class BinarySearchTree {
    Node root; 

    BinarySearchTree(int value) { // 루트를 갖는 생성자
        this.root = new Node(value, null, null);
    }

    public Node insertNode(Node parent, int value) {
        if (parent == null) { // 이진 탐색 트리가 비어있다면
            return new Node(value, null, null); // 새로 들어온 value를 루트로 삽입해줍니다.
        }

        if (value < parent.value) {
            // 삽입할 value가 현재 노드의 값보다 작은 경우, 왼쪽 서브트리로 이동하여 재귀적으로 삽입
            parent.left = insertNode(parent.left, value);
        } else {
            // 삽입할 value가 현재 노드의 값보다 큰 경우, 오른쪽 서브트리로 이동하여 재귀적으로 삽입
            parent.right = insertNode(parent.right, value);
        }
        return parent; // 부모 노드를 가리키는 포인터로서, 삽입 과정에서 부모 노드의 링크를 갱신
    }
    
    // 출력을 위한 레벨 순회 메서드
        public void leveOrder(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node); // 주어진 노드 node를 큐에 추가
        while (!queue.isEmpty()) {
            Node cur = queue.poll(); // 큐에서 현재 노드를 꺼내고 값을 출력
                                     // 다음 에는 먼저 들어온 왼쪽 노드 먼저 출력하고 다시 반복
                                     // 다음에는 먼저 들어온 오른쪽 노드 먼저 출력하고 다시 반복
            System.out.print(cur.value + " ");

            if (cur.left != null) {         // 현재 노드의 왼쪽 자식 노드가 있다면 큐에 추가
                queue.offer(cur.left);
            }
            if (cur.right != null) {         // 현재 노드의 오른쪽 자식 노드가 있다면 큐에 추가
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
}

public class BinarySearchTreeInsertTest {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree(8); // 8이 루트인 이진탐색트리 생성
        bst.root = bst.insertNode(bst.root, 4);
        bst.root = bst.insertNode(bst.root, 10);
        bst.root = bst.insertNode(bst.root, 5);
        bst.root = bst.insertNode(bst.root, 2);
        bst.root = bst.insertNode(bst.root, 15);
        bst.root = bst.insertNode(bst.root, 9);
        bst.root = bst.insertNode(bst.root, 3);
        bst.root = bst.insertNode(bst.root, 1);
        System.out.println("7 삽입 전");
        bst.leveOrder(bst.root);
        System.out.println("7 삽입 후");
        bst.root = bst.insertNode(bst.root, 7);
        bst.leveOrder(bst.root);
        System.out.println("13 삽입 후");
        bst.root = bst.insertNode(bst.root, 13);
        bst.leveOrder(bst.root);

    }
}

 

이진 탐색 트리 삭제.

이진 탐색 트리 삭제는 경우에 따라 달라집니다.

• 삭제 대상 노드가 Leaf인 경우(자식 노드가 없는 경우)
  - 삭제 대상 노드 삭제
  - 부모 노드의 해당 자식 링크를 null로 변경
  - 아래 그림처럼 리프 노드인 3을 삭제한다고 하면 3을 삭제하고 부모 노드인 오른쪽 링크를 null로 바꿔줍니다.

 

• 삭제 대상 노드에 자식 노드가 하나 있는 경우(왼쪽 또는 오른쪽 자식 노드가 하나인 경우)
  - 자식 노드를 삭제 대상 노드의 부모 노드에 연결
  - 삭제 대상 노드 삭제
  - 아래 그림처럼 자식 노드가 하나인 2를 삭제한다고 하면 자식 노드인 1의 정보를 임시로 저장하고
     2의 부모 노드인 4의 자식 노드가 될 수 있도록 연결을 갱신해주고 2는 삭제해줍니다.

• 삭제 대상 노드에 자식 노드가 하나 있는 경우
  - 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택
  - 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택
  - 왼족 서브 트리 가장 큰 노드 또는 오른쪽 서브 트리 가장 작은 노드 중
     선택한 노드를 삭제 대상 노드 위치로 올림(둘중 하나 선택)
  - 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행
  - 삭제 대상 노드 삭제

 

이진 탐색 트리 삭제 코드로 구현하기.

마찬가지로 위 그림과 같이 나올 수 있도록 코드를 구현해 봅시다.
노드 및 이진 탐색 트리 클래스는 동일하고 자식 노드를 둘다 가진 경우는 방법 1에 대한 삭제 메서드를 구현하겠습니다.

    public Node removeNode(Node parent, int value) {
        if (parent == null) { // 트리가 비어있는 경우 null로 반환
            return null;
        }

        if (value < parent.value) {
            // 삭제할 값이 현재 노드의 값보다 작은 경우, 왼쪽 서브트리에서 삭제 수행
            parent.left = removeNode(parent.left, value); // 왼쪽 자식 노드를 갱신
        } else if (value > parent.value) {
            // 삭제할 값이 현재 노드의 값보다 큰 경우, 오른쪽 서브트리에서 삭제 수행
            parent.right = removeNode(parent.right, value); // 오른쪽 자식 노드를 갱신
        } else {   // 삭제할 값과 현재 노드의 값이 같은 경우, 삭제할 노드를 찾았음
            if (parent.left == null) {
                // Case 1: 삭제할 노드가 왼쪽 자식 노드를 가지지 않는 경우
                return parent.right; // 오른쪽 자식 노드를 반환하여 부모 노드의 링크 갱신
            } else if (parent.right == null) {
                // Case 2: 삭제할 노드가 오른쪽 자식 노드를 가지지 않는 경우
                return parent.left; // 왼쪽 자식 노드를 반환하여 부모 노드의 링크 갱신
            } else {
                // Case 3: 삭제할 노드가 두 개의 자식 노드를 가지는 경우
                Node predecessor = parent; // 삭제할 노드의 바로 이전 노드 (왼쪽 서브트리에서 가장 큰 값)
                Node successor = parent.left; // 왼쪽 서브트리에서 시작하여 가장 큰 값을 찾기 위한 노드

                while (successor.right != null) {
                    // 왼쪽 서브트리에서 가장 큰 값을 찾기 위해 오른쪽으로 이동
                    predecessor = successor;
                    successor = successor.right;
                }
                predecessor.right = successor.left; // 대체된 값을 삭제할 노드의 위치에 설정
                parent.value = successor.value; // 대체된 값의 원래 위치를 삭제
            }
        }
        return parent; // 삭제된 노드의 부모 노드의 링크를 갱신하기 위해 반환
    }

public class BinarySearchTreeInsertTest {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree(8); // 8이 루트인 이진탐색트리 생성
		// ...

        bst.root = bst.removeNode(bst.root, 3);
        System.out.println("3 삭제 후");
        bst.leveOrder(bst.root);
        bst.root = bst.removeNode(bst.root, 2);
        System.out.println("2 삭제 후");
        bst.leveOrder(bst.root);
        bst.root = bst.removeNode(bst.root, 8);
        System.out.println("8 삭제 후");
        bst.leveOrder(bst.root);

    }
}