이진 탐색 트리

• 노드의 왼쪽 자식트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있습니다.
• 노드의 오른쪽 자식트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있습니다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 합니다.
• 여기서 탐색은 정렬이 되어 있다는 의미입니다.
• 이진탐색트리는 탐색된 노드를 조회하므로 조회, 삭제, 삽입 연산 모두 O(log n) 시간복잡도를 가집니다.

이진 트리의 유형

Full

모든 자식 노드가 0 또는 2 인 트리입니다. 해당 이진 트리 유형을 만족하려면 각 노드는 자식 노드가 0 이거나, 2개를 무조건 가져야 합니다.

Perfect

리프 노드를 제외한 모든 노드가 자식 노드를 2개 씩 가져야 만족하는 이진트리 입니다. 또한 모든 리프노드는 모두 동일한 레벨에 위치해 있어야 합니다.

다시 정리하자면, 리프를 제외한 모든 노드가 2개의 자식 노드를 가져야 하고, 리프 노드는 무조건 같은 레벨에 위치해 있어야 하므로 완전한 삼각형 형태로 트리구조를 가질 수 밖에 없습니다.

※ 트리의 레벨 참고 이미지

Complete