반응형
반응형
Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS
💋 트리 구조의 분류
트리 자료구조는 주로 노드 간의 관계
및 자식 노드의 개수
에 따라 분류됩니다.
(먼저 트리 구조에 대해 이해해야 합니다.)
✔️ 이진 트리 (Binary Tree):
- 각 노드가
최대 두 개의 자녀 노드
를 가지는 트리 - 자녀 노드가 2개니깐,
left
,right
로 구분할 수 있습니다.
✔️ 삼진 트리 (Ternary Tree):
- 각 노드가
최대 세 개의 자녀 노드
를 가지는 트리 - 일반적으로
left
,mid
,right
이라는 구분을 사용합니다.
✔️ N-트리 / 일반 트리 (N-ary Tree or Generic Tree):
- 각 노드가
최대 N개의 자식
을 가질 수 있는 트리 - 노드는 레코드 및 자식에 대한 참조 목록으로 구성됩니다.
- 중복 참조는 허용되지 않습니다.
이중에서 이진 트리의 종류에 대해서 자세히 알아보겠습니다.
- 풀 이진 트리 (Full Binary Tree)
- 완전 이진 트리 (Complete Binary Tree)
- 균형 이진 트리 (Balanced Binary Tree)
- 퇴화 이진 트리 (Degenerate or Pathological Binary Tree)
💋 풀 이진 트리 (Full Binary Tree)
- 모든 노드에
자녀가 0개거나 2개
인 트리
A full binary tree is a binary tree with either zero or two child nodes for each node.
💋 완전 이진 트리 (Complete Binary Tree)
- 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고, 마지막 레벨은
왼쪽부터 빠짐없이
노드가 채워진 이진 트리
A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.
💋 포화 이진 트리 (Perfect Binary Tree)
- 모든 레벨에서 노드가 빠짐없이 채워져 있는 이진 트리
- perfect binary tree / non-perfect binary tree
💋 균형 이진 트리 (Balanced Binary Tree)
- 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의
높이 차이가 최대 1
인 이진 트리
💋 변질 이진 트리 (Degenerate Binary Tree)
- 모든 부모 노드는
하나의 자녀 노드만
가지는 이진 트리 - pathological binary tree라고도 불립니다.
- 모든 부모 노드가 왼쪽 자녀만 가지면 left skewed binary tree, 오른쪽 자녀만 가지면 right skewed binary tree라고 부릅니다.
💋 참고자료
- https://www.geeksforgeeks.org/full-binary-tree/
- https://www.geeksforgeeks.org/complete-binary-tree/
- https://www.geeksforgeeks.org/perfect-binary-tree/
도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!
반응형
'Computer Science > Data Structure' 카테고리의 다른 글
[자료구조] 이진 탐색 트리 (Binary Search Tree): 개념, 순회, 연산과 시간 복잡도 (2) | 2023.12.15 |
---|---|
[자료구조] Priority Queue(우선순위 큐)와 Heap(힙) (2) | 2023.12.15 |
[자료구조] 트리(Tree) 구조의 개념, 용어, 특징에 대해 알아보자! (5) | 2023.12.14 |
[자료구조] 스택(Stack), 큐(Queue): 개념, LinkedList vs ArrayDeque, 시간복잡도 비교 (3) | 2023.12.13 |
[자료구조] ADT(Abstract Data Type)란?: 배열, 스택, 큐, 집합, 맵, 트리, 우선순위 큐의 ADT와 자바에서 구현한 자료구조 (0) | 2023.12.09 |