이진 트리의 높이 범위

이진 트리의 가능한 높이는 다음과 같습니다. logN < = 높이 < = N-1 (N은 노드 수임)입니다. 그러나 단 하나 또는 두 개의 문장을 사용하여이 해답을 설명하려면 어떻게해야합니까?이진 트리의 높이 범위

2013-11-01 FlowerFire

Logn이란 무엇이며 높이와 관련하여 n-1은 무엇을 의미합니까? – progrenhard

@progenhard 그래서 왜 logN이 최소이고 왜 N-1이 최대 값인지 설명 할 필요가 있다는 것을 의미합니까? – FlowerFire

그래서 하나의 노드를 가진 트리의 높이가 0입니까? 그거 이상 하네. 빈 나무의 높이는 얼마입니까? –

최소 높이와 최대 높이가 발생하는 2 가지 경우를 고려하십시오.

최소 높이 : 각 리프가 아닌 노드는 정확히 두 아이

가있는 경우

최대 높이 : 각 리프가 아닌 노드는 정확히 한 아이, 즉 선형

2013-11-01 06:09:52 sam092

수학적 증거를 사용하는 것보다 훨씬 쉽게 답을 제공하십시오. 감사. – FlowerFire

@FlowerFire 실제로 간단한 그래프를 그리면 설명이 더 쉬울 수도 있습니다. 예 : max의 경우를 설명하기 위해. 높이를 사용하면'1-2-3-4-5-6-7'과 같이 선형 구조를 가진 트리를 그림으로 그릴 수 있습니다 :) – sam092

올바른. 이것은 최악의 경우 인 퇴화 된 2 진 트리가됩니다. – FlowerFire

완벽 균형 잡힌 나무 (잎 이외의 노드가있는 경우 2 명의 자녀를 가짐)는 크기 N = 2^n-1 노드, log2 (N) = n 레벨을 갖는다.

트리의 축약 대소 문자 (모든 노드는 단일 자식을가집니다)는 목록이며 크기 N은 N 수준을가집니다.

2013-11-01 06:23:00 ChuckCottrill

퇴화의 경우, 높이 측면에서 '높이 = N -1'이어야합니다. 그러나 또 다른 대답을 제공하기 위해 당신을 upvote. – FlowerFire

답변