6/29 비선형 자료구조
트리(Tree)
계층 구조를 표현하는 비선형 자료구조로, 하나의 루트에서 시작해 부모-자식 관계로 노드들이 연결된다.
BST(Binary Search Tree, 이진 탐색 트리)
각 노드가 최대 2개의 자식을 가지며, 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 만족하는 탐색용 트리이다. 정렬이 보장되어 있다.
힙(Heap)
부모 노드가 자식 노드보다 항상 우선순위가 높거나 낮은 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 꺼내기 위해 사용된다. PriorityQueue는 보통 힙을 기반으로 구현된다.
| 자료구조 | 탐색 | 삽입 | 삭제 | 주요 특징 |
|---|---|---|---|---|
| 일반 트리 | O(N) | O(1) ~ O(N) | O(N) | 정해진 정렬 규칙이 없으면 원하는 값을 찾기 위해 전체를 볼 수 있음 |
| BST 평균 | O(log N) | O(log N) | O(log N) | 값이 균형 있게 배치되어 있으면 빠름 |
| BST 최악 | O(N) | O(N) | O(N) | 한쪽으로 치우치면 연결 리스트처럼 변함 |
| 균형 BST | O(log N) | O(log N) | O(log N) | AVL Tree, Red-Black Tree처럼 균형을 유지하는 BST |
| 힙 | O(N) | O(log N) | O(log N) | 루트의 최솟값/최댓값 확인은 O(1), 특정 값 탐색은 느림 |
| 힙 루트 확인 | O(1) | - | - | 최소 힙이면 최솟값, 최대 힙이면 최댓값을 바로 확인 가능 |
트리 순회 방식
| 순회 방식 | 방문 순서 | 특징 |
|---|---|---|
| 전위 순회 | 부모 → 왼쪽 → 오른쪽 | 부모를 먼저 처리 |
| 중위 순회 | 왼쪽 → 부모 → 오른쪽 | BST에서 오름차순 출력 |
| 후위 순회 | 왼쪽 → 오른쪽 → 부모 | 부모를 마지막에 처리 |
이진탐색트리 주의점
이진탐색트리는 최악의 상황에 노드들이 한쪽 자식으로만 추가되는 불균형 현상이 발생 가능.
이 경우 탐색 영역이 절반으로 줄여지지 않기 때문에 시간복잡도 증가
그래프와 트리의 차이
트리(Tree)는 순환 구조가 없는 그래프입니다.
즉, 어떤 노드에서 출발해서 간선을 따라 이동했을 때 다시 자기 자신으로 돌아오는 경로가 없어야 합니다.
그래프(Graph)는 노드와 간선으로 이루어진 구조이며, 경우에 따라 순환 구조가 존재할 수 있습니다.
즉, A → B → C → A처럼 다시 처음 노드로 돌아오는 연결이 가능할 수 있습니다.
