Binary Tree

각각의 노드의 자식 노드 수가 2개 이하로 구성되어 있는 Tree를 의미한다.

이진 트리는 다음과 같이 분류할 수 있다.

• 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미합니다.
• 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.
• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미합니다.
• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미합니다.
• 균형 이진 트리(balanced binary tree): 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 차이가 1 이하인 트리입니다. map, set을 구성하는 레드블랙트리는 균형 이진 트리 중 하나입니다.

Binary Search Tree

이진 탐색 트리란 정렬된 이진 트리로써 다음과 같은 속성을 가지고 있습니다.

• 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드 만 포함됩니다
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드 만 포함됩니다.
• 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리이어야 한다.
• 중복된 키를 허용하지 않습니다.