[자료구조] 이진검색트리, Binary Search Tree

이진 검색 트리 (Binary Search Tree)

임의의 이진검색트리의 노드 N은 다음 조건을 만족한다.

- 노드 N의 왼쪽 서브 트리의 모든 키 값은 N보다 작다.
- 노드 N의 오른쪽 서브 트리의 모든 키 값은 N보다 작다.
- 같은 키 값을 갖는 노드는 없다.

Binary Search Tree의 예시

이때, 이진검색트리를 중위순회(Inorder)하면 다음과 같이 키 값의 오름차순으로 노드를 얻을 수 있다.

1 - 4 - 5 - 6 - 7 - 9 - 11 - 12 - 13 - 14 - 15 - 18

 

이렇게 중위 순회를 하면 키 값을 오름차순으로 노드를 얻을 수 있다는 점과 구조가 단순하다는 점, 이진 검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이 쉽다는 점 등의 특징이 있어 폭넓게 사용된다.

 

 이진검색트리 구현

 

package data_structure;

import java.util.Comparator;

/*
* < 이진검색트리 구현 >
*  이진검색트리는 임의의 노드 N에 대하여 다음 조건을 만족한다.
*   - 노드 N의 왼쪽 서브 트리의 모든 키 값은 N보다 작다.
*   - 노드 N의 오른쪽 서브 트리의 모든 키 값은 N보다 작다.
*   - 같은 키 값을 갖는 노드는 없다.
* */
public class BinarySearchTree<K,V> {
    // 1. Node 클래스, 이진검색트리를 구성하는 노드 (key, value, left(왼쪽 자식의 참조 값), right(오른쪽 자식의 참조 값))
    static class Node<K,V> {
        private K key; //키 값
        private V data; // 데이터
        private Node<K,V> left; // 왼쪽 자식 노드
        private Node<K,V> right; // 오른쪽 자식 노드

        //생성자
        Node(K key, V value, Node<K,V> left, Node<K,V> right){
            this.key = key;
            this.data = data;
            this.left = left;
            this.right = right;
        }

        K getKey(){
            return key;
        }

        V getValue(){
            return data;
        }

        void print(){
            System.out.println(data);
        }
    }

    private Node<K,V> root; // 루트에 대한 참조를 보존, 유지하는 필드, 트리가 비어 있는 경우 루트도 없으므로, 값은 null이다.
    private Comparator<? super K> comparator = null; // 키 값의 대소 관계를 비교하는 비교자

    // <생성자>
    // 1. 루트에 대한 참조인 root를 null로 하여 노드가 하나도 없는(비어 있는) 이진검색트리를 생성하는 생성자이다.
    public BinarySearchTree(){
        root = null; // 어떠한 노드도 가리키지 않는 것.
    }

    // 2. 인수로 비교자를 전달받는 생성자이다.
    public BinarySearchTree(Comparator<? super K> c) {
        this(); // BinarySearchTree() 호출, 즉 root가 null인 이진검색트리를 생성
        comparator = c; //필드 comparator에 전달받은 c를 설정한다.
    }

    // <메서드>
    // 1. 두 키 값을 비교
    // key1 > key2 : 양수, key1 < key2 : 음수, key1 == key2 : 0
    private int comp(K key1, K key2){
        // compareTo는 인터페이스 Comparable<K>에 있는 추상메서드이다. 따라서, 사용 시 Comparable로 캐스팅을 해줘야 함.
        return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2)
                                : comparator.compare(key1, key2);
    }

    // 2. 키에 의한 검색
    // 루트 선택 -> 값이 크면 왼쪽, 값이 작으면 오른쪽으로 이동 -> 왼쪽에서 오른쪽 순으로 검색 진행
    public V search(K key){
        Node<K,V> p = root; //null or key값의 참조값

        while(true){
            //root인 p가 null 이면 검색 실패
            if (p == null) {
                return null;
            }

            // comp() : 비교 대상의 key값과 루트의 key을 비교.
            // 양수이면 비교대상이 크니까 오른쪽으로,
            // 음수이면 왼쪽,
            // 0이면 같다는거니까 검색 성공
            int cond = comp(key, p.getKey());
            if(cond == 0){
                return p.getValue();
            }else if(cond > 0){
                p = p.right; // 오른쪽 서브트리의 검색 진행. 따라서 root의 포인터를 왼쪽자식으로 이동.
            }else {
                p = p.left; // 왼쪽 서브트리의 검색 진행.
            }
        }

    }


    // 3. 노드를 삽입하는 메서드 addNode, add
    // node를 루트로 하는 서브 트리에 노드<K,V>를 삽입
    private void addNode(Node<K,V> node, K key, V data){
        int cond = comp(key, node.getKey());
        if (cond == 0) {
            return; // 노드를 삽입하려는데 같은 키 값이 있기때문에 들어갈 수 없다.
        }else if(cond < 0){ // 루트보다 작음 -> 왼쪽으로 이동
            if(node.left == null){
                node.left = new Node<K,V>(key, data, null, null);
            }else {
                addNode(node.right, key, data);
            }
        }else {
            if(node.right == null){
                node.right = new Node<K,V>(key, data, null, null);
            }else {
                addNode(node.right, key, data);
            }
        }
    }

    //노드 삽입
    public void add(K key, V data){
        if(root == null){
            root = new Node<K,V>(key, data, null, null);
        }else{
            addNode(root, key, data);
        }
    }

    // 4. 노드를 삭제하는 remove 메서드
    // 노드를 삭제하는 것은 세가지 경우가 있다.
    // - 1 자식 노드가 없는 노드N을 삭제 : N이 부모노드의 왼쪽인지 오른쪽인지 알아낸 후, 해당하는 방향의 부모노드의 포인터를 null로 만들면 됌.
    // - 2 자식 노드가 1개인 노드N을 삭제 : 삭제할 대상이 왼쪽이라면 자신의 자식을 왼쪽포인터에 넣는다. 오른쪽도 마찬가지
    // - 3 자식 노드가 2개인 노드N을 삭제 : 삭제할 대상의 왼쪽 서브트리에서 제일 큰 키값을 구한다(N이라고 하면). 그 키값을 삭제할 대상의 자리로 복사한 후, N을 1번과 2번의 경우에 해당하는대로 처리한다.

    //키 값이 key인 노드를 삭제
    public boolean remove(K key){
        Node<K,V> p = root; // 스캔 중인 노드
        Node<K,V> parent = null; // 스캔 중이 노드의 부모 노드
        boolean isLeftChild = true; // p는 부모의 왼쪽 자식 노드인가?

        // 검색하려는 대상을 p에 담는 작업
        while(true){
            if(p == null){
                return false;
            }
            int cond = comp(key, p.getKey());
            if(cond == 0) break;
            else {
                parent = p;
                if(cond < 0){
                    isLeftChild = true;
                    p = p.left;
                } else {
                    isLeftChild = false;
                    p = p.right;
                }
            }
        }

        //자식이 1개 있는 경우(오른쪽인지, 왼쪽인지), 자식이 2개 있는 경우
        if(p.left == null){
            if(p == root){
                root = p.right;
            }else if(isLeftChild){
                parent.left = p.right;
            }else {
                parent.right = p.right;
            }
        }else if(p.right == null) {
            if(p == root){
                root = p.left;
            }else if(isLeftChild){
                parent.left = p.left;
            }else {
                parent.right = p.left;
            }
        }else {
            parent = p;
            Node<K,V> left = p.left;
            isLeftChild = true;

            while(left.right != null){
                parent = left;
                left = left.right;
                isLeftChild = false;
            }

            // right자식이 없는 노드가 left에 담김.
            p.key = left.key;
            p.data = left.data;
            if(isLeftChild){
                parent.left = left.left;
            }else {
                parent.right = left.left;
            }
        }
        return true;
    }
}