이진 탐색 트리의 원리와 구현 - (1)

들어가며

• 이진 탐색 트리(Binary Search Tree, BST)는 중복된 데이터를 허용하지 않으며, 데이터가 트리에 삽입될 때 특정한 조건을 따라 저장되는 이진 트리를 말한다.
• 기존의 이진 트리에서 데이터를 탐색할 때 해당 데이터가 트리의 어느 부분에 존재하는지 알 수 없으므로 모든 노드를 탐색해야하는 문제가 있다.
• 이진 탐색 트리는 해당 문제를 해결하기 위해 고안된 자료구조로, 데이터가 삽입될 때 해당 원소와 현재 노드가 가지고 있는 원소를 비교하여 크다면 우측, 작다면 좌측으로 내려가며 저장되는 구조로 되어있다.
• 이는 데이터를 삽입, 삭제할 때 마다 자동적으로 정렬이 수행되는 구조이며 실제로 중위 순회를 BST에 수행할 시 오름차순으로 이루어진 데이터를 얻을 수 있다.
  • 이렇게 데이터의 입 출력을 수행할 때마다 데이터가 자동적으로 정렬되어 있는 자료구조를 associative container라고도 부른다.
• 이진 탐색 트리를 사용하여 데이터를 탐색할 시에 값을 비교할 때 마다 탐색 범위가 절반씩 줄어드므로 특정한 상황이 아니라면 평균적으로 O(logN)이 걸린다.

 

 

이진 탐색 트리의 구현

• 이진 탐색 트리의 구현은 연결 리스트를 통하여 수행하며 아래와 같은 연산을 구현할 것이다.
  • 데이터의 삽입
  • 데이터의 삭제
  • 데이터의 존재 유무
  • 해당 이진 탐색 트리의 순회(traversal) - 해당 순회는 중위 순회(in-order traversal)로 구현할 것이다.
• 노드의 구조와 우리가 구현할 이진 탐색 트리의 전체적인 구조는 다음과 같다.

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

class BinarySearchTree{
    Node root;

    BinarySearchTree(){
        this.root = null;
    }

    public void addNode(int key){
        
    }

    public boolean searchNode(int key){
        
    }

    public void removeNode(int key){
        
    }

    public void traversal(Node cur){
        if (cur == null){
            return;
        }

        traversal(cur.left);
        System.out.print(cur.data + " ");
        traversal(cur.right);
    }
}

• 순회의 경우 이전에 이미 구현한 적이 있으므로 여기서는 이미 구현되어 있다고 가정한다.

 

 

데이터의 삽입

• 데이터의 삽입은 이진 탐색 트리의 원리인 대소 비교를 통해 삽입할 위치를 찾는 것에서 부터 시작된다.
• 루트부터 시작해 삽입할 데이터의 값과 트리에 존재하는 값을 비교한다.
  • 이때 삽입할 데이터의 값 < 현재 위치의 데이터 값 이라면 삽입할 위치는 현재 위치에서 좌측으로 이동한다.
  • 삽입할 데이터의 값 > 현재 위치의 데이터 값 이라면 삽입할 위치는 현재 위치에서 우측으로 이동한다.
• 이후 이동한 위치가 null로 비어있는 공간이라면 새로운 노드를 만들어 달아주면 종료된다.
• 간단한 그림으로 예시를 들면 아래와 같은 상황이 있다고 가정하자.

이진 탐색 트리에 원소를 삽입

• 이 경우, 8은 우선 root인 10와 대소비교를 수행한다. 8 < 10이기 때문에 원소가 삽입될 장소는 10의 좌측인 5로 이동하게 된다.

원소가 삽입되는 장소인 cur과 부모 노드를 가리키는 pre

• 이후 8은 삽입될 장소를 가리키는 cur에 저장된 5와 대소비교를 수행한다. 8 > 5 이기 때문에 cur은 5의 우측으로 이동하게 된다.
• 이때 cur는 null을 가리킨다. 그림에서 보듯이 5의 우측 자식은 null로 존재하지 않기 때문이다.
• 따라서 이 장소는 8을 저장하는데 적합해 보인다. 하지만 링크를 잇는데 cur로는 부족하다. 이전 위치를 기억해야하는 포인터가 하나 더 필요하다.
• 이를 위해 pre가 존재한다. pre는 cur의 직전 노드를 가리키기 때문에 pre.right = new Node(key)라는 구문으로 링크를 이으면서 새로운 노드를 만들어 붙일 수 있다.

pre를 통해 새로운 노드와 부모 노드 간 링크가 설정된 사진

• 해당 과정을 코드로 옮기면 아래와 같다.

public void addNode(int key){
    if (root == null){
        root = new Node(key);
        return;
    }

    if (searchNode(key)){
        return;
    }

    Node cur = this.root;

    while (true){
        Node pre = cur;

        if (cur.data < key){
            cur = cur.right;

            if (cur == null){
                pre.right = new Node(key);
                break;
            }
        } else{
            cur = cur.left;

            if (cur == null){
                pre.left = new Node(key);
                break;
            }
        }
    }
}

• searchNode(key)는 해당 노드가 이미 트리에 존재하는지를 확인하는데 사용한다. 이전에도 서술했지만 BST는 중복된 데이터를 허용하지 않는다.

 

 

정리

• 이번에는 원소의 삽입을 알아보았다. 다음에는 원소의 삭제에 대해 구현해 볼 것이다 원소의 삭제는 삽입보다 더 까다롭다. 그리고 노드가 존재하는지 탐색하는 searchNode 역시 다음 시간에 구현해 볼 것이다.