균형 검색 트리 깊이에 대한 증거

Question

t가 n 요소가있는 균형 잡힌 bST, l 왼쪽 하위 트리 및 r의 오른쪽 인 경우, 깊이가 2Log (n) + 1보다 작거나 같다는 것을 어떻게 증명할 수 있습니까?

내가 가진 유도에 의한 증거가 있지만 나는 그것을 얻지 못합니다.

(StackoverFlow는 주로 프로그래밍 지향적이지만 이진 검색 트리에 대한 몇 가지 질문을 발견하고 시도해보기로 결정했습니다.

Answer 1

"균형"의 정의에 따르면 동일한 노드의 모든 왼쪽 및 오른쪽 하위 트리의 깊이는 최대 하나씩 다릅니다. "깊이"는 일반적으로 "나무 뿌리에서 잎까지 가장 긴 걸어가는 단계의 수"로 정의되므로 예를 들어 뿌리가 1 개와 잎이 2 개있는 BST (균형 BST로 배열 될 수있는 유일한 방법)입니다. 깊이 하나를 가지고 있다고 말합니다 (하나의 뿌리와 하나의 잎을 가진 것과 마찬가지로 깊이 두 가지를 줄 수있는 약간 다른 정의를 사용하는 것처럼 보입니다. 뿌리 인 루트가있는 사람 (단일 요소)은 깊이 0 을가집니다. (요소가 0 인 BST는 없습니다).

그래서 n <= 3 요소의 경우, d (n) 호출 위에서 정의 된 나무 깊이를 명확하게 D(n) < log(n) + 1 (와 함께 log 검사 별 기본 2를 의미합니다 1 = D(2) < log(2) + 1 = 2 (그리고 또한 1 = D(3) 불평등의 RHS, log(3) + 1, 실제로입니다 > 2), 그리고 0 = D(1) < log(1) + 1 = 1 - 이것은 우리에게 유도베이스를 제공합니다.

유도로 증명을 완료하려면 D(k) < log(k) + 1 모든 k < n, 그런 다음 또한 그것을 따릅니다 D(n) < log(n) + 1.

N이 이상하다면 분명히 왼쪽 및 오른쪽 하위 트리가 있습니다. (n-1)/2 각각의 요소와 나무는 하위 트리보다 깊이 1이 더 높습니다. 하지만 D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (유도 가설에 의해) = 1 + log(n-1) (부터 log((n-1)/2) = log(n-1) - 1) 따라서 Fortiori < 1 + log(n), Qed.

만약에 n 심지어 당신은 같은 단계를 따릅니다 log(n) 대신에 log(n-1) 그리고 "포어 리"마감재가 없으면 증거는 여전히 유지됩니다.

Answer 2

밸런스 바이너리 트리가 완료되면 오른쪽과 왼쪽 하위 트리의 요소 수는 (n-1)/2 일 수 있지만 완료되지 않은 경우 요소의 수는 (n-1)/2로 불과하지 않아야합니다. 마지막 레벨에는 요소가 다를 수 있습니다