Tree Algorithm의 정의

트리(Tree)의 정의

$ 1개 이상의 노드로 구성된 유한개의 집합

• 마치 나무처럼 계층적(Hierarchical)으로 연결되는 논리적/수학적 구조(체)

$ 트리를 왜 사용하는가?

• 네트워크 구조 표현
• 데이터 정렬 및 탐색 등등

$ 트리가 되기 위한 조건

• Root가 필요(시작점 혹은 원점)
• 나머지 node들은 독립 트리구조를 생성(Subtree)
  ~ 재귀적으로 트리를 정의 가능

$ 트리의 특징

• 자료의 연관성을 나타냄
  ~ 상위노드와 하위노드로 구분
• graph에 포함됨
  ~ 반복 loop를 사용하지 않는 link graph
• 단순 loop를 갖지 않는 비방향성 link graph
  ~ 모든 node간 쌍 간에 유일한 단순 경로 만 존재함 (One to One)

$ 트리의 표현 및 구현

• 거꾸로 세운 나무 형상, 중첩된 괄호(Nested Parenthesis), 중첩된 집합(Nested Set),
  들여쓰기(Indentation) 표현법
• 트리 구현
  ~ 통상, 리스트 구조를 이용하여 재귀적으로 구현
• 자료 저장 구조로써 트리 구현법
  ~ 왼쪽 자식-오른쪽 형제 표현법(Left Child-Right Sibling Representation,LC-SR)