트리(tree)란??
비선형 자료구조 - 순차적인 연결이 아닌 유기적으로 연결된 자료구조이다.
계층적 관계를 표현한다. - 디렉터리 구조, 조직도
노드(node)로 이루어진 자료구조이다.
그래프의 한 종류이다.
최소 연결 트리라고도 부른다.
사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 이다.
loop나 circuit이 없다. 당연히 self-loop도 없다.
즉, 사이클이 없다.
노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
각 노드는 어떤 자료형으로도 표현이 가능하다.
1. 루트 노드를 갖는다.(한가지)
2. 루트 노드는 0개 이상(0개도 가능)의 자식 노드를 갖고있다.
3. 루트 노드 속 자식 노드 또한 0개 이상의 자식 노드를 갖고있고 이것이 반복된다.
트리의 구조(용어)
- 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
- 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
- 내부 노드(internal): 단말 노드가 아닌 노드
- 간선(edge): 노드를 연결하는 선, link, branch라고도 부른다. - 간선은 정점의 개수 -1개를 가진다. (노드 5개면 간선 4개)
- 형제(sibling): 같은 부모를 가진 노드
- 노드의 크기(size): 자신을 포함한 모든 자식 노드의 수
- 노드의 깊이(depth): 루트에서 해당 노드까지 도달할 떄 거치는 간선의 수
- 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수(degree): 하위 트리 개수 / 간선(degree) = 각 노드가 지닌 가지의 수
- 트리의 차수(degree of tree): 트리의 최대 차수
- 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
트리의 특징
- 두 노드 사이에는 1개의 경로만을 가진다. (루트에서 다른 노드로 갈 떄도 포함)
- 루트 노드가 한 개 = 모든 자식 노드는 한 개의 부모 노드만을 가진다.
- 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
- 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.
이진트리 (binary tree)
각 노드가 최대 2개의 자식 노드를 갖는 트리이다.
- 중위 순회(in-order traversal): 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지
- 전위 순회(pre-order traversal): 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
- 후위 순회(post-order traversal): 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
- 편향 이진 트리 - 한 쪽으로 편향되어 생성된 이진트리
문제점으로는 탐색속도의 저하(편향 트리로 형성이 되면 제일 끝의 요소를 탐색하기 위해 모든 노드들을 탐색해야 한다.) - 포화 이진 트리 - 높이가 h일 때 2^(h+1) - 1 개의 노드개수가 최대 노드의 수, 이 때 최대 노드의 수를 만족하는 트리를 포화 이진트리라고 한다.
내부의 모든 노드들이 2개의 자식을 가지는 트리 (포화 상태) - 완전 이진 트리 - 포화 이진 트리에서 leaf노드들을 오른쪽에서 제거하여 얻어진 트리, 공간의 효율이 좋다.
HR velog