kingsubin

트리 (tree)

• 자료구조의 일종
• 사이클이 없는 연결 그래프
• 정점의 개수 : V
• 간선의 개수 : V-1
  • 정점 V, 간선 V 개 라면 사이클이 1개 있다.
• 정점 V, 간선 V-1 개라면 트리라 할 수 있을까 ? 아니다.
• 왜냐면 연결이 되어있지 않다.
• 정점 V, 간선 V-1 개 라는것은 트리의 성질이다.
• 트리가 맞을려면 연결되어있다는 조건이 추가되어야 한다.

 

트리를 구성하는 요소

- node 

- edge

 

root

- 트리의 가장 윗부분에 위치하는 노드

- 하나의 트리에는 하나의 루트가 존재

 

reaf (terminal node, external node)

- 트리의 가장 아랫부분에 위치하는 노드

- 더 이상 뻗어나갈 수 없는 마지막 노드

 

Parent

- Parent가 없는 V를 Root라고 할 수 있다.

 

Chileren

 

Sibiling

- 같은 부모를 가지면 형제

 

Ancestor, Descendent

- 조상의 정의에는 자신이 포함된다.

- 자손의 정의에는 자신이 포함된다.

 

level

- 루트로부터 얼마나 떨어져 있는지에 대한 값

- 루트의 레벨은 0이고 가지가 하나씩 뻗어나갈 때마다 레벨이 1씩 늘어난다.

 

depth

- 루트에서 현재 노드 사이의 간선 개수 

 

height

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

 

degree 

- 노드가 갖는 자식의 수

- 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다.

- 모든 노드의 자식 수가 2개 이하인 경우에는 특별히 이진트리라고 한다.

 

Rooted Tree

- 루트가 있는 트리

- 루트는 정하기 나름, 있을수도 없을수도 있다.

 

ordered tree, unorered tree

- 형제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류한다.

- 형제 노드의 순서를 따지면 ordered tree, 따지지 않으면 unorered tree

 

-> 순서 트리로 보면 다른 트리지만 무순서 트리로 보면 같은 트리라고 할 수 있다.

 

 

이진트리 (Binary Tree)

 

binary tree (이진트리)

- 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리 (binary tree) 라고 한다.

- 각 노드의 자식은 2명 이하만 유지해야 한다.

 

Perfect Binary Tree

- Leaf Node 를 제외한 노드의 자식의 수는 2개

- Leaf Node 의 자식의 수 0개

- 모든 Leaf Node 의 깊이가 같아야한다.

- 높이가 h인 트리의 노드 개수 = 2^h -1 

 

complete binary tree (완전이진트리)

- Perfect Binary Tree 의 마지막 레벨에서 오른쪽 일부가 사라진 트리

- 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라 한다.

- 높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^k+1 -1 개이다.

- 따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n이다.

 

binary search tree (이진검색트리)

- 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야한다.

- 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.

- 같은 키 값을 갖는 노드는 없다.

 

 

 

- 이진검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있다는 점, 구조가 단순하다는 점,

  이진검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이 쉽다는 점등의 특징이 있어 폭넓게 사용된다.

 

---

트리의 표현

- 그래프의 표현과 같은 방식으로 저장할 수 있다.

 

1. 트리의 부모만 저장하는 방식 

- 각 노드의 부모만 저장한다. 

- 루트는 부모가 없다.

# Union-Find

부모를 한 번에 찾을 수 있지만 자식을 찾는데는 오래 걸린다.

 

2. 완전 이진트리의 경우에는 배열로 표현할 수 있다. 

- 부모의 노드가 x 인 경우 자식의 노드는 2*x, 2*x + 1로 나타내면 된다.

- 구조체나 클래스를 이용할 수도 있다

# Heap, Segment Tree

완전이진트리만 사용할 수 있다.

 

---

트리의 순회

• 어떤 의미를 가지고 있는지가 중요하다.
• DFS, BFS 모두 가능 
• DFS 는 3가지 출력 순서가 있다.
• 세 방문의 차이는 노드 방문 처리를 언제 할 것인가 이다.
• PRE-ORDER (전위순회)
  • 그래프의 DFS 순서와 같다. 
    • 노드 방문
    • 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더
    • 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더
• IN-ORDER (중위순회)
  • 별로 쓸 일 없고 BST 에서 삭제를 구현할때 이용한다.
  • 이진트리가 아니면 정의되지 않는다.
    • 왼쪽 자식 노드를 루트로 하는 서브 트리 인오더
    • 노드 방문
    • 오른쪽 자식 노드를 루트로 하는 서브 트리 인오더
• POST-ORDER (후위순회)
  • 제일 많이 사용하는 방식
    • 왼쪽 자식 노드를 루트로 하는 서브 트리 후위순회
    • 오른쪽 자식 노드를 루트로 하는 서브 트리 후위순회
    • 노드 방문

 

---

트리의 탐색

• 트리의 탐색은 BFS/DFS 를 이용해서 할 수 있다.
• 트리는 사이클이 없는 그래프이기 때문에 임의의 두 정점 사이의 경로는 1개이다.
• 경로가 1개 보다 많다면 그것은 트리가 아니다.
• 경로가 1개이기에 찾으면 그 경로가 최단경로이다.

 

---

트리의 지름

• 트리에 존재하는 모든 경로 중에서 가장 긴 것을 트리의 지름이라고 한다.
• 트리의 지름은 탐색 2번으로 구할 수 있다.
  
  • 1. 한 정점 s에서 모든 정점까지의 거리를 구한다. 이때 가장 먼 거리의 정점을 u 라고 한다.
  • 2. u에서 모든 정점까지의 거리를 구한다. 이때 가장 먼 거리의 정점 v를 구한다.
• 이때 u와 v 사이의 거리를 트리의 지름이다.

 

---

import java.util.Comparator;

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;

    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, 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();
            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;
        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;

        // 검색
        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개인 경우
        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 {
            // 자식 노드가 2개인 경우
            parent = p;
            Node<K,V> left = p.left;
            isLeftChild = true;
            while (left.right != null) {
                parent = left;
                left = left.right;
                isLeftChild = false;
            }
            p.key  = left.key;
            p.data = left.data;
            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);
    }
}

 

---

---

- 20.12.12 추가