문자열의 AVL 트리를 인쇄하는 가장 효율적인 방법은 무엇입니까?

Question

나는 순회 (traversal)가 O (n) 시간에 돌아갈 것이라고 생각하고 있습니다. 그보다 나은 점은 logn 시간에 뭔가를 실행하는 것입니다. 그러나 적어도 n 번 실행해야한다는 것을 고려하면 어떻게 될지 모르겠습니다.

O (n)은 여기서 할 수있는 마지막 시간입니까?

Answer 1

변환 및 답변에 CB의 코멘트 @ 확대 : N (당신이 그것을에서 n 개의 문자열을 가진 AVL 트리가 있고 그들 모두를 인쇄하려면

는, 당신은 적어도 Θ을 할 필요가) 총 작업은 단순히 n 개의 문자열 각각을 인쇄해야하기 때문입니다. 목록을 생성하는 데 필요한 작업량을 줄이거 나 목록에 얼마나 많은 항목이 포함되는지 일련의 값으로 간단히 출력 할 수 있습니다.

여기서 더욱 정확해질 수 있습니다. 트리의 모든 문자열을 결합한 길이를 L이라고 가정합니다. 트리의 모든 문자열을 인쇄하는 데 필요한 시간은 각각 Θ (L) 이상이어야합니다. 개별 문자를 출력하는 데 약간의 계산 작업이 필요하기 때문입니다. 따라서 트리의 모든 문자열을 인쇄하려면 적어도 Θ (n + L) 작업을 수행해야한다고 말할 수 있습니다.

여기에 주어진 경계는 올바른 알고리즘이 적어도 많은 작업을 수행해야한다는 것을 의미합니다. 실제로 많은 작업을 수행하는 알고리즘은 아닙니다. 하지만 inorder, preorder, postorder, level-order와 같은 주요 트리 트래버스를 자세히 살펴보면이 시간 경계와 모두 일치한다는 것을 알 수 있습니다.

절약 할 수있는 부분 중 하나는 공간의 복잡성입니다. 트리의 레벨 순회는 트리가 완벽하게 균형을 이루었을 때 (전체 트리가 메모리에 있고 가장 아래 레이어가 Θ (n) 개의 노드를 가질 수 있기 때문에) 전체 공간이 Ω (n)이어야하며, inorder, preorder 또는 postorder traversal은 AVL 트리에서 로그 높이가있는 현재 액세스 경로 만 저장하기 때문에 O (log n) 메모리 만 필요합니다.