티스토리 뷰
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.
* 트리(Tree)
- 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조(Hierarchical Data Structure)
[트리의 구조]
* 트리 용어
- 노드(Node) : 트리를 구성하는 원소(자료)
- 간선(Edge) : 노드를 연결하는 선
- 루트 노드(Root Node) : 트리의 시작 노드, Level 0
- 형제 노드(Sibling Node) : 같은 부모 노드의 자식 노드들
- 서브 트리(Subtree) : 자식 노드들은 각각 독립하여 새로운 트리를 구성할 수 있으며, 각 노드는 자식노드 수만큼의 수를 가짐
- 노드의 높이(=레벨) : 루트에서 그 노드에 이르는 경로에 있는 간선의 수
* 이진 트리(Binary Tree)
- 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 트리
- 이진 트리의 서브 트리들 역시 모두 이진 트리여야 하며, 두개의 자식노드 중에서 왼쪽에 있는 노드를 left node, 오른쪽에 있는 노드를 right node라고 함
* 이진 트리의 분류
1) 포화 이진 트리(Full Binary Tree)
- 모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리를 의미함
- 높이가 h일 때 (2^(h+1)-1)개의 최대 노드수를 갖는 이진 트리
- 레벨 별로 왼쪽에서 오른쪽으로 차례로(2^(h+1)-1)까지 번호를 붙임
2) 완전 이진 트리(Complete Binary Tree)
- 높이가 h고, 노드 수가 n개일 때(단, n < 2^(h+1)-1), 노드의 위치가 포화 이진 트리의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리
- (n+1)번부터 ( 2^(h+1)-1)번까지의 노드는 공백 노드가 됨
3) 편향 이진 트리(Skewed Binary Tree)
- 이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리
* 이진 트리의 순회
- 순회(Traversal) : 이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것
1) 전위 순회(Preorder Traversal)
- 루트노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 순회하는 방식
- 깊이 우선 순회라고도 함
순회 결과 : A → B → D → H → I → E → J → K → C → F → L → M → G → N → O
2) 중위 순회(Inorder Traversal)
- 왼쪽 서브트리 → 노드 → 오른쪽 서브트리 순으로 순회하는 방식
- 대칭 순회라고도 함
순회 결과 : H → D → I → B → J → E → K → A → L → F → M → C → N → G → O
3) 후위 순회(Postorder Traversal)
- 왼쪽 서브트리 → 오른쪽 서브트리 → 노드 순으로 순회하는 방식
순회 결과 : H → I → D → J → K → E → B → L → M → F → N → O → G → C → A
* 이진 탐색 트리(Binary Search Tree)
- left node 에는 부모노드보다 작은 값이 저장됨
- right node 에는 부모노드와 값이 같거나 큰 값이 저장됨
- 모든 노드는 중복된 값을 가지지 않음
- 이진 탐색 트리를 사용함으로 데이터를 효율적으로 검색 할 수 있음
- 원하는 값을 찾을 때까지 현재의 node값보다 찾고자하는 값이 크면 왼쪽으로 움직이고, 작으면 오른쪽으로 움직임
* 힙(Heap)
- 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조
* 힙의 종류 및 특징
- 최대 힙(Max Heap) : 키값이 가장 큰 노드를 찾기 위한 힙, 부모노드의 키값 >= 자식노드의 키값
- 최소 힙(Min Heap) : 키값이 가장 작은 노드를 찾기 위한 힙, 부모노드의 키값 <= 자식노드의 키값
- 최소 힙에서는 키값이 가장 작은 노드가 루트 노드가 되며, 일반적으로 힙은 최대 힙을 의미함
- 같은 키값의 노드가 중복될 수 있음
* 힙과 이진 탐색 트리 비교
- 공통점
힙과 이진 탐색 트리는 모두 이진 트리 자료구조를 사용한다.
- 차이점
힙의 경우, 최대 힙: 자식 노드값 ≦ 부모 노드값, 최소 힙: 자식 노드값 ≧ 부모 노드값 최대 또는 최소값을 검색하기 위해서 사용함
이진 탐색 트리의 경우, 왼쪽 자식 노드 < 부모 노드 값 <= 오른쪽 자식 노드 탐색을 위해서 사용함
'개인공부 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조] 정렬(Sort) 개념 (0) | 2023.11.22 |
|---|---|
| [자료구조] 그래프(Graph) (0) | 2023.11.22 |
| [자료구조] 큐(Queue) (0) | 2023.11.20 |
| [자료구조] 스택(Stack) (0) | 2023.11.20 |
| [자료구조] 연결 리스트(Linked List) (0) | 2023.11.20 |