트리가 단일 값 트리인지 여부를 결정하는 데 시간 복잡성이 있습니까?

Question

최근에, 나는 이진 트리에이 질문에 건너 온 : 큰-O는 그것이 유니 값 (모든 요소가 같은 값이다)인지를 결정하기 위해 무슨 어떤 임의의 비 균형 트리 감안할 때

1. .

2. 위의 경우 가장 큰 big-O 복잡도 인 균형 숫자 트리 또는 선형 트리가 발생합니까?

   1. 이 나무가 univalue 경우, 우리는 각 노드를 확인해야합니다 확인하려면 :

는이 질문에 대한 내 대답이다. 그래서, 복잡성은 O (n)입니다.

동일한 수의 노드가있는 경우 선형 트리 또는 균형 트리인지에 관계없이 동일한 수의 비교가 있습니다. 따라서 복잡성은 동일합니다.

이 정보가 맞습니까?

Answer 1

임의의 2 진 트리가 주어진다면, 최악의 경우 모든 노드를 검사하여 동일한 값을 갖는지 여부를 판별해야합니다. 여기에 사용할 수있는 간단한 적의 논쟁이 있습니다 - 알고리즘이 모든 값을 보지 않는다면 트리의 고유 한 값 사이에 아무런 관련이 없으므로 적들이 n-1 값이 모두 같은 트리를 제공 할 수 있습니다. 마지막 값을 보지 않았다면, 적들은 그 값을 당신의 알고리즘이 말하는 것과 반대로 설정함으로써 당신의 알고리즘을 잘못되게 할 수 있습니다. 당신은 바이너리 검색 나무에 대해 이야기하는 경우 반면에

, 당신은 시간이 트리의 높이 시간 O (H)에이 문제를 해결할 수 있습니다. 특히 첫 번째 값과 마지막 값을 살펴보고 두 값이 같은지 확인하십시오. 그렇다면 트리의 모든 중간 값이 동일해야합니다. 그렇지 않은 경우 두 가지 고유 한 값을 목격했습니다. 이것은 완벽하게 균형 잡힌 트리에서 O (log n) 시간에 실행되고 축퇴 연결 목록에서 O (n)으로 실행됩니다. 이것이 일반적인 이진 트리의 경우보다 더 흥미로운 질문이기 때문에 이것이 원래의 질문에서 물어 본 것일 수도 있습니다 (필자의 견해로는 적어도).

희망이 도움이됩니다.