이진 트리 탐색의 복잡도

Question

데이터 구조에서 이진 트리의 inorder, postorder 및 preorder 순회의 시간 복잡도는 얼마입니까 ?? 그것은 O (n) 또는 O (log n) 또는 O (n^2)입니까 ??

Answer 1

O(n), 이는 각 노드를 한 번 통과하기 때문에 발생합니다. 또는 오히려 - 각 노드에 대해 수행하는 작업량은 일정합니다 (노드의 나머지 부분에 의존하지 않음).

Answer 2

Travesal은 각 노드를 한 번 치기 때문에 모든 주문에서 O (n)입니다. Lookup은 트리가 일종의 스키마 (즉, 바이너리 검색 트리)를 가지고있는 경우 O (n)보다 작을 수있는 곳입니다.

Answer 3

O (n)이라고 말하고 싶습니다. 나는 모든 나무에 적용되는 균형 잡힌 나무를 찾으러 가고 있습니다. T (n)를

T하면 재귀를 사용한다고 가정 = 2 * (N/2) + 1 ----------> (1)

T (N/2) 오른쪽 하위 트리의 경우 T (n/2)이고 기본 사례를 확인하는 경우 '1'입니다.

단순화하면 (1) 순회 (주문 또는 선주문 또는 후순위) 주문이 O (n)임을 증명할 수 있습니다.

Answer 4

In-order, Pre-order 및 Post-order 순회는 Depth-First 순회입니다.

그래프의 경우 Depth First Traversal의 복잡도는 O (n + m)입니다. 여기서 n은 노드 수이고, m은 모서리 수입니다.

이진 트리도 그래프이기 때문에 여기에서도 마찬가지입니다. 각 깊이 우선 탐색의 복잡성은 O (n + m)입니다.

이진 트리의 경우 노드에서 생성 될 수있는 에지 수는 2로 제한되므로 이진 트리의 최대 총 에지 수는 n-1입니다. 여기서 n은 노드의 총 수입니다 .

그러면 복잡성은 O (n + n-1)이되어 O (n)이됩니다.