트리

정의

방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 자료 구조

---

용어

• Root: 가장 상위의 정점
• Node: 각 정점
• Leaf Node: 자식이 없는 노드
• Level: Root 부터 몇 번째 깊이(단계)에 위치해 있는 지 표시
• Degree: 한 정점에서 뻗어 나가는 간선의 수

---

특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가짐
• 정점이 N 개인 트리는 반드시 N-1 개의 간선을 가짐
• 루트에서 특정 정점으로 가는 경로는 유일함
• 실생활 예: 조직도, 디렉토리 구조

---

이진 트리

• 각 정점이 최대 2개의 자식을 갖는 트리
• 완전 이진 트리: 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리
• 포화 이진 트리: 마지막 레벨까지 모두 채워져 있는 트리
• 편향 트리: 한 방향으로만 정점이 이어지는 트
• 탐색을 위한 알고리즘에서 많이 사용됨

---

이진 트리 특징

• 정점이 N 개인 이진 트리는 최악의 경우 높이가 N이 될 수 있음
• 정점이 N 개인 포화/완전 이진 트리의 높이는 log N 이 됨
• 높이가 n 인 포화 이진 트리는 2ⁿ - 1 개의 정점을 가짐
  이진법을 생각하면 편함
• 일반적으로 이진 트리를 사용하는 경우는 많지 않고
  이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등의 구현에 사용되는 경우가 많음

---

트리 구현 방법

그래프와 마찬가지로 인접 행렬, 인접 리스트 두 가지 방식으로 트리 표현 가능

---

이진 트리 구현 방법

• 배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현
• 자식의 수가 2개 이하이기 때문에 조금 더 최적화된 방식으로 구현 가능

---

Javascript 배열로 이진 트리 구현

• 0번 인덱스는 편의를 위해 undefined
• Left = Index * 2
• Right = Index * 2 + 1
• Parent = Math.floor(Index / 2)
• 연결 리스트로 구현 시 기존 연결 리스트의 next 를 left, right 로 바꾸어서 표현