정의
트리 자료구조의 가장 일반적인 형태입니다.가장 자유로운 트리 구조로, 자식의 수에 제한이 없어 각 노드가 0개 이상의 자식 노드를 가질 수 있습니다.
트리 자료구조의 구조와 동일한 구조를 가지며, 계층 구조 표현에 주로 쓰입니다.
계층 구조(파일 시스템, 조직도, XML/JSON 구조 등)에 활용됩니다.
탐색·삭제가 비효율적이라, 성능 최적화가 필요한 경우에는 다른 트리 구조를 사용합니다.
시간 복잡도
정렬 규칙이 없어 연산 복잡도가 단순합니다.
탐색(Search): O(n)
- 일반 트리에는 정렬 규칙이 없음 → 원하는 값을 찾으려면 최악의 경우 모든 노드를 확인해야 함.
삽입(Insert): O(1) ~ O(n)
- 부모 노드를 이미 알고 있다면 자식으로 바로 붙이면 되므로 O(1).
- 부모를 찾는 과정까지 포함한다면 O(n) (탐색 후 삽입).
삭제(Delete): O(n)
- 삭제하려는 노드를 찾는 데 O(n)이 걸림.
- 찾은 후 삭제 자체는 빠르지만, 탐색 비용 때문에 전체는 O(n).
순회(Traversal): O(n)
- 모든 노드를 방문해야 하므로 당연히 O(n).
- (Preorder / Postorder / Level-order 모두 동일하게 O(n))
728x90