이진 탐색 트리

• 이진 탐색 트리

 이진 탐색 트리는 이진 트리의 한 종류로써 각 노드가 key 값을 가지고 있다. 모든 노드들은 왼쪽 서브트리에 자신보다 작은 key값을 갖고있는 노드들을 포함하고 오른쪽 서브트리에 자신보다 큰 key값을 갖고있는 노드들을 포함한다.

 보통 삽입, 삭제, 검색 등이 O(logN)의 시간복잡도를 갖기 때문에 빠른 정렬, 검색이 가능하다. 또한 중위 순회를 하면 key값의 오름차순으로 노드를 탐색할 수 있다. 단점은 중복 key값을 가질 수 없고 트리가 편향되면  탐색 시간이 늦어진다. (트리가 편향되는 문제를 해결하기 위해 레드-블랙 트리 등의 균형잡힌 이진 탐색 트리가 만들어졌다)

 

• 이진 탐색 트리 구현

 기본적으로 Tree 클래스를 만들고 내부에 Node 클래스를 만들어 구현한다. Node들은 자신의 key값과 left(왼쪽 자식), right(오른쪽 자식)을 갖는다. 필요한 경우 부모 노드인 parent를 만들어 줄 수 있다.

class Tree<K>{

    class Node<K>{
        K key;
        Node<K> left;
        Node<K> right;
        Node(K k)
        {
            key = k;
            left = null;
            right = null;
        }
    }
    Tree(Comparator<? super K> comparator)
    {
        this.comparator = comparator;
        root = null;
    }
    Tree()
    {
        root = null;
    }
    Comparator<? super K> comparator;
    Node<K> root;
}

 여기서 Tree의 변수인 comparator와 root에 대해 알아보면 comparator는 만약 key값의 정렬 기준이 따로 필요한 경우 comparator를 받을 수 있게  만든 것이고 root는 해당 트리의 루트 노드를 의미한다. Tree(Comparator<? super K> comparator) 생성자로 Tree를 만들 때 comparator를 매개변수로 넣을 수 있다. 해당 comparator는 안정성을 높이기 위해 제너릭 K의 상위타입 객체까지 커버가 가능하게 만들었고 만약 매개변수를 넣지 않으면 따로 오버로딩한 Tree() 생성자로 Tree가 만들어지므로 comparator는 초기화 되지 않고 기본값인 null이 된다.

 이제 이 Tree에서 사용할 추가 함수들을 만들어 보자.

 

(1) comp(

 앞으로 구현할 함수들에서 사용할 함수이다. 기본적으로 이진 탐색 트리는 삽입, 검색, 삭제 등을 할 때 노드의 key값을 비교하며 진행하므로 가장  먼저 구현해야할 함수이다.(오름차순으로만 사용할 것이라면 Comparator나 comp함수가 굳이 필요하진 않다.)

int comp(K k1, K k2) 
{
    return (this.comparator == null) ? ((Comparable<K>)k1).compareTo(k2) 
                                     : comparator.compare(k1, k2);
}

 다음과 같이 comp함수가 구현되는데 만약 comparator == null이면 k1을 Comparable로 형변환하여 k1과 k2를 비교하는데 이때는 자동으로 오름차순 비교가 된다. 하지만 만약 따로 comparator를 마련했다면 그 comparator를 기준으로 k1과 k2를 비교한 결과를 반환한다.

 

(2) add

 add는 트리에 노드를 추가하는 함수이다. 단순히 추가하는게 아니라 추가하면서 이진 탐색 트리의 규칙에 맞게 노드를 배치해야한다. 따라서 루트 노드부터 시작해서 해당 노드보다 작으면 왼쪽 서브 트리로 크면 오른쪽 서브 트리로 이동한다. 이동하다가 빈공간을 발견하면 그 자리에 노드가 생성된다.

void  add(K key)
{
    if (root == null)
        root = new Node<>(key);
    else
        add_node(root, key);
}

void add_node(Node<K> node, K key)
{
    int com = comp(key, node.key);
    if (com < 0)
    {
        Node<K> next = node.left;
        if (next == null)
            node.left = new Node<>(key);
        else
            add_node(next, key);
    }
    else if (com > 0)
    {
        Node<K> next =  node.right;
        if (next == null)
            node.right = new Node<>(key);
        else
            add_node(next, key);
    }
}

 먼저 add함수로 들어가 root노드가 없으면 root노드를 생성하고 root노드가 있으면 add_node함수로 들어간다. add_node함수는 현재 판단 대상인 node의 key값과 매개변수로 들어온 key값을 comp 함수로 비교해 다음 행동을 정한다. 만약 매개변수로 들어온 key값이 현재 노드의 key값보다 작으면 next 노드가 현재 노드의 left 노드로 바뀌고, 크면 현재 노드의 right노드로 바뀐다. 만약 next값이 null이면 해당 자리에 노드를 새로 생성하고 노드가 존재하면 그 노드를 매개변수로 add_node 함수를 다시 호출한다. 만약 com == 0이면 Tree에 해당 key값이 이미 존재하므로 노드를 생성하지 않는다.   

 

 

(3) remove

  remove는 add와 반대로 매개변수로 들어온 key값을 갖는 노드를 삭제하는 함수이다. add보다 remove가 더 복잡한데 그 이유는 remove는 노드를 삭제한 후 빈 자리를 이진 탐색 트리의 규칙에 맞게 채워야하기 때문이다. 노드를 삭제하는 경우는 다음과 같이 3가지가 있다.

 

 1) 자식이 없는 노드를 삭제하는 경우

 2) 자식이 1개인 노드를 삭제하는 경우

 3) 자식이 2개인 노드를 삭제하는 경우

 

 1번의 경우는 빈 자리를 채울 필요 없이 삭제만 하면 되고, 2번의 경우에는 노드를 삭제하고 삭제한 노드의 자식을 빈자리에 옮기면 된다. 3번의 경우는 1, 2번에 비해 복잡한데 삭제한 노드의 [왼쪽 서브 트리에서 가장 큰 값]과 [오른쪽 서브 트리에서 가장 작은 값] 중 하나로 빈자리를 채우면 된다. 이번에 구현할 remove에서는 3번의 경우 왼쪽 서브 트리에서 가장 큰 값으로 빈 자리를 채우는 방법을 쓰겠다.

 

remove는 코드가 복잡하므로 큰 그림을 먼저 그리고 코드를 보겠다.

 

1. 매개변수로 받은 key값과 일치하는 Node찾기

 (만약 일치하는 Node가 없다면 종료)

route a : 발견한 Node가 root노드인  경우

2-a1. root = null  - 1)번의 경우

2-a2. root = root.left 또는 root = root.right  - 2)번의 경우

2-a3. root의 왼쪽 서브 트리에서 가장 큰 값을 root로 설정(find_max함수 이용)  - 3)번의 경우

route b : 발견한 Node가 root노드가 아닌 경우

2-b1. Node가 차지하던 Node부모의 자식 자리를 null로 대체 (no_child함수 이용)  - 1)번의 경우

2-b2. Node가 차지하던 Node부모의 자식 자리를 Node.left 또는Node.right로 대체 (one_child함수 이용) - 2)번의 경우

2-b3. Node가 차지하던 Node부모의 자식 자리를 Node의 왼쪽 서브트리에서가장 큰 값으로 대체 (two_child함수 이용)  - 3)번의 경우 

  

이정도 살펴보고 코드를 보고 이해해보자.

    void remove(K key) {
        Node<K> ptr = root;
        Node<K> parent = null;
        // 매개변수 key값과 동일한 key값을 갖는 노드 찾기
        while (ptr != null) {
            int com = comp(key, ptr.key);
            if (com == 0) // 동일한 key값을 갖는 노드 발견!
                break;
            else if (com < 0) {
                parent = ptr;
                ptr = ptr.left;
            } else {
                parent = ptr;
                ptr = ptr.right;
            }
        }
        // 동일한 key값을 갖는 노드를 찾았을 경우만 실행
        if (ptr != null) {
            // route a : 발견한 Node가 root노드인 경우
            if (ptr == root) {
                if (ptr.right == null) {
                    if (ptr.left == null) // 1)번의 경우
                        root = null;
                    else // 2)번의 경우
                        root = ptr.left;
                } else if (ptr.left == null) // 2)번의 경우
                    root = ptr.right;
                else { // 3)번의 경우
                    root = find_max(ptr);
                    root.right = ptr.right;
                    root.left = ptr.left;
                }
            } else {  // route b : 발견한 Node가 root노드가 아닌 경우
                if (ptr.right == null) {
                    if (ptr.left == null) // 1)번의 경우
                        no_child(parent, key);
                    else // 2)번의 경우
                        one_child(parent, ptr, key, 'l');
                } else if (ptr.left == null) // 2)번의 경우
                    one_child(parent, ptr, key, 'r');
                else // 3)번의 경우
                    two_child(parent, ptr, key);
            }
        }
    }

    void no_child(Node<K> parent, K key) {
        if (parent.left.key == key) // 부모의 왼쪽 자식이 ptr인 경우
            parent.left = null;
        else                        // 부모의 오른쪽 자식이 ptr인 경우
            parent.right = null;
    }

    void one_child(Node<K> parent, Node<K> ptr, K key, char c)
    {
        Node<K> child = null;
        if (c == 'l')
            child = ptr.left;
        else
            child = ptr.right;
        if (parent.left.key == key)  // 부모의 왼쪽 자식이 ptr인 경우
            parent.left = child;
        else                         // 부모의 오른쪽 자식이 ptr인 경우
            parent.right = child;
    }
    void two_child(Node<K> parent, Node<K> ptr, K key)
    {
        Node<K> child = find_max(ptr);
        if (parent.left.key == key)  // 부모의 왼쪽 자식이 ptr인 경우
            parent.left = child;
        else                         // 부모의 오른쪽 자식이 ptr인 경우
            parent.right = child;
        child.left = ptr.left;
        child.right = ptr.right;
    }
    
    // 왼쪽 서브 트리에서 가장 큰 값을 찾는 함수 
    Node<K> find_max(Node<K> ptr) { 
        Node<K> child = ptr.left;
        Node<K> parent = ptr;
        boolean check = false;
        while (child.right != null) {
            parent = child;
            child = child.right;
        }
        // 빠져나갈 Node의 자리를 채우는 과정
        if (check) {
            if (child.left != null)
                parent.right = child.left;
            else
                parent.right = null;
        }
        else
        {
            if (child.left != null)
                parent.left = child.left;
            else
                parent.left = null;
        }
        return child;
    }
}

위에서 설명한 내용들을 그대로 코드로 쓴 것이다. 추가로알아야 할 점은 3)번의 경우 왼쪽 서브 트리에서 가장 큰 값을 찾는 함수인 find_max함수에서 가장 큰 key값을 갖는 Node를 찾고 빼가야하기 때문에 그 빈자리를 채워주는 과정이 필요하다. 따라서 주석으로 달아 놓은 것처럼 해당 Node의 자식이 있으면 부모에게 붙여주고 없으면 부모의 자식 자리에 null을 넣어준다.

 

(4) contains

 contains 함수는 말 그대로 매개변수로 주어진 key값이 Tree에 존재하면 true 없으면 false를 반환하는 함수이다. remove에서 매개변수 key값과 같은 key값을 갖는 Node를 탐색하던 것처럼 똑같이 찾으면 된다. 오히려 parent를 고려하지 않으니 코드가 더 쉽게 만들어 진다.

boolean contains(K key)
{
    Node<K> ptr = root;
    while (ptr != null) {
        int com = comp(key, ptr.key);
        if (com == 0)
            return true;
        else if (com < 0)
            ptr = ptr.left;
        else
            ptr = ptr.right;
    }
    return false;
}

ptr을 root로 설정하고 Tree를 타고 내려가면서 탐색을 한다. 만약 같은 key값을 갖는 Node를 찾으면 true를 반환하고, 못 찾으면 ptr이 null이 돼서 while문을 빠져나오고 false를 리턴한다.

 

(5) inorder

 마지막으로 inorder함수를 보자. inorder는 중위순회로도 불리며 왼쪽 서브 트리 -> root -> 오른쪽 서브 트리 순으로 노드를 탐색하는 방법이다. 위에서도 말했듯이 inorder방법으로 Tree의 key값을 읽으면 오름차순으로 읽을 수 있다. 코드를 보면 재귀를 통해 inorder를 수행하고 있는 것을 알 수 있다.

void inorder() {
    rec_inorder(root);
}

void rec_inorder(Node<K> node)
{
    if (node != null) {
        rec_inorder(node.left);
        System.out.println(node);
        rec_inorder(node.right);
    }
}

inorder함수에서 rec_inorder의 시작점인 root노드를 넣어준다. 그러면 rec_inorder는 node != null이면 왼쪽 자식을 방문하고 root노드를 출력하고 오른쪽 자식을 방문한다.

 

 처음 이진 탐색 트리를 직접 구현해봤는데 지금까지 구현한 어떤 자료구조보다 힘들었던것 같다. 다른 함수들은 괜찮았지만 remove 함수가 굉장히 힘들었다. 그래도 직접 구현을 해보고 배운다는 것이 중요하다 생각하므로 공부는 많이 됐다고 생각한다.