1️⃣ 트리(Tree).

트리(Tree) 는 계층적 구조를 나타내는 자료구조로, 노드(Node)와 에지(Edge)로 구성됩니다.

트리는 사이클이 없는 연결 그래프(Connected Graph)이며, 계층적 데이터 표현에 매우 유용합니다.

트리는 부모-자식 관계를 가지며, 데이터의 조직화와 검색, 계층적 데이터 표현에 사용됩니다.

1️⃣ 트리의 구성 요소.

1. 노드(Node) : 트리의 기본 단위로, 데이터를 저장합니다.

2. 에지(Edge) : 노드와 노드를 연결하는 선으로, 부모-자식 관계를 나타냅니다.

3. 루트(Root) : 트리의 최상위 노드로, 부모 노드가 없습니다.

4. 부모(Parent) : 다른 노드를 가리키는 노드입니다.

5. 자식(Child) : 부모 노드에 의해 가리켜지는 노드입니다.

6. 잎(Leaf) : 자식 노드가 없는 노드입니다.

7. 내부 노드(Internal Node) : 자식 노드가 있는 노드입니다.

8. 레벨(Level) : 루트 노드에서 특정 노드까지의 에지 수를 나타냅니다.

9. 높이(Height) : 트리의 최대 레벨을 의미합니다.

2️⃣ 트리의 특성.

• 계층적 구조 : 트리는 계층적 구조로 데이터를 조직화합니다.
• 사이클 없음 : 트리는 사이클이 없는 그래프입니다.
• 연결성 : 모든 노드는 하나의 연결된 구성 요소로 되어 있습니다.
• 한 개의 루트 노드 : 트리는 하나의 루트 노드를 가지며, 루트 노드는 트리의 시작점입니다.

3️⃣ 트리의 종류.

1. 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리입니다.

2. 이진 탐색 트리(Binary Search Tree, BST) : 이진 트리의 일종으로, 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값이 부모 노드의 값보다 큰 특성을 가집니다.

3. 균형 이진 트리(Balanced Binary Tree) : AVL 트리, 레드-블랙 트리 등과 같이 트리의 높이가 균형을 이루도록 유지하는 트리입니다.

4. B-트리(B-Tree) : 데이터베이스와 파일 시스템에서 사용되는 트리로, 자식 노드의 수가 정해진 다진 트리(Multiway Tree)입니다.

5. 힙(Heap) : 완전 이진 트리의 일종으로, 부모 노드의 값이 자식 노드의 값보다 크거나 작은 특성을 가집니다.

6. 트라이(Trie) : 문자열 검색을 위한 트리 자료구조로, 접두사 검색에 유용합니다.

4️⃣ 트리의 주요 연산.

1. 삽입(Insertion) : 트리에 새로운 노드를 추가합니다.
2. 삭제(Deletion) : 트리에서 노드를 제거합니다.
3. 탐색(Search) : 트리에서 특정 값을 찾습니다.
4. 순회(Traversal) : 트리의 모든 노드를 방문합니다. 전위(Preorder), 중위(Inorder), 후위(Postorder), 레벨 순회(Level Order) 방식이 있습니다.