12_트리

• 용어

       - 루트(root): 가장 윗부분에 위치하는 노드. 하나의 트리에는 하나의 루트가 있음

       - 리프(leaf): 트리의 가장 아랫부분에 위치하는 노드 

       - 레벨(level): 루트로부터 얼마나 떨어져 있는지에 대한 값 (루트의 레벨은 0)

       - 차수(degree): 노드가 갖는 자식의 수. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다.

       - 높이(height): 루트로부터 가장 멀리 떨어진 리프까지의 거리 (리프 레벨의 최댓값)

• 너비 우선 탐색(BFS): 낮은 레벨에서 시작해서 왼쪽 → 오른쪽 방향으로 검색
• 깊이 우선 탐색(DFS): 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법
• 전위 순회(Preorder): 노드 방문 → 왼쪽 자식 → 오른쪽 자식
• 중위 순회(Inorder): 왼쪽 자식 → 노드 방문 → 오른쪽 자식
• 후위 순회(Postorder): 왼쪽 자식 → 오른쪽 자식 → 노드 방문
• 이진트리(binary tree): 각 노드의 자식은 2명 이하만 유지
• 완전이진트리(complete binary tree): 루트부터 노드가 채워져 있으면서, 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리 (마지막 레벨은 반드시 끝까지 채울 필요는 없음. 마지막 레벨 제외 노드 가득 채움)

 

 

• 이진검색트리(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;    // 비교자
    
    // 생성자1: 비어 있는 이진검색트리 생성, 자연 순서에 따라 키 값을 비교
    //-- K 타입이 Comparable() 구현하고 있는 Integer, String... 등에 알맞음!
    public BinTree() {
        root = null;
    }
    
    // 생성자2: 비어 있는 이진검색트리 생성, 비교자로 키 값을 비교
    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, key2);
    }
    
    // 키에 의한 검색
    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();
            // key가 작으면 왼쪽 서브 트리로 
            else if (cond < 0)
                p = p.left;
            // key가 크면 오른쪽 서브 트리로 
            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는 부모의 왼쪽 자식 노드?
        
        // 삭제할 key 검색
        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) 자식 노드 없는 경우 & 자식 노드 1개인 경우
        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;
            
        // 2) 자식 노드가 2개인 경우
        } else {
            parent = p;
            Node<K,V> left = p.left;    // 서브 트리 가운데 가장 큰 노드 
            isLeftChild = true;
            
            // 가장 큰 노드 left를 검색
            while (left.right != null) {
                parent = left;
                left = left.right;
                isLeftChild = false;
            }
            
            // left의 key, data를 p로 옮김
            p.key = left.key;
            p.data = left.data;
            if (isLeftChild)
                parent.left = left.left;    // left 삭제
            else 
                parent.right = left.left;   // left 삭제
        }
        return true;
    }
    
    // node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력 (재귀메서드)
    private void printSubTree(Node node) {
        if (node != null) {
            printSubTree(node.left);    // 왼쪽 서브 트리를 키 값의 오름차순으로 출력
            System.out.println(node.key + " " + node.data);     // node 출력
            printSubTree(node.right);   // 오른쪽 서브 트리를 키 값의 오름차순으로 출력
        }
    }
    
    // 모든 노드를 키 값의 오름차순으로 출력
    public void print() {
        printSubTree(root);
    }
}