[자료구조] BST - 이진탐색 트리(Binary Search Tree)

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

BST는 각각의 Node가 2개의 하위 노드를 가진 모양의 Tree이다. 단 BST는 정렬된 상태로 Node가 저장된다. 즉 순서가 있다는 것이다.
쉽게 이야기 하자면 특정 노드가 있을때 그 노드의 왼쪽 하위 노드는 해당 노드보다 data값이 작아야하며 반대로 오른쪽 하위 노드는 data값이 해당 노드보다 커야한다. 그림을 통해 확인해 보면

위 그림을 확인해 보자 root노드인 50의 왼쪽 node의 data 값은 30이고 오른쪽 노드의 data값은 90이다. 해당 규칙을 지키며 tree를 구성한 것이 BST이다.

설계

그렇다면 바로 구현을 시작해보자

Node 설계

우선은 Tree의 각각의 노드를 설계할 것이다. 그림에서 처럼 좌우의 하위 Node를 가지므로 2개의 Node pointer와 data값을 저장하는 data변수가 필요할 것이다. 아래의 그림처럼 설계하면 될 것이다.

이는 DLL의 Node구조와 똑같다 아래는 코드이다.

class Node
{
    int data;
    Node left, right;

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

딱히 별거 없이 쉽게 설계할 수 있다.

BST 설계

다음은 Node를 가지고 BST를 설계한다.
멤버 변수는 최상위 노드를 가리키는 root정도만 있으면 될것이다. 메소드는 삽입, 삭제, 중위순회를 통한 출력 정도만 있으면 Tree의 주요 기능은 구현한 거라고 생각한다. 아래는 BST의 스켈레톤 코드이다.

public class BST
{
    private Node root; //최상위 Node

    public BST() {} //생성자
    public boolean isEmpty() {} //Tree가 비어있는지 판단

    //data 삽입\\
    public void insert(int data) {}
    private Node insertBST(Node temp, int data) {}

    //data 삭제\\
    public void delete(int data) {}
    private Node deleteBST(Node temp, int data) {}

    private int getHeight(Node temp) {} //특정 노드에서 높이를 반환
    private int getNumofNode(Node temp) {} //특정 노드의 하위 노드 개수를 반환
    private Node findMaxNode(Node temp) {} //해당 노드의 하위 노드들 중 가장 큰 값을 가지는 Node를 반환
    private Node findMinNode(Node temp) {} //해당 노드의 하위 노드들 중 가장 작은 값을 가지는 Node 반환

    public void print() {} //root서 부터 삽입된 값을 출력하는 메소드
    private void inorder(Node temp) {} //중위 순회 메소드
}

주석에 설명한 대로 특정한 기능을 하는 부분을 메소드로 구현하였다. private로 구현된 메소드는 거의 대부분 public으로 선언된 메소드에서 사용되는 메소드라 생각하면 된다.

 

삽입

삽입이다. 삽입은 정말 쉽다. 우선 BST는 기본적으로 정렬되어있기때문에 삽입시에 값을 비교하면서 Node의 이동이 진행되어야 한다. 나는 여기서 재귀적인 방법을 사용하였다. 코드를 바로 확인해 보자

public void insert(int data) {root = insertBST(root, data);}

private Node insertBST(Node temp, int data)
{
    // 삽입할 노드를 탐색한다(재귀) \\
    if(temp == null) {temp = new Node(data);}
    else if(data < temp.data) {temp.left = insertBST(temp.left, data);}
    else if(data > temp.data) {temp.right = insertBST(temp.right, data);}
    return temp;
}

insert() 메소드는 사용자에 의해 호출되는 메소드이다. 이후 insert() 메소드 내에서 insertBST() 메소드가 호출되는데, 코드를 살펴보자
이동한 노드 temp가 null이면 그곳에 값을 삽입하고(new Node(data)) 아니라면 현재 노드의 data값과 삽입할 data값을 비교하여 삽입할 자리로 계속해서 이동한다.(여기서 재귀방법을 사용)

삽입은 간단하게 저렇게 구성할 수 있을 것이다.

삭제

다음은 삭제이다. 삭제는 크게 3가지의 경우로 나뉜다.

• case 1: 삭제할 노드가 자식노드가 없을(리프 노드) 경우
• case 2: 삭제할 노드의 자식노드가 1개일 경우(왼쪽, 오른쪽 중 하나)
• case 3: 삭제할 노드의 자식노드가 2개일 경우

이렇게 3가지의 경우로 나누어 설계하였다. 각 case별로 자세히 설펴보자
우선 case 1 "삭제할 노드가 자식노드가 없을 경우"는 너무 간단하게 해당 노드를 삭제해버리면 된다. 왜냐면 부모 노드와 연결해줘야할 자식 노드가 없기때문이다. 그냥 null로 처리해버리면 끝난다. 그림을 확인해 보면

위 그림 처럼 삭제될 것이다.

 

두번째 case 2 "삭제할 노드의 자식노드가 1개일 경우"이다. 이것도 간단하다. 삭제할 노드의 자식노드를 부모 노드에 연결해주면 된다.

 

마지막 case 3 "삭제할 노드의 자식노드가 2개일 경우"이다. 이는 조금 복잡하다. 그림을 통해 보자면...

우선 위 그림처럼 30을 삭제한다고 하면 삭제할 30노드를 탐색할 것이다. 30노드를 탐색하고 나서 보니 30노드는 자식노드가 2개인 경우에 해당된다. 이를 때는 "오른쪽 하위노드에서 가장 작은 값을 가지는 노드" 또는 "왼쪽 하위노드에서 가장 큰 값을 가지는 노드"를 찾아서 30노드의 위치에 옮기고 그 노드를 삭제하면 된다. 아래 그림이 다음 단계이다.

30대신에 35가 그 위치를 대신하고 아래에 있는 35노드를 삭제하면 BST의 모양을 유지한채로 삭제가 가능하다.

 

근데 여기서 생각해봐야 할 것이 있다. 바로 아래의 그림일 경우에는 어떤 문제가 있는가 하면,

BST의 규칙에는 어긋나진 않지만 트리가 너무 한쪽으로 치우친 모양이다. 이렇게 되면 50을 탐색할때 4번의 탐색이 이루어지고 이런 구조의 규모가 큰 Tree라면 호율성이 밑바닥을 칠 것이다. 따라서 삭제를 할때, 최대한 좌우 균형을 유지하면서 삭제를 진행 해야 할 것이다. 즉 이말은 삭제할때 높이나 노드의 개수를 계산해서 유동적으로 삭제를 하자는 것이다.

그래서 구현한 메소드가 바로 특정 노드의 높이를 리턴하는 getHeight()메소드와 특정 노드의 하위 노드 개수를 리턴하는 getNumofNode()메소드인 것이다.
그리고 하위 노드들 중에서 가장 큰 값을 찾는 findMaxNode()와 반대로 작은 값을 찾는 findMinNode()메소드도 필요하다.

다음은 삭제 알고리즘의 코드이다.

주석을 확인하면서 읽어주세요!!

public void delete(int data) {root = deleteBST(root, data);}
private Node deleteBST(Node temp, int data)
{
    if(temp != null)
    {
        Node p;

        // 삭제할 노드까지 이동하는 과정(재귀) \\
        if(temp.data > data) {temp.left = deleteBST(temp.left, data);}
        else if(temp.data < data) {temp.right = deleteBST(temp.right, data);}

        // case 1: 삭제할 노드가 리프노드일 경우 \\
        else if(temp.left == null && temp.right == null)
            {temp = null;}

        // case 2-1: 삭제할 노드의 자식 노드가 1개(left)일 경우 \\
        else if(temp.right == null)
        {
            p = temp;
            temp = temp.left;
            p = null;
        }

        // case 2-2: 삭제할 노드의 자식 노드가 1개(right)일 경우 \\
        else if(temp.left == null)
        {
            p = temp;
            temp = temp.right;
            p = null;
        }
        // case 3: 삭제할 노드의 자식노드가 2개일 경우 \\
        else
        {
            //최소한의 균형을 위해 삭제하고자 하는 노드의 좌우 높이, 노드갯수를
            //비교해서 삭제를 유동적으로 실시함
            boolean flag; // left => true, right => false

            //case 3-1: 삭제할 노드의 왼쪽 subTree가 더 높을때\\
            if(getHeight(temp.left) > getHeight(temp.right))
            {
                p = findMaxNode(temp.left);
                flag = true;
            }

            //case 3-2: 삭제할 노드의 오른른쪽 subTree가 더 높을때\\
            else if(getHeight(temp.left) < getHeight(temp.right))
            {
                p = findMinNode(temp.right);
                flag = false;
            }

            //case 3-3: 양쪽의 subTree의 높이가 같을때\\
            else
            {
                //case 3-3-1: 왼쪽 subTree의 node 개수가 더 많을때\\
                if(getNumofNode(temp.left) >= getNumofNode(temp.right))
                {
                    p = findMaxNode(temp.left);
                    flag = true;
                }

                //case 3-3-2: 오른쪽 subTree의 node 개수가 더 많을때\\
                else
                {
                    p = findMinNode(temp.right);
                    flag = false;
                }
            }

            temp.data = p.data;

            if(flag) {temp.left = deleteBST(temp.left, p.data);}
            else {temp.right = deleteBST(temp.right, p.data);}
        }
    }
    return temp;
}

주석으로 나눈 부분을 덩어리로 보면서 확인하면 될것같다.

 

inorder

다음은 중위 순회를 통한 Tree의 출력메소드를 구현하였다. 삽입 삭제를 잘 구현해도 확인할 방법이 없으니 출력 메소드도 나름(?) 중요하다. ㅎㅎ:D 바로 코드를 확인해보자

public void print()
{
    if(this.isEmpty()) {System.out.println("Tree is empty");}
    else {inorder(this.root); System.out.println();}
}

private void inorder(Node temp)
{
    if (temp != null)
    {
        inorder(temp.left);
        System.out.print(temp.data+" ");
        inorder(temp.right);
    }
}

이전에 썻던 Tree 포스팅에 중위순회에대한 이야기가 있었는데 그것을 이용해서 Tree의 출력을 표현했다. 정상적으로 출력된다면 Tree의 data값들이 모두 오름차순의 형태로 출력되어야 한다.

 

그 밖의 메소드

그 밖의 코드는 삭제메소드에 사용된getHeight(), getNumofNode(), findMaxNode(), findMinNode()의 코드이다.

// temp 노드의 높이를 반환한다. \\
private int getHeight(Node temp)
{
    if(temp == null) {return -1;}

    int leftSubTreeHeight = getHeight(temp.left) + 1;
    int rightSubTreeHegiht = getHeight(temp.right) + 1;

    return leftSubTreeHeight > rightSubTreeHegiht ? leftSubTreeHeight : rightSubTreeHegiht;
}

// temp노드의 하위노드의 개수를 반환한다. \\
private int getNumofNode(Node temp)
{
    if(temp == null) {return -1;}

    int leftSubTreeHeight = getHeight(temp.left) + 1;
    int rightSubTreeHegiht = getHeight(temp.right) + 1;

    return leftSubTreeHeight + rightSubTreeHegiht + 1;
}

// temp노드의 하위 노드들 중 가장 큰 값을 가지는 Node를 반환한다. \\
private Node findMaxNode(Node temp)
{
    if(temp.right == null) {return temp;}
    else {return findMaxNode(temp.right);}
}

// temp노드의 하위 노드들 중 가장 작은 값을 가지는 Node를 반환한다. \\
private Node findMinNode(Node temp)
{
    if(temp.left == null) {return temp;}
    else {return findMinNode(temp.left);}
}

전체 코드

전체 적인 코드는 아래 github 링크에서 자세히 확인 할 수 있다.

Java
https://github.com/JoSangYeon/Algorithm/blob/master/Tree/BST/BST.java

JoSangYeon/Algorithm

C++
https://github.com/JoSangYeon/Algorithm/blob/master/Tree/BST/Improved_BST.cpp

JoSangYeon/Algorithm

아래는 자바코드이다.

BST.java

public class BST
{
    private Node root; //최상위 Node

    public BST()
    {
        this.root = null;
    }
    public boolean isEmpty() {return root == null;}

    public void insert(int data) {root = insertBST(root, data);}
    private Node insertBST(Node temp, int data)
    {
        // 삽입할 노드를 탐색한다(재귀) \\
        if(temp == null) {temp = new Node(data);}
        else if(data < temp.data) {temp.left = insertBST(temp.left, data);}
        else if(data > temp.data) {temp.right = insertBST(temp.right, data);}

        return temp;
    }

    public void delete(int data) {root = deleteBST(root, data);}
    private Node deleteBST(Node temp, int data)
    {
        if(temp != null)
        {
            Node p;

            // 삭제할 노드까지 이동하는 과정(재귀) \\
            if(temp.data > data) {temp.left = deleteBST(temp.left, data);}
            else if(temp.data < data) {temp.right = deleteBST(temp.right, data);}

            // case 1: 삭제할 노드가 리프노드일 경우 \\
            else if(temp.left == null && temp.right == null)
                {temp = null;}

            // case 2-1: 삭제할 노드의 자식 노드가 1개(left)일 경우 \\
            else if(temp.right == null)
            {
                p = temp;
                temp = temp.left;
                p = null;
            }

            // case 2-2: 삭제할 노드의 자식 노드가 1개(right)일 경우 \\
            else if(temp.left == null)
            {
                p = temp;
                temp = temp.right;
                p = null;
            }
            // case 3: 삭제할 노드의 자식노드가 2개일 경우 \\
            else
            {
                //최소한의 균형을 위해 삭제하고자 하는 노드의 좌우 높이, 노드갯수를
                //비교해서 삭제를 유동적으로 실시함
                boolean flag; // left => true, right => false

                //case 3-1: 삭제할 노드의 왼쪽 subTree가 더 높을때\\
                if(getHeight(temp.left) > getHeight(temp.right))
                {
                    p = findMaxNode(temp.left);
                    flag = true;
                }

                //case 3-2: 삭제할 노드의 오른른쪽 subTree가 더 높을때\\
                else if(getHeight(temp.left) < getHeight(temp.right))
                {
                    p = findMinNode(temp.right);
                    flag = false;
                }

                //case 3-3: 양쪽의 subTree의 높이가 같을때\\
                else
                {
                    //case 3-3-1: 왼쪽 subTree의 node 개수가 더 많을때\\
                    if(getNumofNode(temp.left) >= getNumofNode(temp.right))
                    {
                        p = findMaxNode(temp.left);
                        flag = true;
                    }

                    //case 3-3-2: 오른쪽 subTree의 node 개수가 더 많을때\\
                    else
                    {
                        p = findMinNode(temp.right);
                        flag = false;
                    }
                }

                temp.data = p.data;

                if(flag) {temp.left = deleteBST(temp.left, p.data);}
                else {temp.right = deleteBST(temp.right, p.data);}
            }
        }
        return temp;
    }

    private int getHeight(Node temp)
    {
        if(temp == null) {return -1;}

        int leftSubTreeHeight = getHeight(temp.left) + 1;
        int rightSubTreeHegiht = getHeight(temp.right) + 1;

        return leftSubTreeHeight > rightSubTreeHegiht ? leftSubTreeHeight : rightSubTreeHegiht;
    }

    private int getNumofNode(Node temp)
    {
        if(temp == null) {return -1;}

        int leftSubTreeHeight = getHeight(temp.left) + 1;
        int rightSubTreeHegiht = getHeight(temp.right) + 1;

        return leftSubTreeHeight + rightSubTreeHegiht + 1;
    }

    private Node findMaxNode(Node temp)
    {
        if(temp.right == null) {return temp;}
        else {return findMaxNode(temp.right);}
    }

    private Node findMinNode(Node temp)
    {
        if(temp.left == null) {return temp;}
        else {return findMinNode(temp.left);}
    }

    public void print()
    {
        if(this.isEmpty()) {System.out.println("Tree is empty");}
        else {inorder(this.root); System.out.println();}
    }

    private void inorder(Node temp)
    {
        if (temp != null)
        {
            inorder(temp.left);
            System.out.print(temp.data+" ");
            inorder(temp.right);
        }
    }

    public static void main(String[] args)
    {

        int[] data = { 25, 500, 33, 49, 17, 403, 29, 105, 39, 66,
                305, 44, 19, 441, 390, 12, 81, 50, 100, 999 };

        BST bst = new BST();

        System.out.println("데이터 삽입");
        for (int i = 0; i < data.length; i++)
        {
            bst.insert(data[i]);
            bst.print();
        }

        System.out.println("데이터 삭제");
        for (int i = 0; i < data.length; i++)
        {
            bst.delete(data[i]);
            bst.print();
        }
    }
}

 

결론

BST는 Tree의 구체적인 개념의 시작이라고 생각한다. 이후에 B트리, B+ Tree, R Tree 같이 엄청나게 복잡한 개념의 트리로 넘어가는 기본적인 Tree구조인것 같다. 그러나 역시 문제점이 있는데 위에서 삭제 메소드를 설명했듯이 삽입시에 편향되게 삽입하면 그냥 선형 자료구조를 사용하는 거나 다름없이 효율성 문제에서 하자를 띄게 된다. 이를 보완한 것이 AVL트리인데, 이는 다음에 포스팅하기로 한다....

BST는 대학교에서 Tree를 구현할때 아마 제일 먼저 구현하는 자료구조일거 같은데, Linked List를 완벽히 이해하고 Node의 구조와 이동하는 그 메커니즘을 이해 한다면 쉽게 구현할 수 있다.

다음 포스팅은 BST의 균형문제를 해결한 AVL이 될것같다.

 

틀린부분이나 궁금한 부분이 있다면, 댓글을 남겨주세요!!~!