두 갈래라는 구조적 조건
이진 트리의 노드는 자식이 없거나 한 개 또는 두 개일 수 있다. 모든 노드에 자식이 꼭 둘씩 있어야 하는 것은 아니다. 왼쪽 자식 하나만 있는 경우와 오른쪽 자식 하나만 있는 경우도 구별한다.
한 노드를 기준으로 그 아래 구조를 부분 트리라고 한다. 부분 트리 역시 같은 형태의 규칙으로 설명할 수 있어 재귀적인 알고리즘을 적용하기 쉽다.
탐색 규칙은 별도로 추가된다
이진 트리라는 조건만으로 데이터가 크기순으로 정렬되지는 않는다. 이진 탐색 트리는 왼쪽과 오른쪽 부분 트리의 값에 관한 순서 규칙을 추가한 구조다. 중복 값을 처리하는 정책도 따로 정해야 한다.
탐색 트리가 한쪽으로 길게 늘어서면 찾기 과정이 많은 노드를 거칠 수 있다. 균형을 유지하는 방법은 높이가 지나치게 커지는 것을 막지만, 기본 이진 트리 자체가 균형을 보장하는 것은 아니다.
순회 순서가 바꾸는 결과
전위 순회는 노드를 먼저 처리한 뒤 두 부분 트리로 이동하고, 후위 순회는 자식 쪽 처리를 마친 뒤 노드를 처리한다. 중위 순회는 왼쪽 부분 트리와 노드, 오른쪽 부분 트리의 순서다.
중위 순회가 값을 정렬된 순서로 내놓는 것은 적절한 순서 규칙을 가진 이진 탐색 트리일 때다. 임의의 이진 트리를 중위 순회한다고 자동으로 정렬되지는 않는다.
어떤 모양을 허용하는가
완전 이진 트리는 마지막 층을 제외한 층이 채워지고 마지막 층은 왼쪽부터 채워지는 구조다. 모든 내부 노드가 자식 둘을 갖는다는 조건이나 모든 잎의 깊이가 같다는 조건과는 구분된다.
배열 기반 힙은 완전 이진 트리의 모양을 활용하여 부모와 자식 위치를 인덱스로 계산할 수 있다. 반면 빈 자리가 많은 일반 트리에서는 포인터나 다른 표현이 더 적절할 수 있다.