트리
방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조
[사진출처] https://6mini.github.io/computer%20science/2022/02/03/tree/
트리의 특징
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
- 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
- 트리내에 또 다른 트리가 있는 재귀적 자료구조이다.
이진 트리 (Binary Tree)
이진 트리는 최대 2개의 자식노드를 가진다. (자식노드가 없거나 1개여도 가능)
이진 트리의 특징
- 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다. (N개의 노드를 가진 편향트리)
- 정점이 N개인 포화 또는 완전 이진트리의 높이는 log N이다.
- 레벨이 증가됨에 따라 2개씩 정점이 생기기 때문 - 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등에 사용된다.
이진 트리의 종류
1. 편향 이진 트리
편향 이진 트리는 하나의 차수로만 이루어진 경우를 말한다.
배열(리스트)와 같은 선형 구조이므로 가장 아래쪽에 위치한 노드를 탐색 시 모든 데이터를 탐색해야한다는 단점이 있어서 효율적이지 못하다.
2. 완전 이진 트리
모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미한다.
3. 포화 이진 트리
포화 이진 트리는 Leaf Node를 제외한 모든 노드의 차수가 2개로 이루어져 있는 경우다.
해당 차수에 몇개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이하다.
출처
프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.
FrontEnd Developer