자료구조와 알고리즘 - 트리

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 트리란?

• 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조
• Root: 가장 상위의 정점
• Node: 각 정점
• Leaf Node: 자식이 없는 정점(가장 하위)
• Level: Root로부터 몇 번째 깊이인지를 표현
• Degree: 한 정점에서 뻗어나가는 간선 수

2. 트리의 특징

• Root를 제외한 모든 Node는 하나의 부모 Node를 가짐
• Node가 N개인 트리는 반드시 N-1개의 간선을 가짐
• Root에서 특정 정점으로 가는 경로는 유일
• 편향 트리
  • 한 방향으로만 정점이 이어진 것

이진트리

• 각 정점이 최대 2개의 자식을 가지는 트리를 의미
• 탐색을 위한 알고리즘에서 많이 사용
• 완전 이진트리
  • 마지막 Level을 제외하고 모든 Node가 채워진 이진 트리
• 포화 이진트리
  • 마지막 Level까지 모든 Node가 채워진 이진 트리
• Node가 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있음
• Node가 N개인 포화 또는 완전 이진 트리의 높이는 logN
• 높이가 h인 포화 이진 트리는 2^h -1개의 정점을 가짐
• 다음 자료구조에 응용
  • 이진 탐색 트리
  • 힙
  • AVL 트리
  • 레드 블랙 트리

3. 트리의 구현 방법

• 인접 행렬, 인접 리스트 두 가지 방식으로 트리를 표현
• 이진 트리의 경우, 배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현
• JavsScript에서는 배열 또는 연결 리스트로 구현

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript