[자료구조] Binary Tree의 개념과 종류
이진 트리란 ?
이진 트리는 트리 형태의 자료 구조 중 가장 많이 사용하는 트리로, 각 노드의 자녀 노드 수가 최대 두개인 트리를 이진 트리(Binary Tree)라고 합니다.
형태에 따른 이진 트리 종류
1. Full Binary Tree (정 이진 트리)
Full Binary Tree란 모든 노드가 자녀 노드가 없거나 또는 두 개의 자녀 노드를 가지는 이진 트리입니다. (즉, 자녀 노드를 1개를 가지는 노드가 없어야 합니다)
2. complete binary tree (완전 이진 트리)
complete binary tree는 마지막 레벨을 제외한 모든 레벨의 노드가 두 개씩 노드를 가지고, 마지막 레벨은 왼쪽 부터 빠짐없이 노드가 채워지는 이진 트리입니다.
3. perfect binary tree (포화 이진 트리)
perfect binary tree란 모든 레벨에서 노드가 빠짐없이 채워져 있는 이진 트리입니다.
4. degenerate binary tree (변질 이진 트리)
degenerate binary tree는 모든 부모 노드가 하나의 자녀 노드만 가지는 이진 트리입니다.
이 degenerate binary tree는 자녀 노드의 위치에 따라 left skewed binary tree, right skewed binary tree로 나뉩니다.
4.1. left skewed binary tree
left skewed binary tree는 왼쪽으로 편향된 이진 트리라는 뜻으로, 모든 노드가 왼쪽 자녀 노드 한개만 가지는 이진 트리입니다.
4.2. right skewed binary tree
right skewed binary tree는 오른쪽으로 편향된 이진 트리라는 뜻으로, 모든 노드가 왼쪽 자녀 노드 한개만 가지는 이진 트리입니다.
5. balanced binary tree (균형 이진 트리)
balanced binary tree는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 트리를 말합니다.
📌 서브트리란 ?
특정 노드의 자식 노드들이 각각을 루트 노드로 트리를 구성하는 트리의 부분 집합을 말합니다.
📌 트리의 높이란 ?
루트 노드 부터 리프 노드까지의 가장 긴 경로의 간선의 수를 말합니다.
아래의 예시 그림에서 모든 노드의 서브트리가 balanced 한지 알아보겠습니다.
(1) 노드 2 : 왼쪽 서브 트리 {5,7} 은 트리의 높이가 1이고, 오른쪽 서브 트리 {9,1,3,4} 의 트리의 높이가 2입니다.
(2) 노드 5 : 왼쪽 서브 트리는 없기 때문에 트리 높이가 -1 이고, 오른쪽 서브트리 {7} 은 트리 높이가 0입니다.
(3) 노드 9 : 왼쪽 서브 트리인 {1,4} 는 트리 높이가 1 이고, 오른쪽 서브트리 {3} 은 트리 높이가 0입니다.
(4) 노드 1 : 왼쪽 서브트리 {1}은 트리 높이가 0이고, 오른쪽 서브트리는 없기 때문에 -1 입니다.
모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 트리 높이 차이가 1을 넘지 않기 때문에, balanced binary tree(균형 이진 트리)라고 할 수 있습니다.
만약 7번 노드가 없을 때는 2번 노드의 왼쪽 서브트리와 오른쪽 서브트리의 트리 높이 차이가 2가 되기 때문에 balanced binary tree라고 할 수 없습니다.
📌 출처