[알고리즘 스터디 with 케이시] 비 선형 자료 구조 - 트리

트리

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다.

• 루트
  • Level 1에 있는 노드
• 노드
  • 정점
• Leaf Node
  • 마지막 Level 에 있는 노드
• Degree
  • 부모 노드로 부터 나오는 간선의 수
• Level
  • 루트 노드로 부터 얼마나 떨어진지 나타낸다.
  • 루트 노드가 레벨 1이고 한 칸 멀어질 수록 + 1이 된다.

특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N 개인 트리는 반드시 N-1개의 간선이 생긴다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

이진트리

각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.

이진 트리 특징

• 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다.
• 정점이 N개인 포화 또는 완전 이진트리의 높이는 log N이다.
• 높이가 h인 포화 이진 트리는 2^h^ - 1개의 정점을 가진다.
• 일반적인 이진트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다.
  • 이진 탐색 트리
  • 힙
  • AVL 트리
  • 레드 블랙 트리

트리 구현 방법

이진 트리의 구현 방법