자녀가 최대 두 개인 트리. 왼쪽 자녀와 오른쪽 자녀를 구분한다. 자녀 수를 둘로 묶어두면 크면 오른쪽 작으면 왼쪽 같은 규칙을 얹을 수 있고, 배열에 그대로 담을 수도 있다. 이진 탐색 트리와 힙이 그렇게 만들어진다.
배열 인덱스로 부모와 자녀 찾기
빈칸 없이 왼쪽부터 채워진 트리라면 노드를 순서대로 배열에 넣을 수 있고, 그러면 참조가 아예 필요 없어진다. 1번부터 시작할 때 노드 i의 왼쪽 자녀는 2i, 오른쪽 자녀는 2i + 1, 부모는 i / 2다.
Index 0 1 2 3 4 5 6 7
Array - 5 3 3 4 7 8 9
곱하기와 나누기만으로 위아래를 오간다. 힙이 배열로 구현되는 이유이자, 힙이 굳이 완전 이진 트리 모양을 유지하는 이유다.
모양에 따른 이름
모양을 부르는 이름이 여럿이다. 자녀가 0개 아니면 2개뿐이라 자녀 1개인 노드가 없으면 정 이진 트리(full), 마지막 레벨을 뺀 모든 레벨이 꽉 차 있고 마지막 레벨은 왼쪽부터 채워져 있으면 완전 이진 트리(complete), 모든 레벨이 빠짐없이 채워져 있으면 포화 이진 트리(perfect)다.
모든 노드에서 좌우 서브 트리의 높이 차가 최대 1이면 균형 이진 트리(balanced)라고 한다. 실제로 자주 쓰는 것은 완전 이진 트리와 균형 이진 트리 둘이다.
한쪽으로만 뻗은 트리
모든 노드가 자녀를 하나만 가지면 변질 이진 트리(degenerate)다. 왼쪽으로만 뻗으면 left skewed, 오른쪽으로만 뻗으면 right skewed라고 따로 부르기도 한다.
높이가 N이 되므로 트리를 쓰는 의미가 사라지고 연결 리스트와 같아진다. 이진 탐색 트리에 정렬된 데이터를 넣으면 정확히 이 모양이 나온다.