이진 트리 키와 가장 가까운 수를 찾습니다.

Question

균형이 맞지 않은 이진 트리가 있다고합시다. 트리에서 키 k를 검색하고 싶습니다. 그러나, k가 이진 트리에 존재하지 않는다면 k에 가장 가까운 다음 가장 큰 수를 나에게 줄 것입니다.

예를 들어이 숫자 [1,5,6,8,10]이 트리의 키로 있다고 가정합니다. '7'을 검색하면 8을 반환하고 2를 검색하면 5 등을 반환해야합니다.

이러한 검색을 수행하려면 무엇이 수정되어야합니까? 나는 O (log n) 솔루션을 원한다.

Answer 1

"2 진 트리"가 아니라 "2 진 검색 트리"라고 가정하면 y> = x가되도록 트리에서 최소 요소 y를 찾으려면 수정이 필요하지 않습니다.

search(n, x, best_so_far) ::= 
    if n == nil { return best_so_far } 
    if n.value == x { return x } 
    if n.value > x { return search(n.left, x, min(best_so_far, n.value) } 
    if n.value < x { return search(n.right, x, best_so_far) } 

이 함수는 search(root, x, +infinity)이라고합니다.

노드 n의 왼쪽 브랜치를 탐색하는 경우 n의 오른쪽에 아무것도 고려할 필요가 없다는 아이디어가 있습니다. n.value가 x보다 크고 모든 것이 오른쪽에 있습니다. n.value보다. 마찬가지로 노드 n의 오른쪽 분기를 탐색하는 경우 n의 왼쪽에있는 모든 항목을 삭제할 수 있습니다. n.value가 x보다 작고 n의 왼쪽에있는 모든 값이 n.value보다 작습니다.

코드의 런타임은 트리의 높이로 제한되어 있으므로 트리가 균형을 이루면 O (log n)가됩니다.