2022-11-10

Tree

Tree: 노드와 링크로 구성된 자료구조.

• 계층구조(폴더, 조직도)
• acyclic = 비순환 (그래프와의 차이)

종류

• 포화 이진 트리
• 완전 이진 트리

포화 이진 트리

• 트리의 모든 레벨에 노드가 존재하는 트리
• 포화 이진 트리의 노드의 갯수 -> (2^깊이+1) - 1
• 포화 이진 트리의 깊이 -> log2N
• 간선의 수 -> N - 1

완전 이진 트리

• 트리의 마지막레벨만 노드가 없는 트리
• 왼쪽부터 채워져 있어야 한다.
• 완전 이진 트리의 깊이 -> log2N