이진 검색 트리 작업 시간 분석

Question

이진 검색 트리에 대한 내용은 노드가 n 개있는 완전한 트리 (리프 노드를 제외한 모든 노드에 두 개의 자식이 있음)가없는 경우 경로가 1 + log n 노드 이상일 수 없음을 읽었습니다. 내가 잘못 않은 곳 ....

the first level of bst has only one node(i.e. the root)-->2^0 
the second level have 2 nodes(the children of root)---->2^1 
the third level has 2^3=8 nodes 
. 
. 
the (x+1)th level has 2^x nodes 

so the total number of nodes =n = 2^0 +2^1 +2^2 +...+2^x = 2^(x+1)-1 
so, x=log(n+1)-1 

now as it is a 'complete' tree...the longest path(which has most no of nodes)=x 
and so the nodes experienced in this path is x+1= log(n+1) 

는 그럼 어떻게 숫자 1 +가 올 N 로그 않았다 여기

내가했던 계산은 ... 당신이 나를 보여줄 수있다 ...?

Answer 1

짧은 대답 : 완전한 (또는 완전) 이진 트리의 레벨 수 x는 n 노드의 수이고, log2(n+1)이다 (또는, n = 2^(x-1)). x 레벨의 트리는 높이가 x-1입니다. 루트에서 노드까지의 가장 긴 경로는 x = log2(n+1) 개 노드 (및 x-1 에지)입니다.

n+1은 2의 거듭 제곱이므로 여기에 log2(n+1) = 1 + floor(log2(n))이 있습니다. 즉, 1 + log2(n)이 올바른 상한이지만 절대 정수가 아닙니다.

귀하의 계산에서 x이 높이 또는 레벨 수를 나타내는 지 여부는 불분명합니다.