이진트리란?

[kkosang]

이진트리 (Binary Tree)

트리 구조에서 각 노드가 최대 2개의 자식노드를 갖는 계층적인 구조입니다.
자식노드의 개수가 최대 2개이기 때문에 없을 수도 있고 한개만 있을 수도 있습니다.

이진트리의 종류?

Full Binary Tree

• 모든 노드가 2개의 자식을 갖거나 자식이 아예 없음

Complete Binary Tree

• 왼쪽노드 부터 채워지는 트리
• 리프노드를 제외한 모든 레벨에 노드가 채워져 있음

Skewed Binary Tree

• 한쪽으로만 자식 노드가 연결된 트리

Binary Search Tree

• 노드에 저장된 값이 왼쪽 < 부모 < 오른쪽의 규칙을 지킴

Balanced Binary Tree

• BST를 만족함
• 높이가 최소가 되도록 유지
• AVL 트리와 레드-블랙 트리가 있음