6/29 비선형 자료구조
본문 로딩 중...
댓글 0
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
트리(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처럼 다시 처음 노드로 돌아오는 연결이 가능할 수 있습니다.
Develog는 단순히 글을 쓰는 공간이 아닙니다. 성장의 과정을 기록하고, 그 기록으로 나를 증명하며 원하는 기회를 얻는 곳이길 바랐습니다. 누군가의 꿈으로 향하는 중간다리가 되는 것, 그것이 Develog를 만든 이유입니다.
우리들의 게임 발매 이야기
안녕하세요. 플밍 4기 입니다. 게임 개발을 배우기 전 네트워크 엔지니어 도메인에서 익히고 배웠던 네트워크 이론에 대한 기초 입니다. 학습에 도움이 되길 바라며 공유 드립니다.
Develog는 단순히 글을 쓰는 공간이 아닙니다. 성장의 과정을 기록하고, 그 기록으로 나를 증명하며 원하는 기회를 얻는 곳이길 바랐습니다. 누군가의 꿈으로 향하는 중간다리가 되는 것, 그것이 Develog를 만든 이유입니다.
안녕하세요. 플밍 4기 입니다. 게임 개발을 배우기 전 네트워크 엔지니어 도메인에서 익히고 배웠던 네트워크 이론에 대한 기초 입니다. 학습에 도움이 되길 바라며 공유 드립니다.
