균형 이진 검색 트리의 요소에 도달하는 최대 시간이 log n 인 이유는 실제로 완벽하게 균형 잡힌 트리가 1, 3, 7, 15 요소 (즉 1 2의 배수보다 작음). 여기에 주어진 대답 Why is the height of a balanced binary search tree log(n)? (Proof)은 우리가 2^N 개의 노드 (2의 배수)를 가지고 있다고 가정합니다.균형 이진 검색 트리의 높이
그러나이 홀수의 로그를 취하면 높이의 라운드 수를 얻지 못할 것입니다!
질문 :
이그것이 정말 로그인되어 (N + 1) 그러나 그것은 거대한 N에서 무시할 이후 우리가 +1을 삭제 하시겠습니까?
가장 낮은 상한입니다. 일부 n에서는 도달했습니다. 루트가있는 사소한 트리의 높이는 오직 가정 한 것처럼 0이 아니라 1로 정의됩니다. 예 : 3 개의 요소가있는 완벽하게 균형 잡힌 트리는 높이가 1이고 4 개의 요소가있는 트리는 log (4) 인 높이가 2입니다.
상수는 중요하지 않은 한 O(..) 표기법에서 제거됩니다. 귀하의 예제에서 + 1을 추가해도 런타임에 영향을 미치지 않으므로 대신 O(log n)을 말합니다.
각 단계에서 여전히 검색해야하는 트리의 크기를 절반으로 줄여주기 때문에 균형 이진 트리에서 요소를 찾는 것이 O(log n)입니다. 이 큰 O 표기법은 n이 증가함에 따라 알고리즘의 런타임을 표현합니다. 사용자가 수행 할 작업 수를 계산하는 방법으로는 사용되지 않습니다 (몇 가지 추가 작업이 포함될 수 있으므로).
당신이 2^N리프 노드에 대한 협상에 링크 된 질문이 너무 2^2 = 4 리프 노드와 균형 이진 트리 (7 개) 전체 노드를했을합니다. 이 질문에서 N의 의미는 n과 같지 않습니다.