Tree   트리

1. 트리 구조 / 토폴로지 (Tree Topology, Tree Structure, Tree Data Structure)

  ㅇ 1 이상의 노드로 구성된 유한 집합
     - 마치 나무 가지 처럼 계층적(Hierarchical)으로 연결되는 논리적/수학적 구조(체)

        


2. 트리의 용도

  ㅇ 데이터의 포함 관계, 계층 관계 등을 나타내는데 유용
     - 족보 상의 조상-자손 관계를 나타내는 가계도, 조직 체계도 등
  ㅇ 데이터의 분류 등
  ㅇ 데이터의 저장 구조로써의 파일시스템 등
  ㅇ 데이터의 정렬 및 탐색 용도 등
  ㅇ 네트워크 형상 표현 등
     - 통신 네트워크에의 트리 구조 적용 : 트리형 토폴로지 (Tree Topology)
        . 망형(Mesh Topology), 링형(Ring Topology)에 비해 장애 확산방지 및 고립에 유리함
     - 例) 이더넷 스위치 연결 등


3. 트리의 정의

  ㅇ 반드시 루트(Root)라는 특별한 노드가 하나 있어야 함

  ㅇ 나머지 노드들은 다시 각각 독립된 부분 트리 (subtree, 서브트리)가 됨
     - 즉, 재귀적(순환적)인 방법으로 트리를 정의할 수 있음 

     * 재귀적으로 정의된(recursively defined) 자기 참조(self-referential) 자료 구조 임


4. 트리의 특징

  ㅇ 자료의 단순 나열이 아닌 연관 관계(계층 관계, 포함 관계 등)를 표현    ☞ 관계 (Relation) 참조
     - 노드 간에 부모 자식 관계를 갖음
        . 나무나 족보 처럼 노드 사이의 관계가 계층적(Hierarchy) 관련성을 갖음
        . 트리는 조상과 자손 처럼 포함 관계 등을 효율적으로 표현할 수 있음

  ㅇ 트리는 그래프의 일종 (부분 그래프)
     - 트리는 정점(노드) 및 선분(가지)으로 형성되는 그래프의 특수한 경우
        . 루프 순환 없는 단순 그래프임
           .. 단순 순환(Loop) 없이 연결된, 무방향 그래프 구조임
        . 계층 개념 있음
           .. 트리는 그래프이지만, 루트를 가지므로 (그래프는 루트 없음), 계층 개념이 있게됨
           .. 서로 독립된 노드들이, 선분에 의해서 연결된, 계층형 자료구조임
        . 모든 노드 쌍 간에, 단순 경로 만 유일하게 존재함
           .. 임의 노드들 간에 연결은 하나의 경로로 만 가능

  ㅇ 그래프 및 트리 구조는 비선형 자료구조에 속함
     - 노드들의 속성을 선형 자료구조로 표현할 수 없는 경우에 사용됨


5. 트리의 표현 및 구현

  ㅇ 트리의 표현 방법
     - 거꾸로 세운 나무 형상, 중첩된 괄호(Nested Parenthesis), 중첩된 집합(Nested Set),
       들여쓰기(Indentation) 표현법 등

  ㅇ 트리의 구현 방법
     - 통상, 연결 리스트 구조를 이용하여 재귀적으로 구현
     - 자료 저장 구조로써 트리 구현법
        . 왼쪽 자식-오른쪽 형제 표현법(Left Child-Right Sibling Representation,LC-SR)
           .. 왼쪽 링크에 자식을 놓고, 오른쪽 링크에 형제 노드를 놓는 표현 방법
           .. 각 노드 마다 2개의 포인터를 갖고 표현 가능
           .. 이는, LC-RS Binary Tree 라 하여, 범용 트리를 이진 트리로 변환 가능한 표현법 임 


6. 트리의 종류

  ※ ☞ 트리 종류 참조
     - 순서트리, 이진트리, 이진탐색트리, 균형트리 등


7. 트리의 용어들

  ※ ☞ 트리 용어 참조
     - 노드, 부 트리 갯수, 깊이, 차수, 단말노드, 자식, 부모, 루트 등


8. 트리의 연산

  ㅇ 트리의 생성
     - 例) createTree(data, leftChild, rightChild) 
        . 데이터값을 탑재하고, 왼쪽,오른쪽 자식 노드를 취하는/초기화하는 트리의 생성

  ㅇ 트리의 순회 ☞ 트리 순회 (Tree Traversal) 참조
     - 일정 순서로 트리 내 모든 노드를 방문하는 것
     - 방문 순서에 따른 구분 : 전위 순회 (Preorder), 중위 순회 (Inorder), 후위 순회 (Postorder)