이진트리란

각각의 노드가 최대 두개의 자식노드를 가지는 트리 자료구조

이진트리 종류

정이진트리(Full binary tree), 포화이진트리(Perfect Binary tree), 완전이진트리(Complete binary tree), 균형이진트리(Balanced binary tree)

정이진트리(Full binary tree)

full binary tree는 모든 node의 child가 2개 or 0개인 트리를 말한다.

즉, leaf node가 아닌 node는 child를 두 개 가져야만 한다는 뜻이다

포화이진트리(Perfect Binary tree)

perfect binary tree는 full binary tree + 모든 leaf node의 depth가 같은 트리를 말한다.

위의 그림을 보며 가득 찬 이진트리라고 생각하면 이해가 쉽다

perfect binary tree는 가장 깊은 depth의 node들은 child가 없고, 다른 모든 node들은 두 개의 child를 가진다.

완전이진트리(Complete binary tree)

complete binary tree의 depth가 d라고 할 때, depth가 d-1까지는 perfect binary tree이면서, depth가 d인 node(제일 아래 층 node들)은 왼쪽부터 오른쪽의 order대로 node가 채워져 있는 트리를 말한다.

즉, 중간의 순서를 건너뛰고 다음 node를 채울 순 없다.

왼쪽의 그림은 위와 같은 정의를 만족하지만, 오른쪽 그림은 5, 1 다음에 4의 left child node가 채워지지 않고 right child node가 생겼기 때문에 complete binary tree가 아니다.

균형이진트리(Balanced binary tree)

leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리

실제로 많이 쓰인다. 한쪽으로 쏠릴 수 있는 상황에서 트리의 높이를 균형적으로 유지시켜줄 수있어서 검색할때 최악의 경우에도 O(logN)의 안정성을 보장해준다!

균형이진트리는 AVL 트리, 레드블랙트리, B-Tree, B+tree, B*Tree 등에서 주로 사용한다

[자료 구조] - 트리 자료 구조 (3)-이진 트리와 종류(완전, 포화, 완벽, 균형) :: Binary Tree (Full, Complete, Perfect, Balanced)