트리(Tree) 개념

<트리(Tree)>
- 대량의 데이터를 관리하는 역할

- 비선형 구조 -> 모든 데이터가 하나의 선상에 존재하지 않는 구조, 하나의 노드에 연결된 노드들이 여러개이면서 대칭구조를 이룬다 
 *선형 구조-> 모든 데이터가 하나의 선상에 존재하는 구조

- 트리는 정점(node)과 간선(edge)으로 이루어진 그래프의 변형
  *트리(Tree)와 그래프(Graph)의 차이 
     1) 트리 : 그래프의 부분집합, 트리는 오직 하나의 부모노드(Parent Node)를 가질 수 있다 
     2) 그래프 : 하나 이상의 부모노드(Parent Node)를 가질 수 있다

- 비 선형구조(Non-linear structure)란 하나의 노드에 연결된 노드가 복수 개이면서 계층구조

- 트리에서는 루트노드(가장 상위에 위치한 노드)를 제외한 모든 노드가 하나의 상위 노드만을 가지는 특징

- 하나 이상의 상위 노드를 갖는다면 그래프

- 트리는 많은 데이터를 효율적으로 저장하고 검색할 수 있는 기능 -> 트리의 목적
  *데이터와 관련된 트리 : B-Tree(ex. 하나의 노드(data가 하나만 저장)밑에 50개의 노드(data가 50개를 저장)를 가질 수 있다)

- 트리구조는 주로 '포인터(or 재귀함수)'를 사용한다

- 트리는 배열로 정의할 수 없다(배열은 연속공간에 저장되어있으며 크기가 사전에 정의되있어야하기 때문)




<트리의 개념> - (1)
- 트리는 하나 이상의 '유한한 개수의 노드(data)'로 구성되어 있으며, 최상위에 위치한 루트노드(Root Node)에서 시작하여
  노드와 노드는 간선(edge)으로 연결되어있다




<트리의 개념> - (2)
- 트리 구조에서 많이 사용되는 용어

1. 노드(Node) : 트리를 구성하는 하나의 항목 -> 데이터가 저장되어있는 공간

2. 간선(Edge) : 노드와 노드를 연결하는 선 -> 가상의 보이지 않는 논리적인 선(포인터) 또는 연결
  *포인터 : 컴퓨터 메모리상의 주소

3. 루트(Root) : 최상위에 존재하는 노드, 부모노드가 존재하지 않는다

4. 레벨(Level) : 루트 노드에서부터 하나의 간선마다 레벨이 1씩 증가

5. 부모/자식 노드(Parent/Child Node) : 한 노드에 간선으로 연결된 상위 노드를 부모노드라 하고
   하나의 노드에 간선으로 연결돼 하위의 노드를 자식노드라고 한다

6. 말단 노드(Leaf Node) : 최하위 레벨에 존재하는 노드, 자식노드가 존재하지 않는다

7. 비 말단 노드(Non-leaf Node) : 최하위 노드를 제외한 다른 모든 노드

8. 형제 노드(Brothers/Siblings) : 하나의 부모 노드에 연결된 모든 자식 노드들

9. 조상 노드(Ancestors) : 하나의 노드에서 루트노드까지의 모든 상위 레벨에 존재하는 노드들

10. 자손 노드(Descendants) : 하나의 노드에서 말단 노드까지 간선으로 연결된 모든 노드들

11. 차수(Degree) : 어떤 노드에 연결된 자식 노드의 개수

12. 트리의 차수(Degree of a tree) : 트리 내의 노드의 최대 차수 -> 최대차수(=최대용량)

13. 높이(Height) : 말단 노드에서 어떤 노드까지의 레벨 수

14. 깊이(Depth) : 루트 노드에서 어떤 노드까지의 레벨 수

15. 숲(Forest) : 여러 개의 트리가 모인 구조

16. 부 트리, 일부 트리, 부분 트리(Sub Tree) : 트리 내의 노드와 간선들의 부분집합
  - 노드와 간선들이 서로 '연결되어야' 부분트리가 된다 -> 즉, 간선과 노드들이 분리된 상태는 부분트리로 인정되지 않는다

17. 순서 트리(Ordered Tree) : 노드의 '위치'를 의미, 부모노드의 연결이 다를 경우

18. Oriented tree : '레벨'에 의미를 가진다(위치는 무의미), 첫번 째 레벨에 A, 두번 째 레벨에 B, C 등
    *순서트리로 보면 다른 구조일 수 있고, 레벨트리로 보면 같은 구조일수도 있다

19. 사향 트리(Skewed Tree) : 트리를 구성하는 노드들이 한 쪽 방향으로 '비대칭' 상태로 커지는 상태를 말한다
  - 상당히 비효율적인 구조
    *불균형상태의 구조 : 같은 레벨에 들어갈 수 있는 데이터의 갯수가 적어지거나 달라질 수 있다, 레벨의 숫자에 비해 저장할 수 있는 데이터의 갯수가 적어진다
    *균형상태의 구조 : 같은 레벨에 들어갈 수 있는 데이터의 갯수가 많아진다, 레벨의 숫자에 비해 저장할 수 있는 데이터의 갯수가 많아진다
    *이진트리 - 데이터의 갯수 : 2^n
    *삼진트리 - 데이터의 갯수 : 3^n
 
20. 트리의 순회(Traversal) : 트리내의 모든 Node를 한 번씩 정해진 순서로 방문하는 것을 말한다
     트리의 순회에는 모두 5가지 방식이 있다

21. Level Order : 위에서 아래로, 왼쪽에서 오른쪽으로

22. Family Order : 부모노드에서 시작 자식노드를 왼쪽에서 모두 방문하고 가장 오른쪽 노드에 대해 동일한 과정을 반복

23. 전위 순회(Preorder) : 부모노드가 우선 방문하고 왼쪽 부 트리가 오른쪽 부 트리에 우선하는 방식

24. 중위 순회(Inorder) : 왼쪽 부 트리를 모두 방문한 뒤 부모 노드를 방문하고 오른쪽 부 트리를 방문하는 방식(Binary Tree에서만 가능한 방식)

25. 후위 순회(Postorder) : 왼쪽 부 트리, 오른쪽 부 트리를 모두 방문한 뒤 부모 노드를 방문하는 방식