완전한 이진 트리의 마지막 레벨에서 가장 오른쪽 노드의 위치를 ​​찾는 방법은 무엇입니까?

Question

이진 트리에서 문제가 발생했습니다. 문제가 발생하면 전체 이진 트리의 마지막 레벨에서 오른쪽 노드를 찾아야합니다. 여기서 문제는 O (n) 시간에 수행해야한다는 것입니다. 멈춤 지점, O (n)에서하는 것은 모든 요소를 ​​순회하면서 간단하지만 O (n) 미만의 복잡성에서이 작업을 수행 할 수있는 방법이 있습니다. 인터넷을 통해 많은 탐색을했습니다. 그 물건에 관해서 아무것도 얻지 마라. 미리 감사드립니다.

Answer 1

완전한 이진 트리이므로 나뭇잎에 도달 할 때까지 모든 오른쪽 노드로 이동하면 O (N)이 아니라 O (logN)가됩니다. 정규 이진 트리에서는 최악의 경우 모든 노드가 오른쪽으로 정렬되기 때문에 O (N)이 필요하지만 완전한 이진 트리이므로

Answer 2

예, O(log(n)^2)에서 할 수 있습니다. 이진 검색을 변형하여

이것은 가장 왼쪽의 요소 으로 이동 한 다음 두 번째로 왼쪽 요소로 이동 한 다음 네 번째로 가장 왼쪽의 요소 인 8 번째로 이동하여 수행 할 수 있습니다. 이러한 요소가 없을 때까지. 마지막으로 찾은 요소가 i 번째이고 처음으로 2i이 아닌 것으로 가정 해 보겠습니다.

이제이 범위에서 이진 검색을 할 수 있습니다.

총 반복 횟수는 O(log(n/2)) = O(logn)이고 각 반복은 전체 트리를 추월하기 때문에 총 시간은 O(log(n)^2)입니다.

---

여기에서

(1)과 다음은 "X leftest 요소는"트리의 가장 깊은 수준의 노드 만 참조한다.

Answer 3

노드 수를 알고 있다고 가정합니다. 그 번호를 n으로합시다.

완전한 이진 트리에서 레벨 i은 레벨 i - 1보다 두 배 많은 노드 수를 갖습니다.

사이에서 n을 반복적으로 나눌 수 있습니다. 나머지가있는 경우 n은 올바른 아동입니다. 그렇지 않으면 왼쪽 자식입니다. 나머지가 있든 없든 시퀀스가되도록 스택에 저장하는 것이 좋습니다.

일부 등 :

Stack<char> s; 
while (n > 1) 
{ 
    if (n % 2 == 0) 
    s.push('L'); 
    else 
    s.push('R'); 
    n = n/2; // n would int so division is floor 
} 

while 완료는, 스택은 가장 오른쪽 노드의 경로가 포함되어 있습니다.

while이 실행 된 횟수는 log_2(n)입니다.