Tree, Tree Structure, Tree Topology   트리, 트리 구조, 나무 구조, 목 구조, 트리 토폴로지

(2018-05-29)
Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
통신/네트워킹 >   1. 통신 이란?
  2. 신뢰적 통신
[통신이론]
[선로/전송]
[통신망 일반]
[회선교환(PSTN)]
[무선/이동통신]
[광통신]
[인터넷/데이터통신]
통신망 일반 >   1. 통신망
[통신망 기초]
[통신표준(IEEE/ITU)]
[통신망 관리]
[광역망]
[가입자망]
[홈네트워킹]
[시험/연구망]
통신망 기초 > [토폴로지]
[통신망 종류]
[참조모델]
토폴로지   1. "토폴로지" 이란?
  2. 망형/그물형 (Mesh)
  3. 트리형 (Tree)
  4. 링형/환형 (Ring)
  5. 성형/스타형 (Star)
  6. 버스형 (Bus)
  7. 선형망 (Linear)
  8. PTP,PTMP
  9. 중첩망 (Overlay)
  10. 토큰 제어
  11. 토큰 링
  12. 토큰 버스

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
정보기술(IT) >   1. 정보기술
[전산기초]
[컴퓨터구조]
[프로그래밍]
[데이터베이스]
[소프트웨어 공학]
[운영체제]
[정보보호/보안]
[IT 기타기술]
프로그래밍 >   1. 프로그램,프로그래밍
[프로그래밍 언어론]
[객체지향]
[자료구조]
[알고리즘]
[자료표현(알파벳/코드)]
[시스템 소프트웨어]
[프로그래밍언어 종류]
[프로그래밍 기타일반]
자료구조 >   1. 자료구조
[선형자료구조(리스트 등)]
[비선형자료구조(트리,그래프)]
[자료구조 기타일반]
비선형자료구조(트리,그래프) > [그래프]
[트리]
트리   1. 트리
  2. 트리 관련 용어
  3. 트리 종류
  4. 멀티캐스트 트리
  5. 스패닝 트리
  6. 이진 트리
  7. 트리 순회

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

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

     

  ㅇ 트리 주요 활용
     - 족보 상의 조상-자손 관계를 나타내는 가계도, 조직 체계도 등
     - 데이터 저장 구조로써의 파일시스템 등
     - 네트워크 형상 표현 등
     - 데이터 정렬 및 탐색 용도 등


2. 트리의 필수 정의

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

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


3. 트리의 특징

  ㅇ 나무나 족보 처럼 노드 사이의 관계가 계층적 관련성을 갖음
     - 트리는 조상과 자손과의 관계 등을 효율적으로 표현할 수 있음

  ㅇ 트리는 그래프의 일종
     - 트리는 정점(노드) 및 선분(가지)으로 형성되는 그래프의 특수한 경우
        . 서로 독립된 노드들이 선분에 의해서 연결된 계층자료구조
           .. 순환 루프를 포함하지 않는 연결 그래프의 일종

     - 단순 순환(loop,cycle)을 갖지않는 비방향성 연결 그래프 구조임
        . 모든 노드 쌍 간에 유일한 단순 경로 만 존재함
           .. 즉, 임의 노드들 간에 연결은 하나 만 가능

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


4. 트리의 표현

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

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

  ㅇ 트리 구현
     - 일반적으로, 리스트 구조를 이용하여 재귀적으로 구현


5. 트리 종류

  ※ ☞ 트리 종류 (순서트리,이진트리 등) 참조


6. 트리를 설명하는 용어들

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


7. 트리 순회 (Tree Traversal)

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


8. 통신 네트워크에의 트리 구조 적용

  ㅇ (Tree Topology)
     - 망형(Mesh Topology), 링형(Ring Topology)에 비해 장애 확산방지 및 고립에 유리함

  ※ 例) 이더넷 스위치 연결 등


[토폴로지] 1. "토폴로지" 이란? 2. 망형/그물형 (Mesh) 3. 트리형 (Tree) 4. 링형/환형 (Ring) 5. 성형/스타형 (Star) 6. 버스형 (Bus) 7. 선형망 (Linear) 8. PTP,PTMP 9. 중첩망 (Overlay) 10. 토큰 제어 11. 토큰 링 12. 토큰 버스

 
        최근수정     요약목록(시험중)     참고문헌