이진검색트리

트리란?

• 데이터 사이의 계층 관계를 나타내는 자료구조
• 모든 노드가 가지는 자식 노드 수가 n 이하인 트리를 n진 트리라고 한다.
  • 모든 노드의 자식 수가 2개 이하인 경우는 특별히 이진 트리라고 한다.
• 형제 노드의 순서를 따지면 순서 트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)라고 한다.
  • 순서 트리의 노드를 스캔하는 방법은 너비 우선 탐색과 깊이 우선 탐색이 있다.

너비 우선 탐색

• 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려가는 탐색 방법

깊이 우선 탐색

• 리프까지 내려가면서 검색하는 것은 우선순위로 하는 탐색 방법
• 언제 노드를 방문할지에 따라 세 종류로 구분한다.
  • 전위 순회(Preorder) : 노드 방문 → 왼쪽 자식 → 오른쪽 자식
  • 중위 순회(Inorder) : 왼쪽 자식 → 노드 방문 → 오른쪽 자식
  • 후위 순회(Postorder) : 왼쪽 자식 → 오른쪽 자식 → (돌아와) 노드 방문

이진트리

• 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다.
• 각 노드의 자식은 2개 이하만 유지해야 한다.
• 이진트리는 왼쪽 자식과 오른쪽 자식을 구분한다.
• 왼쪽 자식을 다시 루트로 하는 서브 트리를 왼쪽 서브 트리(left tree), 오른쪽 자식을 다시 루트로 하는 서브 트리를 오른쪽 서브 트리(right tree)라고 한다.

완전이진트리

• 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리(complete binary tree)라고 한다.
  1. 마지막 레벨을 제외한 레벨은 노드를 가득 채운다.
  2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 끝까지 채울 필요는 없다.

이진검색트리

• 이진검색트리(binary search tree)의 조건은 다음과 같다.
  1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
  2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
  3. 같은 키 값을 갖는 노드는 없다.
• 이진검색트리를 중위 순회하면 키 값의 오름차순으로 노드를 얻을 수 있다.
• 구조가 단순하다.
• 이진검색과 비슷한 방식으로 검색이 가능하다.
• 노드의 삽입이 쉽다.

//이진검색트리
 
public class BinTree<K, V> {
 
    //노드
    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 data, 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;                            //루트
    private Comparator<? super K> comparator = null;    //비교자
    
    //노드의 키 값을 비교할 때 자연 순서에 따라 비교
    //K의 타입이 Comparable 인터페이스를 구현하고 있는 Integer 클래스나 String 클래스 등에 알맞음
    public BinTree() {
        root = null;    //비어 있는 이진검색트리를 생성한다
    }
    
    //노드의 키 값을 비교할 때 전달받은 비교자로 비교
    public BinTree(Comparator<? super K> c) {
        this();
        comparator = c;
    }
    
    //두 키 값을 비교
    private int comp(K key1, K key2) {
        return (comparator == null) ? ((Comparable<K>) key1).compareTo(key2) : comparator.compare(key1, key1);
    }
    
    //키 값으로 검색
    //루트부터 시작해 현재 선택한 노드의 키 값과 목표하는 값을 비교하면서 왼쪽, 오른쪽으로 검색을 진행한다
    public V search(K key) {
        Node<K, V> p = root;        //루트에 주목
        
        while (true) {
            if (p == null) {        //더 이상 진행하지 않으면
                return null;        //검색 실패
            }
            int cond = comp(key, p.getKey());
            if (cond == 0) {
                return p.getValue();
            } else if (cond < 0) {
                p = p.left;
            } else {
                p = p.right;
            }
        }
    }
    
    //node를 루트로하는 서브 트리에 노드<k, V>를 삽입
    private void addNode(Node<K, V> node, K key, V data) {
        int cond = comp(key, node.getKey());
        if (cond == 0) {
            return;                    //같은 key가 이진검색트리에 이미 있음
        } else if (cond < 0) {
            if (node.left == null) {
                node.left = new Node<K, V>(key, data, null, null);
            } else {
                addNode(node.left, 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);
        }
    }
    
    //키 값이 key인 노드를 삭제
    public boolean remove(K key) {
        Node<K, V> p = root;             //스캔 중인 노드
        Node<K, V> parent = null;         //스캔 중인 노드의 부모 노드
        boolean isLeftChild = true;       //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;
                }
            }
        }
        
        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) {    //가장 큰 노드 left를 검색    
                parent = left;
                left = left.right;
                isLeftChild = false;
            }
            p.key = left.key;                //left의 키 값을 p로 옮김
            p.data = left.data;              //left의 데이터를 p로 옮김
            if (isLeftChild) {
                parent.left = left.left;
            } else {
                parent.right = left.left;
            }
        }
        return true;
    }
    
    //node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력(중위 순회)
    private void printSubTree(Node node) {
        if (node != null) {
            printSubTree(node.left);
            System.out.println(node.key + " " + node.data);
            printSubTree(node.right);
        }
    }
    
    //모든 노드를 키 값의 오름차순으로 출력
    public void print() {
        printSubTree(root);
    }
    
    //node를 뿌리로 하는 서브 트리의 노드를 키 값의 내림차순으로 출력
    private void printSubTreeR(Node node) {
        if (node != null) {
            printSubTreeR(node.right);
            System.out.println(node.key + " " + node.data);
            printSubTreeR(node.left);
        }
    }
    
    //모든 노드를 키 값의 내림차순으로 출력
    public void printReverse() {
        printSubTreeR(root);
    }
    
    //최소 key의 값을 갖는 노드를 반환
    private Node<K, V> getMinNode() {
        if (root == null) {
            return null;
        } else {
            Node<K, V> p = root;
            
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
    }
    
    //최대 key의 값을 갖는 노드를 반환
    private Node<K, V> getMaxNode() {
        if (root == null) {
            return null;
        } else {
            Node<K, V> p = root;
            
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
    }
    
    //가장 작은 키 값을 반환
    public K getMinKey() {
        Node<K, V> minNode = getMinNode();
        return minNode == null ? null : minNode.getKey();
    }
    
    //가장 작은 키 값을 갖는 노드의 데이터를 반환
    public V getDataWithMinKey() {
        Node<K, V> minNode = getMinNode();
        return minNode == null ? null : minNode.getValue();
    }
    
    //가장 큰 키 값을 반환
    public K getMaxKey() {
        Node<K, V> maxNode = getMaxNode();
        return maxNode == null ? null : maxNode.getKey();
    }
    
    //가장 큰 키 값을 갖는 노드의 데이터를 반환
    public V getDataWithMaxKey() {
        Node<K, V> maxNode = getMaxNode();
        return maxNode == null ? null : maxNode.getValue();
    }
}