[Algorithm] 트리 Tree

[Algorithm] 트리 Tree

 

트리란?

트리란 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이때 각 노드는 재사용 되지 않는 구조이다. 말로 풀어내면 복잡할 수 있는데 그림으로 보면 한눈에 이해가 간다.

---

트리와 관련된 용어

• 노드 node: 트리는 노드들의 집합으로 트리를 구성하는 것으로 보통 값과 부모 자식의 정보를 가지고 있다.
• 엣지/간선 edge: 엣지는 노드들을 연결하는 간선으로 부모 노드와 자식 노드를 연결하게 된다.
• 루트 노드 root node: 가장 상위 노드로 부모를 가지지 않는다.
• 리프 노드 leaf node: 가장 하위 노드로 자식을 가지지 않는다.
• 형제 노드 sibling node: 같은 부모를 가지는 자식 노드들을 말한다.
• 노드의 깊이 depth: 트리에서 부모에서 자식순으로 이동할 때, depth가 1 증가하며 따라서 형제 노드 간의 depth는 일치하며 root node의 depth는 0이 된다.
• 노드의 크기 size: 자신을 포함한 모든 자손 노드들의 개수를 말한다.
• 노드의 레벨 level: 트리의 특정 깊이를 가지는 노드의 집합을 말한다.
• 노드의 차수 degree: 하위 트리 개수 / 엣지 수
• 트리의 차수 degree of tree: 트리의 최대 차수를 말한다.
• 트리의 높이 height: 루트 노드에서 가장 깊숙히 있는 노드의 깊이를 말한다.

---

트리의 특징

• 그래프의 한 종류
  • DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류
    • 사이클이 없다.
• 계층 모델이다.
  • 사용: pc나 모바일 핸드폰의 파일 구조
• 노드가 N개의 트리는 항상 N-1개의 엣지를 가진다.
• 두개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한개의 루트 노드만이 존재하며 모든 자식 노드는 한개의 부모 노드만을 가진다.
  • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
• 순회는 Pre-order, In-order, Post-order로 이루어진다.

---

트리의 종류

이진 트리(binary-tree) vs 이진 트리가 아닌 트리(non-binary-tree)

1. 이진 트리가 아닌 트리 Non-binary-tree
   • 노드의 자식 개수에 대한 제한이 없는 트리
   • 대표적인 예: 트라이(trie)
2. 이진 트리 Binary-tree
   • 노드의 자식 개수가 2개 이하인 트리
   • 이진 트리 순회
     • 중위 순회(in-order traversal): 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지
     • 전위 순회(pre-order traversal): 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
     • 후위 순회(post-order traversal): 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
   • 이진 검색 트리 Binary-search-tree (BST)

     

      
     • 각 노드는 left subtree와 right subtree의 루트를 자식으로 가지며 이때 왼쪽 서브트리는 자신보다 작은 값을 오른쪽 서브트리는 자신보다 큰 값을 가진다.
     • 자료 입력, 삭제, 탐색 모두 시간복잡도가 O(log N) 이다.
   • BST에서 만약 주어진 데이터셋이 증가수열의 형태라고 생각해보자. 1-2-3-4... 이와 같이 길게 늘어진 형태가 되서 탐색에 걸리는 시간도 O(N)이 된다. 만약에 이렇게 길게 늘어진 트리의 중간에 있는 노드를 루트로 잡고 접는다면? 그럼 시간복잡도가 O(log N)이 됨을 알 수 있다. 이렇게 표현하는 방식이 바로 아래의 균형 이진 탐색 트리이다.
     

     

   • 균형 이진 탐색 트리 Balanced binary search tree
     • O(logN) 시간에 삽입과 탐색을 할 수 있을 정도로 균형이 잘 잡혀 있는 경우
     • EX) Splay tree, AVL tree, RedBlack tree
       

       

   • 완전 이진 트리 Complete Binary Tree
     • 트리의 모든 높이에서 노드가 꽉 차 있는(2개가 모두 있는) 이진 트리. 즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
     • 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
     • 마지막 레벨 h에서 (1 ~ 2h-1)개의 노드를 가질 수 있다.
     • 배열을 사용해 효율적으로 표현 가능
   • 전 이진 트리 Full Binary Tree
     • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
   • 포화 이진 트리 Perfect Binary Tree
     • 전 이진 트리이면서 완전 이진 트리인 경우
     • 모든 말단 노드는 같은 높이에 잇어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.
     • 모든 내부 노드가 두 개의 자식 노드를 가진다.
     • 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
     • 노드는 개수는 2^(k-1)개 이다. (k: 트리의 높이)

---

관련 알고리즘 이론

• 이진 힙: 완전 이진 트리의 한 종류
• 트라이
• 그래프: 트리는 그래프의 한 종류

---

Reference

http://www.secmem.org/blog/2019/05/09/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A2%85%EB%A5%98%EC%99%80-%EC%9D%B4%ED%95%B4/

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html