트리와 그래프

트리 와 그래프

---

1. 트리

   • 트리 참고
   • 
   • 
     
   • 개념:
     • 차수(degree): 하나의 node 의 child node 의 수, 트리의 차수는 최대 child node 의 수
     • 레벨(level):
       • A node = 1
       • B node = 2
       • D node = 3

   • Left Child-Right Sibling 표현법:

     • 왼쪽에 child node , 오른쪽에 sibling node (형제노드)
     • 
     • 
       
     • JAVA 구현

     •   class TreeNode {
             int index;
             boolean isRootNode;
             TreeNode[] childNode;
       
             boolean hasChild(){
                 if (childNode == null || childNode.length() == 0){
                     return true;
                 }else{
                     return false;
                 }
             }
       
             void appendChild(TreeNode insertNode){
                 // childNode 가 없다면
                 if (childNode == null){
                     childNode = new TreeNode[](1);
                     childNode[0] = insertNode;
                 }
                 // 기존의 childNode 가 존재한다면
                 else {
                     TreeNode[] newChildNode = Arrays.copyOf(childNode, childNode.length() + 1);
                     newChildNode[newChildNode.length()-1] = insertNode;
                     childNode = newChildNode;
                 }
             }
         }
       

2. 그래프

   • 그래프 참고
   • 그래프 참고2
   • 정의: 현실세계의 사물이나 추상적인 개념 간의 연결 관계를 표현
     ex) 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계
   • 구성요소: G(V, E): 그래프는 Vertex와 Edge들의 집합
     • 정점 (Node, Vertex)
     • 간선 (Edge): 정점간의 관계 나타냄 (비용, 개수 등등)
   • 종류:
     • 유향 그래프: 그래프에 방향이 있는 그래프
     • 가중치 그래프: 간선에 가중치가 있는 그래프 ex) 정점 이동간에 드는 비용
     • 다중 그래프: 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프 ex) 도로망
     • 트리 혹은 루트 없는 트리: 부모 자식 관계가 없을 뿐, 간선들의 연결 관계만 보면 트리와 같은 무향 그래프
     • DAG(Directed acyclic graph): 한 점에서 출발해 자기 자신으로 돌아오는 경로가 존재하지 않는 방향 그래프, 위 그림에서 무향일 경우에는 cycle이 존재할 수 있음

3. 이진 트리

   • 이진 트리
     • 정의:
       • 한 노드가 최대 두 개의 자식 노드를 가지는 트리
     • 속성 값 정의:
       • 방향 간선(directed edge): 부모에서 자식으로 가는 경로를 가리킨다
       • 루트 노드(root node): 부모가 없는 노드 로, 트리는 하나의 루트 노드만을 가진다
       • 단말 노드(leaf node): 자식이 없는 노드
       • 노드의 깊이(depth): 루트 노드에서 자신까지 가는 경로의 길이 == 레벨(level) 과 비슷
         • 루트 노드의 깊이: 0
       • 트리의 높이(height): 루트 노드에서 가장 깊이 있는 노드까지 가는 경로의 길이
       • 형제(sibling)은 같은 부모를 가지는 노드
       • 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
       • 노드의 진입차수(In-degree): 노드에 들어오는 모든 간선의 수
       • 노드의 진출차수(Out-degree)는 노드에서 나가는 모든 간선의 수
     • 종류:
       • 루트를 가진 이진 트리(rooted binary tree): 모든 노드의 자식이 최대 2개인 트리
       • 정 이진 트리(full binary tree): 단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리
       • 포화 이진 트리(perfect binary tree): 모든 단말 노드의 깊이가 같은 정 이진 트리
       • 완전 이진 트리(complete binary tree): 끝 부분(마지막 레벨)을 제외하고 모든 노드가 채워진(마지막 레벨을 제외하고는 모든 노드가 자식노드를 2개를 가진) 이진 트리. 마지막 레벨의 노드들은 왼쪽으로 채워져 있다. 마지막 레벨이 다 채워질 수도 있다.
     • 이진 트리 탐색
       • 정의: 이진 트리의 모든 노드를 방문하는 것 혹은 방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 한다
       • 속성:
         • 각 노드에 값이 있다
         • 각 노드의 키값은 모두 달라야 한다
         • 값들은 전순서가 있다
         • 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다
         • 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다
         • 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다
         • 중복된 노드가 없어야 한다
       • 방법:
         • in-order : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문
         • pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문
         • post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문
         • level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, … , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)
       • 특징:
         • 데이터의 이동이 많은 동적인 데이터들의 집합에 적합한 탐색 방법
         • VS 배열을 이용한 이진탐색: 수행속도는 빠르나 데이터의 삽입과 삭제가 일어날 때, 배열 내의 데이터들을 이동해야하는 문제점이 있음
         • 트리 구조를 이용하여 데이터의 삽입과 삭제가 필요할 때, 전체적인 데이터의 이동이 없이 포인터만 연결 시켜주면서 간단하게 해결

4. 문제풀이

   • 균형 이진 트리 란: 단말 노드 간의 depth 차이가 1 이하 인 이진트리 찾기

   • 단순 구현

       class Node {
           int index;
           Node leftChild;
           Node rightChild;
     
           boolean isLeafNode(){
               if(leftChild == null && rightChild == null){
                   return true;
               }else{
                   return false;
               }
           }
     
       }
     
       public NodeTest{
     
           Node [] tree;
     
           //TODO 구현 필요
           int getLevel(Node[]tree, Node){
               return 0;
           }
     
           // DFS 구현 필요
     
           public static void main(String[]args){
     
               int minLeafNodeLevel = tree.size();
               int maxLeafNodeLevel = -1;
     
               for (Node singleNode : tree){
                   if( singleNode.isLeafNode() ){
     
                       int level = getLevel(singleNode);
     
                       if (level > maxLeafNodeLevel){
                           level = maxLeafNodeLevel;
                       }else if (level < minLeafNodeLevel){
                           level = minLeafNodeLevel;
                       }
                   }
     
               }
     
               if((maxLeafNodeLevel - minLeafNodeLevel) <= 1){
                   System.out.println("균형 이진 트리");
               }else{
                   System.out.println("균형 이진 트리 아님");
               }
     
           }
       }