20. 이진 탐색 트리(Binary Search Tree)

  얼마전 회사 업무를 진행하던 도중에 프로그램 하나에 문제가 생겨서 살펴보게 되었는데, 해당 프로그램의 Select 구문에 Binary Search가 적용되어서 문제가 생긴 적이 있었다. 우리가 알고리즘을 배우면서 효율적으로 문제를 푸는 방법에 대해 많이 살펴보게 되는데, 항상 효율성이 정답은 아니다. 이번에 배울 Binary Search Tree 역시 그렇다. 이를 적용하게 되면 일반적인 Search 보다 훨씬 효율적으로 문제를 풀 수 있지만 항상 이를 적용 한다고 옳은 것은 아니다.

1. Binary Search 란?

  이진 탐색 트리(Binary Search Tree)를 알기 위해서는 우선 Binary Search에 대해알아야 한다. Binary Search는 알고리즘 보다는 자료를 저장하는 구조의 일종이다. 일반적인 탐색은 데이터에 있는 각 요소들은 인덱스 값을 기준으로(혹은 다른 Key값을 기준으로) 순차적으로 탐색하며 내가 보고 싶은 요소를 찾는 것이다. 하지만 인덱스 값이(혹은 Key) 내가 찾고자 하는 어떤 값의 의미를 갖고 있고, 순차적으로 정렬되어 있다면 탐색 작업은 훨씬 수월해진다. 예를 들어 설명해보자. 

  만약 당신이 지도가 없는 상태로 마포구 양화로 125를 찾아야 한다고 가정해보자. 운좋게 어떻게 흐르고 흘러 양화로를 찾아서 왔고 양화로 어딘가에 서있다. 당신이 지금 번지수 (양화로 110의 110)를 모르고 있다고 하면, 지금 위치든 혹은 양화로 1로 이동해서든 하나 씩 모두 들려보면서 125번지를 찾아야 한다. 하지만, 우리는 양화로의 번지수가 1부터 순차적으로 연속된다는 점을 기본 상식으로 알고 있다. 설령 몰랐다고 해도 직관적으로 1번지 부터 시작하지 뜬금없이 297번지부터 시작하지는 않을 것이라는 점은 안다. 그렇다면 내 위치를 기준으로 125번지가 큰 수인지 작은수 인지 체크하여 그 쪽 방향으로 가면 된다. 그 다음 건물에서 다시 한번 번호를 찾아 125와 비교하며 찾아 간다면, 앞서 말한 방법보다 쉽게 찾을 수 있다. 양화로의 번지수가 순차적으로 되어 있지 않다면, 당신은 모든 건물을 찾아가보는 방법밖에 없다. (TMI 주의! 양화로 125는 사실 이 글을 쓰고 있었던 위치다.) 

  우리가 술자리에서 하는 게임 중 UpDown 게임도 사실 이진 탐색을 활용한 게임이다. 우리가 1부터 100까지의 숫자를 순차적으로 탐색하게된다면 모든 수의 탐색을 거쳐야하므로 평균적으로 50번의 탐색이 일어난다. 하지만, UpDown 게임에서 50번을 거치면 숫자를 찾지 않는다. 특정 수를 부르면 해당 값의 Up Down을 말하며 찾게 되기 떄문에, 숫자 선택만 적절히 한다면 (1/2값이 아닌 다른 수를 부르지만 않는다면) 6번안에 원하는 숫자를 찾을 수 있게 된다.

  물론 이렇게 강력한 이진 탐색이지만 사전 작업이 필요하다. 앞서 말했듯이 인덱스 값 혹은 Key 값이 내가 찾으려는 값의 의미를 가지며, 이 값이 순차적으로 Sorting 되어 있어야 한다.

2. 이진 탐색 트리(BST) 

  이런 이진 탐색 방식을 가장 잘 담아낼 수 있는 자료 구조는 트리 방식이다. 트리 구조는 숫자 비교하는데 있어 매우 강력할 뿐만 아니라, Index 탐색에 있어 Queue나 Stack 보다 훨씬 유리하다. 이진 탐색 트리는 아래와 같은 특징을 가진다.

• 이진 탐색트리의 자식 노드의 개수는 2개 이하이다.
• 모든 원소는 중복된 값을 가져서는 안된다.
• 왼쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 작다.
• 오른쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 크다.
• 왼쪽 서브트리와 오른쪽 서브트리는 모두 이진 탐색 트리이다.

  이제 위의 특징을 만족하는 이진 탐색트리의 예시를 살펴보자.

  이진 탐색 트리를 Java 코드로 구현 하기 위해서는 우선 각 노드의 구조를 구현해야 한다. 해당 노드에 필요한 정보는 노드에 담을 데이터 값, 그리고 해당 노드의 왼쪽, 오른쪽 서브 트리의 값이다. 위의 이진 탐색 트리의 구조를 표현하면 아래와 같이 나올 것이다.

  노드 하나에 총 3가지의 정보가 들어가야 할 것이고, Data와 자신의 자식 노드에 대한 연결이 되어 있어야 한다. 이를 코드로 구현하면 아래와 같다.

class Node{
    // 데이터 선언
    private int data;
    private Node left;
    private Node right;
    
    // Constructor
    public Node(int data){
        this.setData(data);
        setRight(null);
        setLeft(null);
    }
    
    // getter, setter
    public int getData() {return data;}
    public void setData(int data) {this.data = data;}
    public Node getLeft() {return left;}
    public void setLeft(Node left) {this.left = left;}
    public Node getRight() {return right;}
    public void setRight(Node right) {this.right = right;}
}

  3. 이진 탐색트리의 삽입 연산

  위의 이진 탐색 트리에서 25라는 값을 삽입한다고 가정해보자. 25를 트리에 입력하게 되면 우선 루트 노드와 비교하면서 방향을 정하게 된다. 루트 노드는 24이므로 25는 루트 값보다 크다. 따라서, 24와 비교를 하게 되면 우측 방향으로 이동하게 된다. 그 다음 노드인 32와 비교했을 때는 더 작은 값이므로, 좌측으로 이동하게 된다.

  만약 가장 아래까지 내려가서 노드가 null이라면 그 자리에 바로 들어가게 된다. 위와 같은 경우엔 27 노드의 좌측에 들어가게 된다면 삽입입이 끝나게 된다. 이 과정을 Java 언어로 표현해보자.

    public void insert(int data){
        Node node = new Node(data);
        
        if(root == null){
            root = node;
            return;
        }
        
        Node current = root;
        Node temp = current;
        while(true){
            if(current.getData()>data){
                current = current.getLeft();
                if(current == null){
                    temp.setLeft(node);
                    return;
                }
            }
            else if(current.getData()<data){
                current = current.getRight();
                if(current == null){
                    temp.setRight(node);
                    return;
                }
            }
            else{
                System.out.println("중복된 값입니다.");
                return;
            }
        }
        
    }

4. 이진 탐색트리의 삭제 연산

  이진 탐색트리의 삭제 연산은 삽입보다는 조금 어렵다. 삭제를 하기 위해서는 총 3가지 경우의 수가 존재한다.

- 삭제하려는 노드가 리프 노드인 경우

  이 경우 간단하게 탐색 작업을 거친 후 해당 노드를 삭제하면 쉽게 구현 할 수 있다. 이 경우에는 어렵지 않다. Root인 24를 기준으로 탐색을 실시 한 뒤, 21 노드를 찾아서 해당 노드만 없애주면 간단하다. 이때, 21 노드의 상위 노드인 16 노드의 우측 노드 값 역시 삭제 해주어야 한다.

- 삭제하려는 노드의 자식 노드가 1개인 경우

  위 이진탐색 트리 중에서 32 노드를 지우려는 경우이다. 이 때는 32 노드를 삭제 한 후 해당 위치로 자식 서브트리를 위로 올려 주어야 한다. 이 경우에도 물론, 24 노드의 우측에 27 노드를 입력 시켜 27 아래에 있는 서브트리가 24 노드의 좌측으로 이동 해야 한다. 

- 삭제하려는 노드의 자식 노드가 2개인 경우

  24 노드를 지운다고 할 때, 21과 27 두 노드 중 하나의 값을 상위 노드로 올려야 한다. 어느 방향의 노드를 올려도 이진 탐색트리의 구조는 깨지지 않게 된다. 따라서, 어떤 노드를 올릴 지 선택 기준을 세워 놓으면 이진 탐색트리는 유지 된다. 이 값을 조금 더 정확하게 설명하면, 삭제하려는 노드 오른쪽 서브트리의 최소값 혹은 삭제하려는 노드의 왼쪽 서브트리의 최대값 일 것이다. 어느 값을 선택하더라도 크게 상관이 없으므로, 이번 코드에서는 왼쪽 서브트리의 최대값을 선택하도록 하겠다. 즉, 위의 이진탐색트리에서 21 값을 선택한다.

  삭제 연산에 대한 Java 코드는 아래와 같다.

    public void delete(int data){
        if(root==null){
            System.out.println("삭제할 노드가 없습니다.");
            return;
        }
        
        Node parent = root;
        Node current = root;
        
        // parent의 좌,우측을 나타내는 변수
        boolean isLeft = false;
        
        // 삭제 하려는 노드 찾기
        while(current.getData()!=data){
            parent = current;
            if(current == null){
                System.out.println("노드를 찾을 수 없습니다.");
                return;
            }
            else if(current.getData()<data){
                isLeft = false;
                current = current.getRight();
            }
            else if(current.getData()>data){
                isLeft = true;
                current = current.getLeft();
            }
        }
        
        // Case1 : 자식 노드가 없는 경우
        if(current.getLeft()==null && current.getRight()==null){
            // 삭제하려는 노드가 root인 경우
            if(current == root) root = null;
            
            if(isLeft){
                parent.setLeft(null);
                
            }
            else{
                parent.setRight(null);
            }
        }
        
        // Case2: 자식 노드가 1개 인 경우
        else if(current.getLeft()==null){    // 오른쪽 서브트리가 존재
            if(current==root){    // 삭제하려는 노드가 root인 경우(parent가 존재하지 않는 경우)
                root = current.getRight();
            }
            if(isLeft){
                parent.setLeft(current.getRight());
            }
            else{
                parent.setRight(current.getRight());
            }
            
        }
        else if(current.getRight()==null){    // 왼쪽 서브트리가 존재
            if(current==root){    // 삭제하려는 노드가 root인 경우(parent가 존재하지 않는 경우)
                root = current.getLeft();
            }
            if(isLeft){
                parent.setLeft(current.getLeft());
            }else{
                parent.setRight(current.getLeft());
            }
        }
        
        // Case3: 자식 노드가 2개인 경우 (왼쪽 서브트리 선택)
        else if(current.getLeft()!=null && current.getRight()!=null){
            if(current==root){    // 삭제하려는 노드가 root인 경우(parent가 존재하지 않는 경우)
                root = current.getLeft();
            }
            if(isLeft){
                parent.setLeft(current.getLeft());
            }
            else{
                parent.setRight(current.getRight());
            }
        }
    }

  이진 탐색 트리의 코딩은 위와 같이 구현 할 수 있다. 이진 탐색 트리는 완전 트리 구조로 구현하지 않는 이상 그리 어렵지 않게 구현 할 수 있다. 완전 트리로 구현하고 싶다면 꽤나 많은 작업이 필요하고, 전위, 중위, 후의 탐색의 개념까지 알고 있어야 한다. 그래서 다음 시간에는 트리 구조에서의 전위, 중위, 후위 탐색에 대해 알아보도록 하자.