Tree
- Binary tree
- Binary search tree
- Heap tree
Tree traversal
Tree
트리는 그래프의 여러 구조 중 무방향 그래프의 구조를 가지고 있다.
데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결되는 계층적 자료구조이며, 하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조로 되어 있다. 또한 아래로만 뻗기 때문에 사이클이 없다.
용어
- root node, parent node, child node, leaf node
- level - 노드와 노드의 간격. root node 가 Level 1 이다.
- 높이(height) - root node 부터 특정 node 까지의 레벨
- 깊이(depth) - 특정 노드부터 시작하여 root 까지의 레벨
트리의 예시 : 폴더구조, 대진표, 조직도 등
Binary Tree (이진 트리)
효율적인 탐색을 위해 만들어진 여러가지 트리 중 많이 쓰이는 트리이다.
자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 정의한다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 Full binary tree(정 이진 트리), Complete binary tree (완전 이진 트리), Perfect binary tree (포화 이진 트리)로 나뉜다.
| 이름 | 의미 |
|---|---|
| full(정) | 각 노드가 0 개 혹은 2개의 자식 노드를 갖는 트리 |
| complete(완전) | 왼쪽부터 오른쪽으로 채워 가면서, 마지막 레벨을 제외한 모든 레벨이 차 있고, 마지막 레벨에 적어도 하나의 노드가 있는 트리 |
| perfect(포화) | 모든 레벨이 가득 차 있는 트리 |
Binary Search Tree (이진 탐색 트리)
모든 왼쪽 자식은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식은 루트나 부모보다 큰 값을 가진 트리를 이진 탐색 트리라고 정의한다.
Heap Tree (Heap)
Heap 은 우선순위 큐를 구현하기위한 트리로, 완전 이진 트리 형태를 가진다.
특징
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(혹은 항상 작은) 이진 트리를 말한다.
- 힙 트리는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
종류
- min heap (최소 힙) :
부모 <= 자식형태의 heap. root 에는 최소값이 위치한다. - max heap (최대 힙) :
부모 >= 자식형태의 heap. root 에는 최대값이 위치한다.
이미지 : Heap Data Structure | GeeksforGeeks
구현
- 힙을 저장하는 표준적인 자료구조는 배열 이다.
- 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
- 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
- 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
힙에서의 부모 노드와 자식 노드의 관계
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1부모의 인덱스 = (자식의 인덱스) / 2의 몫. (나머지는 무시)
이미지 : [자료구조] 힙(heap)이란 | Heee's Development Blog
삽입/삭제가 일어날 경우 노드들이 위치를 바꾸며 규칙에 맞게 정렬된다.
Tree traversal (트리 순회)
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것.
- 크게 세가지로 나뉜다. 나뉘는 기준은 루트를 언제 체크할 것이냐이다.
- 순회는 항상 왼쪽에서 오른쪽으로 진행된다.
1. pre-order (전위 순회)
먼저 루트를 체크한 뒤 왼쪽이 끝나면 오른쪽을 체크한다.
2. in-order (중위 순회)
먼저 왼쪽을 체크한 뒤 루트를 체크하고 오른쪽을 체크한다.
3. post-order (후위 순회)
먼저 왼쪽을 체크한 뒤 오른쪽을 체크하과 루트를 체크한다.
위 세 순회는 DFS 의 일종이다.
그외
Red-Black tree - 균형을 알아서 맞추는 이진 탐색 트리
B-tree 등
참고
