트리와 그래프는 대표적인 *비선형 자료구조 이다. (선형 구조에는 배열, 연결리스트, 스택, 큐 등이 있다.)
트리(Tree)
- 노드로 이루어진 자료구조이다.
- 사이클(cycle) 이 존재할 수 없다.
- 하나의 루트 노드를 가진다. 루트 노드(root node)는 0개 이상의 자식 노드(child node)를 가진다. (반복)
- 자식이 없는 노드는 '말단'(= leaf node)이라고 부른다.
트리의 종류
이진 트리(Binary tree)
- 각 노드가 최대 2개의 자식을 갖는 트리
이진 탐색 트리(Binary search tree)
- 모든 노드가 특정 순서를 가진 이진 트리 (특정 순서 속성은 모든 노드에 대해 반드시 참이여야 한다.)
예) 아래 1번 트리는 '왼쪽 자식 노드 <= n < 오른쪽 자식 노드' 속성을 모드 노드가 따르고 있음으로 이진 탐색 트리가 맞다.
2번 트리의 경우 마지막 노드 12이 최상위 노드 8에 왼쪽에 있기 때문(12 <= 8 거짓이므로) 에 이진 탐색 트리가 아니다.
완전 이진 트리(Complete binary tree)
- 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리
- 마지막 level은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져 있어야 한다.
전 이진 트리(Full bianry tree)
- 모든 노드의 자식이 없거나 정확히 2개를 가진 이진 트리
포화 이진 트리(Perfect binary tree)
- 전 이진 트리 + 완전 이진 트리
- 모든 말단 노드(leaf node)는 같은 높이에 있어야하고 마지막 level 에서 노드의 개수가 최대가 되어야 한다.
- 노드의 개수가 정확히 2^k-1 (k는 트리의 높이) 개가 되어야 한다.
이진 트리 순회 (Traversal)
중위 순회(in-order)
- 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지 (left branch -> root -> right branch) 순서로 노드를 방문(visit) 하고 출력하는 방법이다.
- 이진 탐색 트리의 경우 오름차순으로 출력하게 된다.
전위 순회(pre-order)
- 자식 노드보다 현재 노드를 먼저 방문(visit)하는 방법이다. (root -> left branch -> right branch)
- 가장 먼저 방문하게 될 노드는 항상 root 이다.
후위 순회(post-order)
- 모든 자식 노드들을 먼저 방문한 뒤 마지막에 현재 노드를 방문하는 방법이다. (left branch -> right branch -> root)
- 가장 마지막에 방문하게 될 노드는 항상 root 이다.
이진 힙
최소힙(Min-heaps)
- 원소가 오름차순으로 정렬되어 있다.
- 완전 이진 트리
- 각 노드의 원소가 자식들의 원소(parent <= child)보다 작다. (따라서 루트는 트리 전체의 가장 작은 원소가 된다.)
- 연산: insert(삽입), extract_min(최소원소추출)
최대힙(Max-heaps)
- 내림차순으로 정렬되어 있는 특징만 다를 뿐 최소힙과 동일하다.
트라이(Prefix tree)
- 접두사 트리라고도 불리며, n-차 트리의 변종으로 각 노드에 문자를 저장하는 자료구조이다.
- 각 노드는 1개에서 ALPHABET_SIZE + 1 개까지 자식 노드를 가질 수 있다.
참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview
'algorithm > concept' 카테고리의 다른 글
| [자료구조] 그래프(Graph) (0) | 2022.01.10 |
|---|
