자료구조
트리, 힙
탁재민
2024. 2. 12. 17:48
트리
노드(node)가 부모(parent)와 자식(children) 관계를 이루며 간선(edge)으로 연결된 계층적 비선형 자료구조
특징
- 계층 구조: 노드들이 부모-자식 관계를 가짐
- 단일 경로: 하나의 루트 노드를 가지며, 루트 노드에서 어떤 노드까지 이르는 경로는 유일
- 순환 구조 없음: 어떤 노드에서 시작해서 같은 노드로 돌아가는 경로가 존재하지 않음(그래프와의 차이점)
- 재귀적 구조: subtree 내부에 다시 subtree를 가지는 재귀적 구조
용어
- 노드(Node): 데이터와 자식 노드에 대한 참조를 가지는 트리의 기본 요소
- 간선(Edge): 노드와 노드를 잇는 선
- 루트 노드(Root Node): 트리의 최상위에 위치하는 노드
- 부모 노드(Parent Node): 어떤 노드의 바로 위에 있는 노드
- 자식 노드(Children Node):어떤 노드의 바로 아래에 있는 노드
- 리프 노드(Leaf Node): 자식 노드를 가지지 않는 노드
- 조상(Ancestor): 어떤 노드보다 위에 있는 모든 노드
- 자손(Descendant): 어떤 노드보다 아래에 있는 노드들을 가리킵니다.
- 형제 노드(Sibling Node): 같은 부모를 가진 노드
- 서브 트리(Subtree): 특정 노드와 해당 노드의 자손들로 이루어진 트리(부분집합)
- 높이(Height): 루트 노드에서 가장 깊은 리프 노드까지의 거리
- 깊이(Depth): 루트 노드에서부터 특정 노드까지의 거리
- 레벨(Level): 트리의 각 층. 루트 노드가 0층에 있으며, 그 다음 층마다 1씩 증가
순회 방법
- 전위 순회(Pre-order Traversal): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
- 중위 순회(In-order Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
- 후위 순회(Post-order Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
- 레벨 순회(Level-order Traversal): 루트 노드부터 시작하여 각 레벨별로 왼쪽에서 오른쪽으로
사용 목적
- 계층적 구조 표현: 파일 시스템의 폴더 및 파일 구조, 조직도, JSON 문서 등을 표현
이진 탐색 트리
효율적인 데이터 탐색, 정렬을 위한 이진 트리
특징
- 모든 원소는 유일한 키를 가짐
- 왼쪽 서브트리 노드들의 키 < 루트 노드 키 < 오른쪽 서브트리 노드들의 키
- 서브 트리들 또한 이진 탐색 트리
연산
- 탐색, 삽입, 삭제 시간복잡도
- 편향: O(n)
- 균등: O(log n)
- 중위 순회: 정렬된 순서 얻음, O(n)
- 삭제 방법:
- 리프 노드: 그냥 삭제
- 자식이 1개인 노드: 삭제하려는 노드의 부모 노드와 삭제하려는 노드의 자식 노드를 연결
- 자식이 2개인 노드: 삭제할 노드의 오른쪽 서브트리에서 가장 작은 키 또는 왼쪽 서브트리에서 가장 큰 키를 삭제하려는 노드의 위치로 교체
힙
최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
특징
- 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 차례대로 채워져 있는 구조
- 최대 힙(Max Heap): 각 노드의 값이 해당 자식 노드의 값보다 크거나 같은 힙
- 최소 힙(Min Heap): 각 노드의 값이 해당 자식 노드의 값보다 작거나 같은 힙
- 배열 사용 힙 구조
- 왼쪽 자식 index = (부모 index) * 2
- 오른쪽 자식 index = (부모 index) * 2 + 1
- 부모 index = (자식 index) / 2
연산
- 삽입: 새로운 원소를 힙의 맨 끝에 추가한 후,부모 요소와 반복적으로 비교 후 교환해 힙 속성 유지(시간복잡도: O(log n))
- 삭제: 루트 노트 삭제 후, 자식 요소와 반복적으로 비교 후 교환해 힙 속성 유지(시간복잡도: O(log n))
사용 목적
- 스케줄링(Scheduling): 운영 체제에서 우선순위가 높은 프로세스나 작업을 먼저 실행하도록 스케줄링하는 데에 활용