[DATA STRUCTURE] 트리

트리

• 비선형 자료구조이며, 계층적 관계를 표현하는 자료구조
• 연결 리스트와 비슷하지만 노드 한개가 다른 여러 노드를 가리키는 자료구조 즉 노드로 이루어진 자료구조
• 트리는 하나의 루트 노드를 가지며, 루트 노드는 0개이상의 자식 노드를 가짐, 자식 노드 또한 0개이상을 자식 노드를 가지게 되며, 이는 반복적으로 정의 됨

---

트리 용어

• 노드 (Node) : 트리를 구성하고 있는 요소를 의미
• 루트 (Root) : 부모가 없는 노드, 즉 트리구조에서 최상위에 있는 노드를 의미함, 트리에는 최대 한개 루트만 존재
• 간선 (Edge) : 트리를 구성하기 위하여, 노드와 노드를 연결하는 선을 의미, 즉 부모에서 자식으로 이어지는 연결선
• 리프 (Leaf) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미, 즉 자식이 없는  노드
• 형제 : 부모가 같은 노드들을 지칭함

---

트리 특징

• 그래프의 한 종류, '최소 연결 트리' 라고 함
• 계층 구조
• 비순환 그래프의 한 종류
• 이진트리, 이진탐색트리, 균형트리, 이진 힙 등이 있음

	트리
정의	그래프의 한종류, DAG(Directed Acyclic Graph, 방향성 있는 비순환 그래프)의 종류
방향성	방향 그래프
사이클	사이클 불가능, 자체 간선 불가능, 비순환 그래프
루트노드	한개의 루트노드만 존재
부모-자식	부모 자식 관계
모델	계층 모델
순회	전위탐색, 중위탐색, 후위탐색, 레벨탐색(BFS)
간선의 수	노드가 N개인 트리는 항상 N-1의 간선을 가짐
경로	임의의 두 노드간의 경로는 유일함
예시	이진트리, 이진탐색트리, 균형트리, 이진힙

---

이진 트리 (Binary Tree)

루트 노트를 중심으로 두개의 서브트리로 나뉘어 지며, 나뉘어진 두 서브트리도 모두 이진 트리여야 함

• 각 노드가 자식이 없거나, 한 개 혹은 두개의 자식을 가짐
• 엄격한 이진 트리 :  모든 노드가 두개의 자식을 가지거나 자식이 없는 트리
• 포화 이진 트리 :  모든 노드가 두개의 자식을 가지고, 모든 리프 노드가 같은 레벨에 있는 트리, 모든 레벨이 꽉찬 트리
• 완전 이진 트리 : 트리 높이가 h일 경우, 레벨 h-1까지 모든 노드가 채워져있고 레벨 h에 있는 노드는 가능한 왼쪽으로 채워져 있는 트리
• 트리 높이로 각 이진 트리의 노드 개수를 추측할 수 있음

---

이진 검색 트리 (BST)

이진 검색 트리 규칙

이진 트리의 일종이며, 데이터를 저장하는 규칙이 있음 (특정 데이터의 위치를 찾기위해 사용되는 규칙), 즉 검색용 이진트리

• 이진 탐색 트리의 노드에 저장되는 값은 유일함 
• 노드 왼쪽 서브 트리의 모든 값들이 해당 노드의 값보다 작아야함
• 노드 오른쪽 서브 트리의 모든 값들이 해당 노드의 값보다 커야함
• 왼쪽, 오른쪽 서브 트리 모두 각각 이진 검색 트리여야함

이진 검색 트리 시간 복잡도

• O(logn)의 시간복잡도를 갖지만, 정확하게는 O(h)임 (트리의 높이를 하나씩 더할수록 추가할 수 있는 노드 수가 두개 증가하기 때문에)
• 저장 순서에 따라서 계속 한쪽으로 만 노드가 추가되는 경우가 발생할 수 있는데, 성능에 영향을 미치며, 시간복잡도가 O(n)이 됨, 이러한 경우는 편향트리라고 부름

---

트리 순회

• 전위탐색 (PreOrder 노드 -> 왼쪽 -> 오른쪽)
• 중위탐색 (InOrder 왼쪽 -> 노드 -> 오른쪽)
• 후위탐색 (PostOrder 왼쪽 -> 오른쪽 -> 노드)
• 레벨탐색 (BFS)