정의
- cycle이 없는 undirected connected 그래프
- connected graph : 그래프에 속한 임의의 두 정점 사이에 항상 경로가 존재하는 그래프
- data structure에서는 주로 방향이 있는 directed tree를 이용
- 방향은 주로 부모에서 자식, 위에서 아래 방향
용어
- 노드 (node) : 트리의 기본 구성 요소. 그래프의 vertex
- 루트, 부모, 자식, 형제, 리프
- 경로 (path) : 출발 노드부터 도착 노드까지 이르는 길 사이의 노드 리스트
- 길이 (length) : 출발 노드부터 도착 노드까지 이르는 길 사이의 edge 개수
- 깊이 (depth)
- 노드의 깊이 : 해당 노드와 루트 노드 사이의 길이
- 트리의 깊이 (= 트리의 높이)
- 높이 (height)
- 노드의 높이 : 해당 노드에서 리프 노드까지의 길이들 중 최대값
- 트리의 높이 : 루트 노드의 높이
- 레벨 (level) : 루트 노드부터 해당 노드까지 길이
- 차수 (degree) : 각 노드의 자식의 개수
- 트리의 차수 : 트리의 차수 중 최대값
- 크기 (size) : 노드의 개수
- 너비 (width) : 가장 많은 노드를 가지고 있는 레벨의 크기
- forest : 서로 독립인 트리들의 모임
- subtree : 부분 트리
예시
- 문서 목차
- 디렉토리 구조
- 게임에서 스킬 트리
종류
이진 트리 (Binary Tree)
- 트리의 차수를 2로하는 트리
- 자식의 수가 최대 2이므로 left child, right child와 같은 식으로 표현하기도 함
- 종류
- 정 이진 트리 (full binary tree)
- 포화 이진 트리 (perfect binary tree)
- 완전 이진 트리 (complete binary tree)
- 순회 방법
- 중위 순회 (in-order traversal) : 왼쪽 자식 - 자신 - 오른쪽 자식
- 이진 탐색 트리를 이 방법으로 순회하면 정렬된 결과를 얻을 수 있음
- 전위 순회 (pre-order traversal) : 자신 - 왼쪽 자식 - 오른쪽 자식
- 후위 순회 (post-order traversal) : 왼쪽 자식 - 오른쪽 자식 - 자신
- 레벨 순서 순회 (level-order traversal) : 레벨 순서로 순회 (= BFS)
- 중위, 전위, 후위는 스택으로, 레벨 순서는 큐로 구현 가능
- 중위 순회 (in-order traversal) : 왼쪽 자식 - 자신 - 오른쪽 자식
- 종류
- 이진 탐색 트리 (Binary Search Tree)
- 힙 (Heap)
이진 탐색 트리 (Binary Search Tree, BST)
- 이진 트리의 일종 (이진 트리의 부분집합)
- 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만, 오른쪽 가지에는 노드의 값보다 큰 값들만 있도록 구성
- 어떤 값을 찾아 노드를 거칠 때 왼쪽 또는 오른쪽 subtree로는 갈 필요가 없어짐
- 이진 탐색에 유리한 구조가 됨
- 이상적인 경우에는 검색, 삽입, 삭제가 O(logN) (트리 균형이 잘 맞는 경우)
- 최악의 경우에는 O(N) (트리가 1자로 구성된 경우)
- 트리의 균형이 안맞는 경우 편향(skew) 되었다고 함
- 편향 문제를 해결하기 위해 나온 자가 균형 이진 탐색 트리가 있음
- AVL tree
- Red-black tree
기타 트리
- B tree
- 2-3-4 tree
- B+ tree
- Trie
추후 스터디
- heap
- AVL tree, Red-black tree
- Trie
- B tree ...
hi