이진 트리의 밀도

Question

주어진 이진 트리의 밀도를 어떻게 찾을 수 있습니까? 나는이 면접 시험 질문을 우연히 만나고, 그들이 밀도로 무엇을 의미하는지에 관해 확신하지 못했다! 어떤 도움을 주시면 감사하겠습니다.

Answer 1

조밀 한 이진 트리 (이것은 2^(h + 1) - 1 nodes) 가까이 있습니다. 스파 스 트리 (이것은 가까운 h 노드가) 연결리스트에 가깝다. h는 하나의 루트 노드가 트리의 높이 완벽에 가까운

(n - h)/(2^(h + 1) - h - 1) 

난 그냥 공식 최대 것을 만들어, 그래서 인터뷰 대답을 사용자의 요구에 맞게한다면 모르겠지만, 그것은거야 : 높이 0

밀도의 간단한 측정 될 수있다 퇴화 된 나무는 0, 완벽한 나무는 1을 주면 빽빽한 나무의 경우 1에 가까운 숫자를 얻을 수 있습니다. nd 숫자는 0에 가깝다.

Wikipedia에는 이진 트리에 대한 많은 정보가 있습니다.

Answer 2

이진 트리에서 각 레벨의 노드 수는 값 범위 내에 속합니다. 레벨 0에는 루트 노드가 1 개 있습니다. 레벨 1에는 1 또는 2 노드가있을 수 있습니다. 모든 레벨 k에서 노드 수는 1에서 2k 사이입니다. 레벨 당 노드 수는 트리의 밀도에 영향을줍니다. 직관적으로 밀도는 트리의 높이에 비례하여 트리의 크기 (노드 수)를 측정 한 것입니다.