이 섹션에서 우리는 하나의 이진 트리 데이터 구조의 몇 가지 중요한 속성을 볼 것입니다. 이와 같은 이진 트리가 있다고 가정합니다.
일부 속성은 -
- 레벨 'l'의 최대 노드 수는 $2^{l-1}$ 입니다. 여기서 레벨은 루트 자체를 포함하여 루트에서 노드까지의 경로에 있는 노드 수입니다. 루트 수준을 1로 고려하고 있습니다.
- 높이 h의 이진 트리에 존재하는 최대 노드 수는 $2^{h}-1$입니다. 여기서 높이는 루트에서 리프 경로의 최대 노드 수입니다. 여기서 우리는 노드가 하나인 트리의 높이가 1이라고 생각합니다.
- n개의 노드가 있는 이진 트리에서 가능한 최소 높이 또는 최소 수준 수는 $\log_{2}\lgroup{n+1}\rgroup$ 입니다. 리프 노드의 높이를 0으로 간주하면 공식은 $\log_{2}\lgroup{n+1}\rgroup-1$ 이 됩니다.
- 'L' 잎이 있는 이진 트리에는 최소 $\log_{2}{L+1}$ 수의 레벨이 있습니다.
- 이진 트리에 0 또는 2개의 자식이 있는 경우 리프 노드의 수는 항상 2개의 자식이 있는 노드보다 하나 더 많습니다.
주의 바이너리 트리는 트리의 한 종류이기 때문에; 그래프 이론에서 트리의 모든 속성을 가지고 있습니다.