07. 이진 트리

이진 트리 개요

• 트리는 나무의 형태를 뒤집은 것과 같은 형태의 자료구조
• 각 노드간 연결고리를 가지라고 하며 최상단을 루트, 최하단을 리프라 함

• 노드간 부모/자식 관계가 성립하며 같은 부모를 가진 노드들은 형제 노드라 함

트리의 길이, 깊이, 높이

• 길이(Length)는 출발노드에서 목적지 노드까지 거쳐야 하는 가짓수
• 깊이(Depth)는 루트로부터 특정 노드까지의 길이

• 높이(Height)란 루트 노드에서 가장 깊은 노드까지의 길이
• 이진 트리(Binary Tree)는 최대 2개의 자식 노드를 가질 수 있는 트리

포화 이진 트리

• 포화 이진 트리(Full Binary Tree)는 리프 노드를 제외한 모든 노드가 두 자식을 가진 형태

완전 이진 트리

• 완전 이진 트리(Complete Binary Tree)는 모든 노드들이 왼쪽 자식 노드부터 채워진 형태

높이 균형 트리

• 높이 균형 트리(Height Balanced Tree)는 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 형태