[Data Structure] Tree

🎯 목표 :  Tree 자료구조의 이해

📒 Tree

비 선형 구조로 나무를 거꾸로 그린 형태의 자료구조.

📌 Tree 구조와 특징

• Root 라는 하나의 최상위 데이터를 시작으로 여러개의 데이터를 간선(=가지 Edge)으로 연결한다.
• 각 데이터를 Node라고 하며, 두 노드가 계층 구조로 이루어 져있다.
• 깊이(Depth)는 루트로 부터 하위 계층의 특정 노드까지의 길이를 표현 한다.
• 레벨(Level)은 같은 계층에 있는 노드를 묶은 집합이다. 같은 레벨의 노드를 형제 노드라 할수 있다.
• 높이(Height)는 리프노드를 기준으로 루트까지의 길이를 표현한다.
• 서브 트리는 트리 구조의 데이터에서 작은 트리를 표현한다.

---

📒 Binary Tree / Binary Search Tree

이진 트리의 구조와 이진 트리 기반의 탐색을 위한 자료구조인 이진 탐색 트리구조를 이해한다.

---

📌 이진 트리(Binary Tree)

• 각 노드가 0개의 노드 이상 왼쪽 자식과 오른쪽 자식 노드 최대 둘을 갖는 트리 구조다.
• 완전 이진 트리(Complete binary tree)

• 완전 이진트리는 마지막 레벨을 제외한 레벨은 모든 자식 노드를 가지고있다.
• 마지막 레벨의 노드는 왼쪽부터 오른쪽으로 노드를 빠짐없이 채우되 끝까지 채울 필요없다.
• 정 이진 트리(Full binary tree)는 각 노드가 0개 또는 2개의 자식노드를 가지며, 루트를 제외한 모든 레벨의 노드가 끝까지 채워져 있지 않은 비대칭 구조다.
• 포화 이진 트리(Perfect binary tree)는 마지막 레벨의 노드까지 가득 채워져 있는 구조다. 

---

📌 트리의 탐색

👉 너비 우선 탐색(Breathde First Search)

• 루트에서 왼쪽의 자식 노드로 부터 각 레벨별 탐색을한다.

👉 깊이 우선 탐색(Depth First Search)

• 깊이를 기준으로 하나의 경로를 끝까지 탐색후 다음 깊이 경로를 탐색한다.

👉 깊이 우선 탐색에서의 순회

• 깊이 우선 탐색을 할때 언제 노드를 방문하며 순회를 할지에 대한 세가지 종류가 있다.

👉 전위 순회

• 루트 -> 왼쪽 서브 트리 -> 오른쪽 서브트리 순으로 방문하여 순회.

👉 중위 순회

• 왼쪽 서브 트리 -> 루트 -> 오른쪽 서브 트리 순서로 방문하여 순회.

👉 후회 순회

• 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문하여 순회

---

📌 이진 탐색 트리

• 이진트리 기반의 탐색을 위한 자료구조.
• 효율적인 탐색 능력을 가지며 삽입과 삭제가 가능하다.
• 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모노드의 값보다 작고, 모든 오른쪽 자식의 값이 루트나 부모노드의 값보다 크다.
• 배열로 이진트리를 구현할 경우 메모리 낭비가 심하며 배열의 크기에따라 트리의 높이가 제한된다.
  이를 개선 하기 위해 일반적으로 Link를 이용한 이진트리를 구현하며 LinkedList를 구현하는 방법과 유사하다.

---

📌 이진 탐색 트리 구현

• 개념 학습은 블로깅 정리로 마무리하고,
• 다음 블로깅에서는 이진 탐색 트리를 Link를 이용한 방식으로 삽입과 삭제 기능을 하는 메소드까지 구현해 볼것이다.
• 이진 탐색 트리는 균형 잡힌 입력순서의 데이터가가 아닐때 입력 되는 값의 순서에 따라 한쪽으로 노드가 몰릴수도 있다. 이를 방지하기 위해 균형 이진 검색 트리 방식으로 구현을 해볼 예정이다.